Delaunay 三角剖分

¥Delaunay triangulations

Delaunay 三角剖分是由 x 和 y 方向上的一组点形成的三角形网格。没有任何点位于任何三角形的外接圆内，这对于某些应用来说是一个很好的几何属性，并且有助于避免“细长”三角形。Delaunay 三角剖分是 Voronoi 图 的对偶。

¥The Delaunay triangulation is a triangular mesh formed from a set of points in x and y. No point is inside the circumcircle of any triangle, which is a nice geometric property for certain applications, and tends to avoid “sliver” triangles. The Delaunay triangulation is the dual of the Voronoi diagram.

new Delaunay(points)

源代码 · 返回给定平面点数组 [x0, y0, x1, y1, …] 的 Delaunay 三角剖分。

¥Source · Returns the Delaunay triangulation for the given flat array [x0, y0, x1, y1, …] of points.

const delaunay = new d3.Delaunay(Float64Array.of(0, 0, 0, 1, 1, 0, 1, 1));

给定的点可以是任何类似数组的类型，但通常是 Float64Array。

¥The given points may be any array-like type, but is typically a Float64Array.

delaunay.points {#delaunay_points}

点的坐标为数组 [x0, y0, x1, y1, …]。

¥The coordinates of the points as an array [x0, y0, x1, y1, …].

delaunay.halfedges {#delaunay_halfedges}

半边索引为 Int32Array [j0, j1, …]。对于每个索引 0 ≤ i < halfedges.length，存在一条从三角形顶点 j = halfedges[i] 到三角形顶点 i 的半边。等价地，这意味着三角形 ⌊i / 3⌋ 与三角形 ⌊j / 3⌋ 相邻。如果 j 为负数，则三角形 ⌊i / 3⌋ 是 凸包 上的外部三角形。例如，渲染 Delaunay 网格的内部边缘三角测量：

¥The halfedge indexes as an Int32Array [j0, j1, …]. For each index 0 ≤ i < halfedges.length, there is a halfedge from triangle vertex j = halfedges[i] to triangle vertex i. Equivalently, this means that triangle ⌊i / 3⌋ is adjacent to triangle ⌊j / 3⌋. If j is negative, then triangle ⌊i / 3⌋ is an exterior triangle on the convex hull. For example, to render the internal edges of the Delaunay triangulation:

const {points, halfedges, triangles} = delaunay;
for (let i = 0, n = halfedges.length; i < n; ++i) {
  const j = halfedges[i];
  if (j < i) continue;
  const ti = triangles[i];
  const tj = triangles[j];
  context.moveTo(points[ti * 2], points[ti * 2 + 1]);
  context.lineTo(points[tj * 2], points[tj * 2 + 1]);
}

另请参阅 delaunay.render。

¥See also delaunay.render.

delaunay.hull {#delaunay_hull}

一个 Int32Array，其中包含按逆时针顺序构成凸包的点索引。如果点共线，则按顺序返回它们。

¥An Int32Array of point indexes that form the convex hull in counterclockwise order. If the points are collinear, returns them ordered.

另请参阅 delaunay.renderHull。

¥See also delaunay.renderHull.

delaunay.triangles {#delaunay_triangles}

三角形顶点索引为 Uint32Array [i0, j0, k0, i1, j1, k1, …]。每个相邻的索引三元组 i, j, k 构成一个逆时针三角形。三角形点的坐标可以通过 delaunay.points 找到。例如，渲染三角形 i：

¥The triangle vertex indexes as an Uint32Array [i0, j0, k0, i1, j1, k1, …]. Each contiguous triplet of indexes i, j, k forms a counterclockwise triangle. The coordinates of the triangle’s points can be found by going through delaunay.points. For example, to render triangle i:

const {points, triangles} = delaunay;
const t0 = triangles[i * 3 + 0];
const t1 = triangles[i * 3 + 1];
const t2 = triangles[i * 3 + 2];
context.moveTo(points[t0 * 2], points[t0 * 2 + 1]);
context.lineTo(points[t1 * 2], points[t1 * 2 + 1]);
context.lineTo(points[t2 * 2], points[t2 * 2 + 1]);
context.closePath();

另请参阅 delaunay.renderTriangle。

¥See also delaunay.renderTriangle.

delaunay.inedges {#delaunay_inedges}

传入的半边索引为 Int32Array [e0, e1, e2, …]。对于每个点 i，inedges[i] 是传入半边的半边索引 e。对于重合点，半边索引为 -1；对于凸包上的点，传入半边位于凸包上；对于其他点，传入半边的选择是任意的。内边表可用于遍历 Delaunay 三角剖分；另见 delaunay.neighbors。

¥The incoming halfedge indexes as a Int32Array [e0, e1, e2, …]. For each point i, inedges[i] is the halfedge index e of an incoming halfedge. For coincident points, the halfedge index is -1; for points on the convex hull, the incoming halfedge is on the convex hull; for other points, the choice of incoming halfedge is arbitrary. The inedges table can be used to traverse the Delaunay triangulation; see also delaunay.neighbors.

Delaunay.from(points, fx, fy, that) {#Delaunay_from}

提示

Delaunay.from 通常比 新的 Delaunay 函数 慢，因为它需要实现一个新的 xy 坐标平面数组。

¥Delaunay.from is typically slower than new Delaunay because it requires materializing a new flat array of xy coordinates.

源代码 · 返回给定点数组或可迭代对象的 Delaunay 三角剖分。如果未指定 fx 和 fy，则 points 被假定为一个由两个元素组成的数字数组：[[x0, y0], [x1, y1], …].

¥Source · Returns the Delaunay triangulation for the given array or iterable of points. If fx and fy are not specified, then points is assumed to be an array of two-element arrays of numbers: [[x0, y0], [x1, y1], …].

const delaunay = d3.Delaunay.from([[0, 0], [0, 1], [1, 0], [1, 1]]);

否则，fx 和 fy 是按顺序为 points 数组中的每个元素调用的函数，并且必须返回每个点的相应 x 和 y 坐标。

¥Otherwise, fx and fy are functions that are invoked for each element in the points array in order, and must return the respective x and y coordinate for each point.

const delaunay = d3.Delaunay.from([{x: 0, y: 0}, {x: 0, y: 1}, {x: 1, y: 0}, {x: 1, y: 1}], (d) => d.x, (d) => d.y);

如果指定了该参数，则函数 fx 和 fy 将以此参数调用。（请参阅 Array.from。）

¥If that is specified, the functions fx and fy are invoked with that as this. (See Array.from for reference.)

delaunay.find(x, y, i) {#delaunay_find}

delaunay.find(0, 0) // -1

示例 · 源代码 · 返回距离指定点 ⟨x, y⟩ 最近的输入点的索引。搜索从指定的点 i 开始。如果未指定 i，则默认为零。

¥Examples · Source · Returns the index of the input point that is closest to the specified point ⟨x, y⟩. The search is started at the specified point i. If i is not specified, it defaults to zero.

delaunay.neighbors(i) {#delaunay_neighbors}

delaunay.neighbors(-1) // []

源代码 · 返回与指定点 i 相邻点索引的可迭代对象。如果 i 是重合点，则可迭代对象为空。

¥Source · Returns an iterable over the indexes of the neighboring points to the specified point i. The iterable is empty if i is a coincident point.

delaunay.render(context) {#delaunay_render}

源代码 · 将 Delaunay 三角剖分的边渲染到指定的上下文。指定的上下文必须实现 CanvasPathMethods API 中的 context.moveTo 和 context.lineTo 方法。如果未指定上下文，则返回 SVG 路径字符串。

¥Source · Renders the edges of the Delaunay triangulation to the specified context. The specified context must implement the context.moveTo and context.lineTo methods from the CanvasPathMethods API. If a context is not specified, an SVG path string is returned instead.

delaunay.renderHull(context) {#delaunay_renderHull}

源代码 · 将 Delaunay 三角剖分的凸包渲染到指定的上下文。指定的上下文必须实现 CanvasPathMethods API 中的 context.moveTo 和 context.lineTo 方法。如果未指定上下文，则返回 SVG 路径字符串。

¥Source · Renders the convex hull of the Delaunay triangulation to the specified context. The specified context must implement the context.moveTo and context.lineTo methods from the CanvasPathMethods API. If a context is not specified, an SVG path string is returned instead.

delaunay.renderTriangle(i, context) {#delaunay_renderTriangle}

源代码 · 将 Delaunay 三角剖分的三角形 i 渲染到指定的上下文。指定的上下文必须实现 CanvasPathMethods API 中的 context.moveTo 、 context.lineTo 和 context.closePath 方法。如果未指定上下文，则返回 SVG 路径字符串。

¥Source · Renders triangle i of the Delaunay triangulation to the specified context. The specified context must implement the context.moveTo, context.lineTo and context.closePath methods from the CanvasPathMethods API. If a context is not specified, an SVG path string is returned instead.

delaunay.renderPoints(context, radius) {#delaunay_renderPoints}

源代码 · 将 Delaunay 三角剖分的输入点以指定半径的圆的形式渲染到指定的上下文。如果未指定半径，则默认为 2。指定的上下文必须实现 CanvasPathMethods API 中的 context.moveTo 和 context.arc 方法。如果未指定上下文，则返回 SVG 路径字符串。

¥Source · Renders the input points of the Delaunay triangulation to the specified context as circles with the specified radius. If radius is not specified, it defaults to 2. The specified context must implement the context.moveTo and context.arc methods from the CanvasPathMethods API. If a context is not specified, an SVG path string is returned instead.

delaunay.hullPolygon() {#delaunay_hullPolygon}

源代码 · 返回表示凸包的闭合多边形 [[x0, y0], [x1, y1], …, [x0, y0]]。另请参阅 delaunay.renderHull。

¥Source · Returns the closed polygon [[x0, y0], [x1, y1], …, [x0, y0]] representing the convex hull. See also delaunay.renderHull.

delaunay.trianglePolygons() {#delaunay_trianglePolygons}

源代码 · 按顺序返回 每个三角形的多边形 上的可迭代对象。另请参阅 delaunay.renderTriangle。

¥Source · Returns an iterable over the polygons for each triangle, in order. See also delaunay.renderTriangle.

delaunay.trianglePolygon(i) {#delaunay_trianglePolygon}

源代码 · 返回表示三角形 i 的闭合多边形 [[x0, y0], [x1, y1], [x2, y2], [x0, y0]]。另请参阅 delaunay.renderTriangle。

¥Source · Returns the closed polygon [[x0, y0], [x1, y1], [x2, y2], [x0, y0]] representing the triangle i. See also delaunay.renderTriangle.

delaunay.update() {#delaunay_update}

源代码 · 在点被就地修改后重新计算三角剖分。

¥Source · Recomputes the triangulation after the points have been modified in-place.

delaunay.voronoi(bounds) {#delaunay_voronoi}

源代码 · 返回给定 Delaunay 三角剖分的 Voronoi 图。渲染时，图表将被裁剪到指定的边界 = [xmin, ymin, xmax, ymax]。

¥Source · Returns the Voronoi diagram for the given Delaunay triangulation. When rendering, the diagram will be clipped to the specified bounds = [xmin, ymin, xmax, ymax].

const delaunay = d3.Delaunay.from(points);
const voronoi = delaunay.voronoi([0, 0, 640, 480]);

如果未指定 bounds，则默认为 [0, 0, 960, 500]。即使在不存在三角剖分的退化情况下（即 0、1 或 2 个点以及共线点），也会返回 Voronoi 图。

¥If bounds is not specified, it defaults to [0, 0, 960, 500]. The Voronoi diagram is returned even in degenerate cases where no triangulation exists — namely 0, 1 or 2 points, and collinear points.