ドローネ三角形分割

ドローネ三角形分割は、 *x* と *y* の点の集合から形成される三角形メッシュです。どの点もどの三角形の外接円の内側にありません。これは特定のアプリケーションにとって優れた幾何学的特性であり、「 sliver 」三角形を回避する傾向があります。ドローネ三角形分割はボロノイ図の双対です。

new Delaunay(points)

ソース ・ 指定された *points* のフラット配列[ *x0* 、 *y0* 、 *x1* 、 *y1* 、…]のドローネ三角形分割を返します。

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

指定された *points* は、任意の配列のような型にすることができますが、通常はFloat64Arrayです。

*delaunay* .points

点の座標を配列[ *x0* 、 *y0* 、 *x1* 、 *y1* 、…]として表します。

*delaunay* .halfedges

Int32Array [ *j0* 、 *j1* 、…]としての半辺インデックス。各インデックス0 ≤ *i* < *halfedges* .lengthについて、三角形頂点 *j* = *halfedges* [ *i* ]から三角形頂点 *i* への半辺があります。同様に、これは三角形⌊ *i* / 3⌋が三角形⌊ *j* / 3⌋に隣接していることを意味します。 *j* が負の場合、三角形⌊ *i* / 3⌋は凸包の外側の三角形です。たとえば、ドローネ三角形分割の内部エッジをレンダリングするには

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も参照してください。

*delaunay* .hull

反時計回りの順序で凸包を形成する点インデックスのInt32Array。点が同一線上にある場合は、順序付けられた状態で返します。

*delaunay* .renderHullも参照してください。

*delaunay* .triangles

Uint32Array [ *i0* 、 *j0* 、 *k0* 、 *i1* 、 *j1* 、 *k1* 、…]としての三角形頂点インデックス。インデックス *i* 、 *j* 、 *k* の各連続するトリプレットは、反時計回りの三角形を形成します。三角形の点の座標は、 *delaunay* .pointsを参照することで見つけることができます。たとえば、三角形 *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も参照してください。

*delaunay* .inedges

着信半辺インデックスをInt32Array [ *e0* 、 *e1* 、 *e2* 、…]として表します。各点 *i* について、 *inedges* [ *i* ]は着信半辺の半辺インデックス *e* です。一致する点の場合、半辺インデックスは-1です。凸包上の点の場合、着信半辺は凸包上にあります。他の点の場合、着信半辺の選択は任意です。 *inedges* テーブルを使用して、ドローネ三角形分割をトラバースできます。 *delaunay* .neighborsも参照してください。

Delaunay.from( *points* 、 *fx* 、 *fy* 、 *that* )

ヒント

Delaunay.fromは、新しい *xy* 座標のフラット配列を具体化する必要があるため、通常new Delaunayよりも遅くなります。

ソース ・ 指定された配列または *points* の反復可能オブジェクトのドローネ三角形分割を返します。 *fx* と *fy* が指定されていない場合、 *points* は数値の2要素配列の配列であると想定されます：[[ *x0* 、 *y0* ]、[ *x1* 、 *y1* ]、…]。

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

それ以外の場合、 *fx* と *fy* は *points* 配列の各要素に対して順番に呼び出される関数であり、各点のそれぞれのx座標とy座標を返す必要があります。

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を参照）

*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* )

ソース ・ ドローネ三角形分割のエッジを指定された *context* にレンダリングします。指定された *context* は、CanvasPathMethods APIの *context* .moveToメソッドと *context* .lineToメソッドを実装する必要があります。 *context* が指定されていない場合、代わりにSVGパス文字列が返されます。

*delaunay* .renderHull( *context* )

ソース ・ ドローネ三角形分割の凸包を指定された *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* )

ソース ・ ドローネ三角形分割の入力点を、指定された *radius* の円として指定された *context* にレンダリングします。 *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)

ソースコード · 与えられたドローネ三角形分割のボロノイ図を返します。レンダリング時に、図は指定された *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 つの点、および同一線上の点）でも返されます。