Delaunay 三角剖分
🌐 Delaunay triangulations
德劳内三角剖分是由一组 x 和 y 坐标点形成的三角网。没有任何一点位于任何三角形的外接圆内，这对于某些应用来说是一个很好的几何特性，并且倾向于避免“薄片”三角形。德劳内三角剖分是 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, …] 的 points 的 Delaunay 三角剖分。
const delaunay = new d3.Delaunay(Float64Array.of(0, 0, 0, 1, 1, 0, 1, 1));给定的 points 可以是任何类数组类型，但通常是 Float64Array。
🌐 The given points may be any array-like type, but is typically a Float64Array.
delaunay.points
点的坐标作为数组 [x0, y0, x1, y1, …]。
🌐 The coordinates of the points as an array [x0, y0, x1, y1, …].
delaunay.halfedges
半边索引表示为 Int32Array [j0, j1, …]。对于每个索引 0 ≤ i < halfedges.length，存在一条从三角形顶点 j = halfedges[i] 到三角形顶点 i 的半边。等效地，这意味着三角形 ⌊i / 3⌋ 与三角形 ⌊j / 3⌋ 相邻。如果 j 为负值，则三角形 ⌊i / 3⌋ 是 凸包 上的外三角形。例如，要渲染德劳内三角剖分的内部边：
🌐 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
一个 Int32Array，包含按逆时针顺序形成凸包的点索引。如果这些点共线，则返回按顺序排列的点。
🌐 An Int32Array of point indexes that form the convex hull in counterclockwise order. If the points are collinear, returns them ordered.
🌐 See also delaunay.renderHull.
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();🌐 See also delaunay.renderTriangle.
delaunay.inedges
传入半边索引为 Int32Array [e0, e1, e2, …]。对于每个点 i，inedges[i] 是一个传入半边的索引 e。对于重合点，半边索引为 -1；对于凸包上的点，传入半边位于凸包上；对于其他点，传入半边的选择是任意的。inedges 表可用于遍历 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)
TIP
Delaunay.from 通常比 new Delaunay 慢，因为它需要生成一个新的平面 xy 坐标数组。
来源 · 返回给定数组或可迭代 points 的德劳内三角剖分。如果未指定 fx 和 fy，则假定 points 是由数字组成的两个元素数组的数组：[[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);如果指定了 that，则函数 fx 和 fy 会以 that 作为 this 调用。（参考 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(0, 0) // -1示例 · 来源 · 返回最接近指定点 ⟨x, y⟩ 的输入点的索引。搜索从指定点 i 开始。如果未指定 i，则默认为零。
delaunay.neighbors(i)
delaunay.neighbors(-1) // []来源 · 返回一个可迭代对象，该对象包含指定点 i 的相邻点的索引。如果 i 是重合点，则该可迭代对象为空。
delaunay.render(context)
来源 · 将 Delaunay 三角剖分的边渲染到指定的 context。指定的 context 必须实现 CanvasPathMethods API 中的 context.moveTo 和 context.lineTo 方法。如果未指定 context，则返回一个 SVG 路径字符串。
delaunay.renderHull(context)
来源 · 将 Delaunay 三角剖分的凸包渲染到指定的 context 中。指定的 context 必须实现来自 CanvasPathMethods API 的 context.moveTo 和 context.lineTo 方法。如果未指定 context，则返回一个 SVG 路径字符串。
delaunay.renderTriangle(i, context)
来源 · 将德劳内三角剖分的三角形 i 渲染到指定的 context 中。指定的 context 必须实现 CanvasPathMethods API 中的 context.moveTo、context.lineTo 和 context.closePath 方法。如果未指定 context，则返回一个 SVG 路径字符串。
delaunay.renderPoints(context, radius)
来源 · 将 Delaunay 三角剖分的输入点呈现为指定 context 中的圆，圆的半径为指定的 radius。如果未指定 radius，则默认为 2。指定的 context 必须实现来自 CanvasPathMethods API 的 context.moveTo 和 context.arc 方法。如果未指定 context，则返回一个 SVG 路径字符串。
delaunay.hullPolygon()
来源 · 返回表示凸包的闭合多边形 [[x0, y0], [x1, y1], …, [x0, y0]]。另请参见 delaunay.renderHull。
delaunay.trianglePolygons()
来源 · 返回一个可迭代对象，按顺序包含每个三角形的多边形。另请参见 delaunay.renderTriangle。
delaunay.trianglePolygon(i)
来源 · 返回表示三角形 i 的闭合多边形 [[x0, y0], [x1, y1], [x2, y2], [x0, y0]]。另请参见 delaunay.renderTriangle。
delaunay.update()
来源 · 在点被原地修改后重新计算三角剖分。
delaunay.voronoi(bounds)
来源 · 返回给定 Delaunay 三角剖分的 Voronoi 图。在渲染时，该图将被裁剪到指定的 边界 = [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.