notice /**
 * Delaunay triangulation
 */ interface DelaunayI < P > { /**
     * The coordinates of the points as an array [x0, y0, x1, y1, ...].
     * Typically, this is a Float64Array, however you can use any array-like type in the constructor.
     */ points : ArrayLike < number > ; /**
     * The halfedge indices 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.
     */ halfedges : Int32Array ; /**
     * An arbitrary node on the convex hull.
     * The convex hull is represented as a circular doubly-linked list of nodes.
     */ hull : Node ; /**
     * The triangle vertex indices as an Uint32Array [i0, j0, k0, i1, j1, k1, ...].
     * Each contiguous triplet of indices i, j, k forms a counterclockwise triangle.
     * The coordinates of the triangle's points can be found by going through 'points'.
     */ triangles : Uint32Array ; /**
     * 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.
     */ inedges : Int32Array ; /**
     * The outgoing halfedge indexes as a Int32Array [e0, e1, e2, ...].
     * For each point i on the convex hull, outedges[i] is the halfedge index e of the corresponding outgoing halfedge; for other points, the halfedge index is -1.
     */ outedges : Int32Array ; /**
     * 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.
     */ find ( x , y , i ? ) : number ; /**
     * 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.
     */ neighbors ( i ) : IterableIterator < number > ; /**
     * Returns the closed polygon [[x0, y0], [x1, y1], ..., [x0, y0]] representing the convex hull.
     */ hullPolygon ( ) : Polygon ; /**
     * Returns the closed polygon [[x0, y0], [x1, y1], [x2, y2], [x0, y0]] representing the triangle i.
     */ trianglePolygon ( i ) : Triangle ; /**
     * Returns an iterable over the polygons for each triangle, in order.
     */ trianglePolygons ( ) : IterableIterator < Triangle > ; /**
     * Returns the Voronoi diagram for the associated points.
     * When rendering, the diagram will be clipped to the specified bounds = [xmin, ymin, xmax, ymax].
     * If bounds is not specified, it defaults to [0, 0, 960, 500].
     * See To Infinity and Back Again for an interactive explanation of Voronoi cell clipping.
     */ voronoi ( bounds ? ) : Voronoi < P > ; } /**
 * A point represented as an array tuple [x, y].
 */ type Point = number [ ] ; /**
 * A closed polygon [[x0, y0], [x1, y1], [x2, y2], [x0, y0]] representing a triangle.
 */ type Triangle = Point [ ] ; /**
 * A closed polygon [[x0, y0], [x1, y1], ..., [x0, y0]].
 */ type PolygonI = Point [ ] ; /**
 * A rectangular area [x, y, width, height].
 */ export type Bounds = number [ ] ; /**
 * A function to extract a x- or y-coordinate from the specified point.
 */ type GetCoordinate < P , PS > = ( point : P , i : number , points : PS ) => number ; /**
 * A point node on a convex hull (represented as a circular linked list).
 */ interface Node { /**
     * The index of the associated point.
     */ i : number ; /**
     * The x-coordinate of the associated point.
     */ x : number ; /**
     * The y-coordinate of the associated point.
     */ y : number ; /**
     * The index of the (incoming or outgoing?) associated halfedge.
     */ t : number ; /**
     * The previous node on the hull.
     */ prev : Node ; /**
     * The next node on the hull.
     */ next : Node ; /**
     * Whether the node has been removed from the linked list.
     */ removed : boolean ; } /**
 * An interface for the rect() method of the CanvasPathMethods API.
 */ interface RectContext { /**
     * rect() method of the CanvasPathMethods API.
     */ rect ( x , y , width , height ) : void ; } /**
 * An interface for the moveTo() method of the CanvasPathMethods API.
 */ interface MoveContext { /**
     * moveTo() method of the CanvasPathMethods API.
     */ moveTo ( x , y ) : void ; } /**
 * An interface for the lineTo() method of the CanvasPathMethods API.
 */ interface LineContext { /**
     * lineTo() method of the CanvasPathMethods API.
     */ lineTo ( x , y ) : void ; } /**
 * An interface for the arc() method of the CanvasPathMethods API.
 */ interface ArcContext { /**
     * arc() method of the CanvasPathMethods API.
     */ arc ( x , y , radius , startAngle , endAngle , counterclockwise ? ) : void ; } /**
 * An interface for the closePath() method of the CanvasPathMethods API.
 */ interface ClosableContext { /**
     * closePath() method of the CanvasPathMethods API.
     */ closePath ( ) : void ; } /**
 * Voronoi regions
 */ interface VoronoiI < P > { /**
     * The Voronoi diagram’s associated Delaunay triangulation.
     */ delaunay : DelaunayI < P > ; /**
     * The circumcenters of the Delaunay triangles [cx0, cy0, cx1, cy1, ...].
     * Each contiguous pair of coordinates cx, cy is the circumcenter for the corresponding triangle.
     * These circumcenters form the coordinates of the Voronoi cell polygons.
     */ circumcenters : Float64Array ; /**
     * An array [vx0, vy0, wx0, wy0, ...] where each non-zero quadruple describes an open (infinite) cell
     * on the outer hull, giving the directions of two open half-lines.
     */ vectors : Float64Array ; /**
     * The bounds of the viewport [xmin, ymin, xmax, ymax] for rendering the Voronoi diagram.
     * These values only affect the rendering methods (voronoi.render, voronoi.renderBounds, cell.render).
     */ xmin : number ; ymin : number ; xmax : number ; ymax : number ; /**
     * Returns true if the cell with the specified index i contains the specified point ⟨x, y⟩.
     * (This method is not affected by the associated Voronoi diagram’s viewport bounds.)
     */ contains ( i , x , y ) : boolean ; /**
     * Returns the convex, closed polygon [[x0, y0], [x1, y1], ..., [x0, y0]] representing the cell for the specified point i.
     */ cellPolygon ( i ) : PolygonI ; /**
     * Returns an iterable over the polygons for each cell, in order.
     */ cellPolygons ( ) : IterableIterator < PolygonI > ; } const EPSILON = Math . pow ( 2 , - 52 ) ; const EDGE_STACK = new Uint32Array ( 512 ) ; class Delaunator { static from ( points , getX = defaultGetX , getY = defaultGetY ) { const n = points . length ; const coords = new Float64Array ( n * 2 ) ; for ( let i = 0 ; i < n ; i ++ ) { const p = points [ i ] ; coords [ 2 * i ] = getX ( p ) ; coords [ 2 * i + 1 ] = getY ( p ) ; } return new Delaunator ( coords ) ; } constructor ( coords ) { const n = coords . length >> 1 ; if ( n > 0 && typeof coords [ 0 ] !== 'number' ) throw new Error ( 'Expected coords to contain numbers.' ) ; this . coords = coords ; const maxTriangles = Math . max ( 2 * n - 5 , 0 ) ; this . _triangles = new Uint32Array ( maxTriangles * 3 ) ; this . _halfedges = new Int32Array ( maxTriangles * 3 ) ; this . _hashSize = Math . ceil ( Math . sqrt ( n ) ) ; this . _hullPrev = new Uint32Array ( n ) ; this . _hullNext = new Uint32Array ( n ) ; this . _hullTri = new Uint32Array ( n ) ; this . _hullHash = new Int32Array ( this . _hashSize ) . fill ( - 1 ) ; this . _ids = new Uint32Array ( n ) ; this . _dists = new Float64Array ( n ) ; this . update ( ) ; } update ( ) { const { coords , _hullPrev : hullPrev , _hullNext : hullNext , _hullTri : hullTri , _hullHash : hullHash } = this ; const n = coords . length >> 1 ; let minX = Infinity ; let minY = Infinity ; let maxX = - Infinity ; let maxY = - Infinity ; for ( let i = 0 ; i < n ; i ++ ) { const x = coords [ 2 * i ] ; const y = coords [ 2 * i + 1 ] ; if ( x < minX ) minX = x ; if ( y < minY ) minY = y ; if ( x > maxX ) maxX = x ; if ( y > maxY ) maxY = y ; this . _ids [ i ] = i ; } const cx = ( minX + maxX ) / 2 ; const cy = ( minY + maxY ) / 2 ; let minDist = Infinity ; let i0 , i1 , i2 ; for ( let i = 0 ; i < n ; i ++ ) { const d = dist ( cx , cy , coords [ 2 * i ] , coords [ 2 * i + 1 ] ) ; if ( d < minDist ) { i0 = i ; minDist = d ; } } const i0x = coords [ 2 * i0 ] ; const i0y = coords [ 2 * i0 + 1 ] ; minDist = Infinity ; for ( let i = 0 ; i < n ; i ++ ) { if ( i === i0 ) continue ; const d = dist ( i0x , i0y , coords [ 2 * i ] , coords [ 2 * i + 1 ] ) ; if ( d < minDist && d > 0 ) { i1 = i ; minDist = d ; } } let i1x = coords [ 2 * i1 ] ; let i1y = coords [ 2 * i1 + 1 ] ; let minRadius = Infinity ; for ( let i = 0 ; i < n ; i ++ ) { if ( i === i0 || i === i1 ) continue ; const r = circumradius ( i0x , i0y , i1x , i1y , coords [ 2 * i ] , coords [ 2 * i + 1 ] ) ; if ( r < minRadius ) { i2 = i ; minRadius = r ; } } let i2x = coords [ 2 * i2 ] ; let i2y = coords [ 2 * i2 + 1 ] ; if ( minRadius === Infinity ) { for ( let i = 0 ; i < n ; i ++ ) { this . _dists [ i ] = coords [ 2 * i ] - coords [ 0 ] || coords [ 2 * i + 1 ] - coords [ 1 ] ; } quicksort ( this . _ids , this . _dists , 0 , n - 1 ) ; const hull = new Uint32Array ( n ) ; let j = 0 ; for ( let i = 0 , d0 = - Infinity ; i < n ; i ++ ) { const id = this . _ids [ i ] ; if ( this . _dists [ id ] > d0 ) { hull [ j ++ ] = id ; d0 = this . _dists [ id ] ; } } this . hull = hull . subarray ( 0 , j ) ; this . triangles = new Uint32Array ( 0 ) ; this . halfedges = new Uint32Array ( 0 ) ; return ; } if ( orient ( i0x , i0y , i1x , i1y , i2x , i2y ) ) { const i = i1 ; const x = i1x ; const y = i1y ; i1 = i2 ; i1x = i2x ; i1y = i2y ; i2 = i ; i2x = x ; i2y = y ; } const center = circumcenter ( i0x , i0y , i1x , i1y , i2x , i2y ) ; this . _cx = center . x ; this . _cy = center . y ; for ( let i = 0 ; i < n ; i ++ ) { this . _dists [ i ] = dist ( coords [ 2 * i ] , coords [ 2 * i + 1 ] , center . x , center . y ) ; } quicksort ( this . _ids , this . _dists , 0 , n - 1 ) ; this . _hullStart = i0 ; let hullSize = 3 ; hullNext [ i0 ] = hullPrev [ i2 ] = i1 ; hullNext [ i1 ] = hullPrev [ i0 ] = i2 ; hullNext [ i2 ] = hullPrev [ i1 ] = i0 ; hullTri [ i0 ] = 0 ; hullTri [ i1 ] = 1 ; hullTri [ i2 ] = 2 ; hullHash . fill ( - 1 ) ; hullHash [ this . _hashKey ( i0x , i0y ) ] = i0 ; hullHash [ this . _hashKey ( i1x , i1y ) ] = i1 ; hullHash [ this . _hashKey ( i2x , i2y ) ] = i2 ; this . trianglesLen = 0 ; this . _addTriangle ( i0 , i1 , i2 , - 1 , - 1 , - 1 ) ; for ( let k = 0 , xp , yp ; k < this . _ids . length ; k ++ ) { const i = this . _ids [ k ] ; const x = coords [ 2 * i ] ; const y = coords [ 2 * i + 1 ] ; if ( k > 0 && Math . abs ( x - xp ) <= EPSILON && Math . abs ( y - yp ) <= EPSILON ) continue ; xp = x ; yp = y ; if ( i === i0 || i === i1 || i === i2 ) continue ; let start = 0 ; for ( let j = 0 , key = this . _hashKey ( x , y ) ; j < this . _hashSize ; j ++ ) { start = hullHash [ ( key + j ) % this . _hashSize ] ; if ( start !== - 1 && start !== hullNext [ start ] ) break ; } start = hullPrev [ start ] ; let e = start , q ; while ( ( ( q = hullNext [ e ] ) , ! orient ( x , y , coords [ 2 * e ] , coords [ 2 * e + 1 ] , coords [ 2 * q ] , coords [ 2 * q + 1 ] ) ) ) { e = q ; if ( e === start ) { e = - 1 ; break ; } } if ( e === - 1 ) continue ; let t = this . _addTriangle ( e , i , hullNext [ e ] , - 1 , - 1 , hullTri [ e ] ) ; hullTri [ i ] = this . _legalize ( t + 2 ) ; hullTri [ e ] = t ; hullSize ++ ; let n = hullNext [ e ] ; while ( ( ( q = hullNext [ n ] ) , orient ( x , y , coords [ 2 * n ] , coords [ 2 * n + 1 ] , coords [ 2 * q ] , coords [ 2 * q + 1 ] ) ) ) { t = this . _addTriangle ( n , i , q , hullTri [ i ] , - 1 , hullTri [ n ] ) ; hullTri [ i ] = this . _legalize ( t + 2 ) ; hullNext [ n ] = n ; hullSize -- ; n = q ; } if ( e === start ) { while ( ( ( q = hullPrev [ e ] ) , orient ( x , y , coords [ 2 * q ] , coords [ 2 * q + 1 ] , coords [ 2 * e ] , coords [ 2 * e + 1 ] ) ) ) { t = this . _addTriangle ( q , i , e , - 1 , hullTri [ e ] , hullTri [ q ] ) ; this . _legalize ( t + 2 ) ; hullTri [ q ] = t ; hullNext [ e ] = e ; hullSize -- ; e = q ; } } this . _hullStart = hullPrev [ i ] = e ; hullNext [ e ] = hullPrev [ n ] = i ; hullNext [ i ] = n ; hullHash [ this . _hashKey ( x , y ) ] = i ; hullHash [ this . _hashKey ( coords [ 2 * e ] , coords [ 2 * e + 1 ] ) ] = e ; } this . hull = new Uint32Array ( hullSize ) ; for ( let i = 0 , e = this . _hullStart ; i < hullSize ; i ++ ) { this . hull [ i ] = e ; e = hullNext [ e ] ; } this . triangles = this . _triangles . subarray ( 0 , this . trianglesLen ) ; this . halfedges = this . _halfedges . subarray ( 0 , this . trianglesLen ) ; } _hashKey ( x , y ) { return Math . floor ( pseudoAngle ( x - this . _cx , y - this . _cy ) * this . _hashSize ) % this . _hashSize ; } _legalize ( a ) { const { _triangles : triangles , _halfedges : halfedges , coords } = this ; let i = 0 ; let ar = 0 ; while ( true ) { const b = halfedges [ a ] ; const a0 = a - ( a % 3 ) ; ar = a0 + ( ( a + 2 ) % 3 ) ; if ( b === - 1 ) { if ( i === 0 ) break ; a = EDGE_STACK [ -- i ] ; continue ; } const b0 = b - ( b % 3 ) ; const al = a0 + ( ( a + 1 ) % 3 ) ; const bl = b0 + ( ( b + 2 ) % 3 ) ; const p0 = triangles [ ar ] ; const pr = triangles [ a ] ; const pl = triangles [ al ] ; const p1 = triangles [ bl ] ; const illegal = inCircle ( coords [ 2 * p0 ] , coords [ 2 * p0 + 1 ] , coords [ 2 * pr ] , coords [ 2 * pr + 1 ] , coords [ 2 * pl ] , coords [ 2 * pl + 1 ] , coords [ 2 * p1 ] , coords [ 2 * p1 + 1 ] ) ; if ( illegal ) { triangles [ a ] = p1 ; triangles [ b ] = p0 ; const hbl = halfedges [ bl ] ; if ( hbl === - 1 ) { let e = this . _hullStart ; do { if ( this . _hullTri [ e ] === bl ) { this . _hullTri [ e ] = a ; break ; } e = this . _hullPrev [ e ] ; } while ( e !== this . _hullStart ) ; } this . _link ( a , hbl ) ; this . _link ( b , halfedges [ ar ] ) ; this . _link ( ar , bl ) ; const br = b0 + ( ( b + 1 ) % 3 ) ; if ( i < EDGE_STACK . length ) { EDGE_STACK [ i ++ ] = br ; } } else { if ( i === 0 ) break ; a = EDGE_STACK [ -- i ] ; } } return ar ; } _link ( a , b ) { this . _halfedges [ a ] = b ; if ( b !== - 1 ) this . _halfedges [ b ] = a ; } _addTriangle ( i0 , i1 , i2 , a , b , c ) { const t = this . trianglesLen ; this . _triangles [ t ] = i0 ; this . _triangles [ t + 1 ] = i1 ; this . _triangles [ t + 2 ] = i2 ; this . _link ( t , a ) ; this . _link ( t + 1 , b ) ; this . _link ( t + 2 , c ) ; this . trianglesLen += 3 ; return t ; } } function pseudoAngle ( dx , dy ) { const p = dx / ( Math . abs ( dx ) + Math . abs ( dy ) ) ; return ( dy > 0 ? 3 - p : 1 + p ) / 4 ; } function dist ( ax , ay , bx , by ) { const dx = ax - bx ; const dy = ay - by ; return dx * dx + dy * dy ; } function orientIfSure ( px , py , rx , ry , qx , qy ) { const l = ( ry - py ) * ( qx - px ) ; const r = ( rx - px ) * ( qy - py ) ; return Math . abs ( l - r ) >= 3.3306690738754716e-16 * Math . abs ( l + r ) ? l - r : 0 ; } function orient ( rx , ry , qx , qy , px , py ) { const sign = orientIfSure ( px , py , rx , ry , qx , qy ) || orientIfSure ( rx , ry , qx , qy , px , py ) || orientIfSure ( qx , qy , px , py , rx , ry ) ; return sign < 0 ; } function inCircle ( ax , ay , bx , by , cx , cy , px , py ) { const dx = ax - px ; const dy = ay - py ; const ex = bx - px ; const ey = by - py ; const fx = cx - px ; const fy = cy - py ; const ap = dx * dx + dy * dy ; const bp = ex * ex + ey * ey ; const cp = fx * fx + fy * fy ; return dx * ( ey * cp - bp * fy ) - dy * ( ex * cp - bp * fx ) + ap * ( ex * fy - ey * fx ) < 0 ; } function circumradius ( ax , ay , bx , by , cx , cy ) { const dx = bx - ax ; const dy = by - ay ; const ex = cx - ax ; const ey = cy - ay ; const bl = dx * dx + dy * dy ; const cl = ex * ex + ey * ey ; const d = 0.5 / ( dx * ey - dy * ex ) ; const x = ( ey * bl - dy * cl ) * d ; const y = ( dx * cl - ex * bl ) * d ; return x * x + y * y ; } function circumcenter ( ax , ay , bx , by , cx , cy ) { const dx = bx - ax ; const dy = by - ay ; const ex = cx - ax ; const ey = cy - ay ; const bl = dx * dx + dy * dy ; const cl = ex * ex + ey * ey ; const d = 0.5 / ( dx * ey - dy * ex ) ; const x = ax + ( ey * bl - dy * cl ) * d ; const y = ay + ( dx * cl - ex * bl ) * d ; return { x , y } ; } function quicksort ( ids , dists , left , right ) { if ( right - left <= 20 ) { for ( let i = left + 1 ; i <= right ; i ++ ) { const temp = ids [ i ] ; const tempDist = dists [ temp ] ; let j = i - 1 ; while ( j >= left && dists [ ids [ j ] ] > tempDist ) ids [ j + 1 ] = ids [ j -- ] ; ids [ j + 1 ] = temp ; } } else { const median = ( left + right ) >> 1 ; let i = left + 1 ; let j = right ; swap ( ids , median , i ) ; if ( dists [ ids [ left ] ] > dists [ ids [ right ] ] ) swap ( ids , left , right ) ; if ( dists [ ids [ i ] ] > dists [ ids [ right ] ] ) swap ( ids , i , right ) ; if ( dists [ ids [ left ] ] > dists [ ids [ i ] ] ) swap ( ids , left , i ) ; const temp = ids [ i ] ; const tempDist = dists [ temp ] ; while ( true ) { do i ++ ; while ( dists [ ids [ i ] ] < tempDist ) ; do j -- ; while ( dists [ ids [ j ] ] > tempDist ) ; if ( j < i ) break ; swap ( ids , i , j ) ; } ids [ left + 1 ] = ids [ j ] ; ids [ j ] = temp ; if ( right - i + 1 >= j - left ) { quicksort ( ids , dists , i , right ) ; quicksort ( ids , dists , left , j - 1 ) ; } else { quicksort ( ids , dists , left , j - 1 ) ; quicksort ( ids , dists , i , right ) ; } } } function swap ( arr , i , j ) { const tmp = arr [ i ] ; arr [ i ] = arr [ j ] ; arr [ j ] = tmp ; } function defaultGetX ( p ) { return p [ 0 ] ; } function defaultGetY ( p ) { return p [ 1 ] ; } const epsilon = 1e-6 ; class Path { constructor ( ) { this . _x0 = this . _y0 = this . _x1 = this . _y1 = null ; this . _ = '' ; } moveTo ( x , y ) { this . _ += `M${ ( this . _x0 = this . _x1 = + x ) },${ ( this . _y0 = this . _y1 = + y ) }` ; } closePath ( ) { if ( this . _x1 !== null ) { ( this . _x1 = this . _x0 ) , ( this . _y1 = this . _y0 ) ; this . _ += 'Z' ; } } lineTo ( x , y ) { this . _ += `L${ ( this . _x1 = + x ) },${ ( this . _y1 = + y ) }` ; } arc ( x , y , r ) { ( x = + x ) , ( y = + y ) , ( r = + r ) ; const x0 = x + r ; const y0 = y ; if ( r < 0 ) throw new Error ( 'negative radius' ) ; if ( this . _x1 === null ) this . _ += `M${ x0 },${ y0 }` ; else if ( Math . abs ( this . _x1 - x0 ) > epsilon || Math . abs ( this . _y1 - y0 ) > epsilon ) this . _ += 'L' + x0 + ',' + y0 ; if ( ! r ) return ; this . _ += `A${ r },${ r },0,1,1,${ x - r },${ y }A${ r },${ r },0,1,1,${ ( this . _x1 = x0 ) },${ ( this . _y1 = y0 ) }` ; } rect ( x , y , w , h ) { this . _ += `M${ ( this . _x0 = this . _x1 = + x ) },${ ( this . _y0 = this . _y1 = + y ) }h${ + w }v${ + h }h${ - w }Z` ; } value ( ) { return this . _ || null ; } } class Polygon { constructor ( ) { this . _ = [ ] ; } moveTo ( x , y ) { this . _ . push ( [ x , y ] ) ; } closePath ( ) { this . _ . push ( this . _ [ 0 ] . slice ( ) ) ; } lineTo ( x , y ) { this . _ . push ( [ x , y ] ) ; } value ( ) { return this . _ . length ? this . _ : null ; } } export class Voronoi < P > implements VoronoiI < P > { xmin : number ; ymin : number ; xmax : number ; ymax : number ; /**
     * The Voronoi diagram’s associated Delaunay triangulation.
     */ delaunay : DelaunayI < P > ; /**
     * The circumcenters of the Delaunay triangles [cx0, cy0, cx1, cy1, ...].
     * Each contiguous pair of coordinates cx, cy is the circumcenter for the corresponding triangle.
     * These circumcenters form the coordinates of the Voronoi cell polygons.
     */ circumcenters : Float64Array ; /**
     * An array [vx0, vy0, wx0, wy0, ...] where each non-zero quadruple describes an open (infinite) cell
     * on the outer hull, giving the directions of two open half-lines.
     */ vectors : Float64Array ; constructor ( delaunay , [ xmin , ymin , xmax , ymax ] = [ 0 , 0 , 960 , 500 ] ) { if ( ! ( ( xmax = + xmax ) >= ( xmin = + xmin ) ) || ! ( ( ymax = + ymax ) >= ( ymin = + ymin ) ) ) throw new Error ( 'invalid bounds' ) ; this . delaunay = delaunay ; this . _circumcenters = new Float64Array ( delaunay . points . length * 2 ) ; this . vectors = new Float64Array ( delaunay . points . length * 2 ) ; ( this . xmax = xmax ) , ( this . xmin = xmin ) ; ( this . ymax = ymax ) , ( this . ymin = ymin ) ; this . _init ( ) ; } update ( ) { this . delaunay . update ( ) ; this . _init ( ) ; return this ; } _init ( ) { const { delaunay : { points , hull , triangles } , vectors , } = this ; const circumcenters = ( this . circumcenters = this . _circumcenters . subarray ( 0 , ( triangles . length / 3 ) * 2 ) ) ; for ( let i = 0 , j = 0 , n = triangles . length , x , y ; i < n ; i += 3 , j += 2 ) { const t1 = triangles [ i ] * 2 ; const t2 = triangles [ i + 1 ] * 2 ; const t3 = triangles [ i + 2 ] * 2 ; const x1 = points [ t1 ] ; const y1 = points [ t1 + 1 ] ; const x2 = points [ t2 ] ; const y2 = points [ t2 + 1 ] ; const x3 = points [ t3 ] ; const y3 = points [ t3 + 1 ] ; const dx = x2 - x1 ; const dy = y2 - y1 ; const ex = x3 - x1 ; const ey = y3 - y1 ; const bl = dx * dx + dy * dy ; const cl = ex * ex + ey * ey ; const ab = ( dx * ey - dy * ex ) * 2 ; if ( ! ab ) { x = ( x1 + x3 ) / 2 - 1e8 * ey ; y = ( y1 + y3 ) / 2 + 1e8 * ex ; } else if ( Math . abs ( ab ) < 1e-8 ) { x = ( x1 + x3 ) / 2 ; y = ( y1 + y3 ) / 2 ; } else { const d = 1 / ab ; x = x1 + ( ey * bl - dy * cl ) * d ; y = y1 + ( dx * cl - ex * bl ) * d ; } circumcenters [ j ] = x ; circumcenters [ j + 1 ] = y ; } let h = hull [ hull . length - 1 ] ; let p0 , p1 = h * 4 ; let x0 , x1 = points [ 2 * h ] ; let y0 , y1 = points [ 2 * h + 1 ] ; vectors . fill ( 0 ) ; for ( let i = 0 ; i < hull . length ; ++ i ) { h = hull [ i ] ; ( p0 = p1 ) , ( x0 = x1 ) , ( y0 = y1 ) ; ( p1 = h * 4 ) , ( x1 = points [ 2 * h ] ) , ( y1 = points [ 2 * h + 1 ] ) ; vectors [ p0 + 2 ] = vectors [ p1 ] = y0 - y1 ; vectors [ p0 + 3 ] = vectors [ p1 + 1 ] = x1 - x0 ; } } /**
     * Renders the mesh of Voronoi cells to the specified context.
     * The specified context must implement the context.moveTo and context.lineTo methods from the CanvasPathMethods API.
     */ render ( context ) { const buffer = context === null ? ( context = new Path ( ) ) : undefined ; const { delaunay : { halfedges , inedges , hull } , circumcenters , vectors , } = this ; if ( hull . length <= 1 ) return null ; for ( let i = 0 , n = halfedges . length ; i < n ; ++ i ) { const j = halfedges [ i ] ; if ( j < i ) continue ; const ti = Math . floor ( i / 3 ) * 2 ; const tj = Math . floor ( j / 3 ) * 2 ; const xi = circumcenters [ ti ] ; const yi = circumcenters [ ti + 1 ] ; const xj = circumcenters [ tj ] ; const yj = circumcenters [ tj + 1 ] ; this . _renderSegment ( xi , yi , xj , yj , context ) ; } let h0 , h1 = hull [ hull . length - 1 ] ; for ( let i = 0 ; i < hull . length ; ++ i ) { ( h0 = h1 ) , ( h1 = hull [ i ] ) ; const t = Math . floor ( inedges [ h1 ] / 3 ) * 2 ; const x = circumcenters [ t ] ; const y = circumcenters [ t + 1 ] ; const v = h0 * 4 ; const p = this . _project ( x , y , vectors [ v + 2 ] , vectors [ v + 3 ] ) ; if ( p ) this . _renderSegment ( x , y , p [ 0 ] , p [ 1 ] , context ) ; } return buffer && buffer . value ( ) ; } /**
     * Renders the viewport extent to the specified context.
     * The specified context must implement the context.rect method from the CanvasPathMethods API.
     * Equivalent to context.rect(voronoi.xmin, voronoi.ymin, voronoi.xmax - voronoi.xmin, voronoi.ymax - voronoi.ymin).
     */ renderBounds ( context ) { const buffer = context === null ? ( context = new Path ( ) ) : undefined ; context . rect ( this . xmin , this . ymin , this . xmax - this . xmin , this . ymax - this . ymin ) ; return buffer && buffer . value ( ) ; } /**
     * Renders the cell with the specified index i to the specified context.
     * The specified context must implement the context.moveTo, context.lineTo, and context.closePath methods from the CanvasPathMethods API.
     */ renderCell ( i , context ) { const buffer = context == null ? ( context = new Path ( ) ) : undefined ; const points = this . _clip ( i ) ; if ( points === null ) return ; context . moveTo ( points [ 0 ] , points [ 1 ] ) ; let n = points . length ; while ( points [ 0 ] === points [ n - 2 ] && points [ 1 ] === points [ n - 1 ] && n > 1 ) n -= 2 ; for ( let i = 2 ; i < n ; i += 2 ) { if ( points [ i ] !== points [ i - 2 ] || points [ i + 1 ] !== points [ i - 1 ] ) context . lineTo ( points [ i ] , points [ i + 1 ] ) ; } context . closePath ( ) ; return buffer && buffer . value ( ) ; } * cellPolygons ( ) { const { delaunay : { points } , } = this ; for ( let i = 0 , n = points . length / 2 ; i < n ; ++ i ) { const cell = this . cellPolygon ( i ) ; if ( cell ) yield cell ; } } cellPolygon ( i ) { const polygon = new Polygon ( ) ; this . renderCell ( i , polygon ) ; return polygon . value ( ) ; } _renderSegment ( x0 , y0 , x1 , y1 , context ) { let S ; const c0 = this . _regioncode ( x0 , y0 ) ; const c1 = this . _regioncode ( x1 , y1 ) ; if ( c0 === 0 && c1 === 0 ) { context . moveTo ( x0 , y0 ) ; context . lineTo ( x1 , y1 ) ; } else if ( ( S = this . _clipSegment ( x0 , y0 , x1 , y1 , c0 , c1 ) ) ) { context . moveTo ( S [ 0 ] , S [ 1 ] ) ; context . lineTo ( S [ 2 ] , S [ 3 ] ) ; } } contains ( i , x , y ) { if ( ( ( x = + x ) , x !== x ) || ( ( y = + y ) , y !== y ) ) return false ; return this . delaunay . _step ( i , x , y ) === i ; } * neighbors ( i ) { const ci = this . _clip ( i ) ; if ( ci ) for ( const j of this . delaunay . neighbors ( i ) ) { const cj = this . _clip ( j ) ; if ( cj ) loop : for ( let ai = 0 , li = ci . length ; ai < li ; ai += 2 ) { for ( let aj = 0 , lj = cj . length ; aj < lj ; aj += 2 ) { if ( ci [ ai ] == cj [ aj ] && ci [ ai + 1 ] == cj [ aj + 1 ] && ci [ ( ai + 2 ) % li ] == cj [ ( aj + lj - 2 ) % lj ] && ci [ ( ai + 3 ) % li ] == cj [ ( aj + lj - 1 ) % lj ] ) { yield j ; break loop ; } } } } } _cell ( i ) { const { circumcenters , delaunay : { inedges , halfedges , triangles } , } = this ; const e0 = inedges [ i ] ; if ( e0 === - 1 ) return null ; const points = [ ] ; let e = e0 ; do { const t = Math . floor ( e / 3 ) ; points . push ( circumcenters [ t * 2 ] , circumcenters [ t * 2 + 1 ] ) ; e = e % 3 === 2 ? e - 2 : e + 1 ; if ( triangles [ e ] !== i ) break ; e = halfedges [ e ] ; } while ( e !== e0 && e !== - 1 ) ; return points ; } _clip ( i ) { if ( i === 0 && this . delaunay . hull . length === 1 ) { return [ this . xmax , this . ymin , this . xmax , this . ymax , this . xmin , this . ymax , this . xmin , this . ymin ] ; } const points = this . _cell ( i ) ; if ( points === null ) return null ; const { vectors : V } = this ; const v = i * 4 ; return V [ v ] || V [ v + 1 ] ? this . _clipInfinite ( i , points , V [ v ] , V [ v + 1 ] , V [ v + 2 ] , V [ v + 3 ] ) : this . _clipFinite ( i , points ) ; } _clipFinite ( i , points ) { const n = points . length ; let P = null ; let x0 , y0 , x1 = points [ n - 2 ] , y1 = points [ n - 1 ] ; let c0 , c1 = this . _regioncode ( x1 , y1 ) ; let e0 , e1 ; for ( let j = 0 ; j < n ; j += 2 ) { ( x0 = x1 ) , ( y0 = y1 ) , ( x1 = points [ j ] ) , ( y1 = points [ j + 1 ] ) ; ( c0 = c1 ) , ( c1 = this . _regioncode ( x1 , y1 ) ) ; if ( c0 === 0 && c1 === 0 ) { ( e0 = e1 ) , ( e1 = 0 ) ; if ( P ) P . push ( x1 , y1 ) ; else P = [ x1 , y1 ] ; } else { let S , sx0 , sy0 , sx1 , sy1 ; if ( c0 === 0 ) { if ( ( S = this . _clipSegment ( x0 , y0 , x1 , y1 , c0 , c1 ) ) === null ) continue ; [ sx0 , sy0 , sx1 , sy1 ] = S ; } else { if ( ( S = this . _clipSegment ( x1 , y1 , x0 , y0 , c1 , c0 ) ) === null ) continue ; [ sx1 , sy1 , sx0 , sy0 ] = S ; ( e0 = e1 ) , ( e1 = this . _edgecode ( sx0 , sy0 ) ) ; if ( e0 && e1 ) this . _edge ( i , e0 , e1 , P , P . length ) ; if ( P ) P . push ( sx0 , sy0 ) ; else P = [ sx0 , sy0 ] ; } ( e0 = e1 ) , ( e1 = this . _edgecode ( sx1 , sy1 ) ) ; if ( e0 && e1 ) this . _edge ( i , e0 , e1 , P , P . length ) ; if ( P ) P . push ( sx1 , sy1 ) ; else P = [ sx1 , sy1 ] ; } } if ( P ) { ( e0 = e1 ) , ( e1 = this . _edgecode ( P [ 0 ] , P [ 1 ] ) ) ; if ( e0 && e1 ) this . _edge ( i , e0 , e1 , P , P . length ) ; } else if ( this . contains ( i , ( this . xmin + this . xmax ) / 2 , ( this . ymin + this . ymax ) / 2 ) ) { return [ this . xmax , this . ymin , this . xmax , this . ymax , this . xmin , this . ymax , this . xmin , this . ymin ] ; } return P ; } _clipSegment ( x0 , y0 , x1 , y1 , c0 , c1 ) { while ( true ) { if ( c0 === 0 && c1 === 0 ) return [ x0 , y0 , x1 , y1 ] ; if ( c0 & c1 ) return null ; let x , y , c = c0 || c1 ; if ( c & 0b1000 ) ( x = x0 + ( ( x1 - x0 ) * ( this . ymax - y0 ) ) / ( y1 - y0 ) ) , ( y = this . ymax ) ; else if ( c & 0b0100 ) ( x = x0 + ( ( x1 - x0 ) * ( this . ymin - y0 ) ) / ( y1 - y0 ) ) , ( y = this . ymin ) ; else if ( c & 0b0010 ) ( y = y0 + ( ( y1 - y0 ) * ( this . xmax - x0 ) ) / ( x1 - x0 ) ) , ( x = this . xmax ) ; else ( y = y0 + ( ( y1 - y0 ) * ( this . xmin - x0 ) ) / ( x1 - x0 ) ) , ( x = this . xmin ) ; if ( c0 ) ( x0 = x ) , ( y0 = y ) , ( c0 = this . _regioncode ( x0 , y0 ) ) ; else ( x1 = x ) , ( y1 = y ) , ( c1 = this . _regioncode ( x1 , y1 ) ) ; } } _clipInfinite ( i , points , vx0 , vy0 , vxn , vyn ) { let P = Array . from ( points ) , p ; if ( ( p = this . _project ( P [ 0 ] , P [ 1 ] , vx0 , vy0 ) ) ) P . unshift ( p [ 0 ] , p [ 1 ] ) ; if ( ( p = this . _project ( P [ P . length - 2 ] , P [ P . length - 1 ] , vxn , vyn ) ) ) P . push ( p [ 0 ] , p [ 1 ] ) ; if ( ( P = this . _clipFinite ( i , P ) ) ) { for ( let j = 0 , n = P . length , c0 , c1 = this . _edgecode ( P [ n - 2 ] , P [ n - 1 ] ) ; j < n ; j += 2 ) { ( c0 = c1 ) , ( c1 = this . _edgecode ( P [ j ] , P [ j + 1 ] ) ) ; if ( c0 && c1 ) ( j = this . _edge ( i , c0 , c1 , P , j ) ) , ( n = P . length ) ; } } else if ( this . contains ( i , ( this . xmin + this . xmax ) / 2 , ( this . ymin + this . ymax ) / 2 ) ) { P = [ this . xmin , this . ymin , this . xmax , this . ymin , this . xmax , this . ymax , this . xmin , this . ymax ] ; } return P ; } _edge ( i , e0 , e1 , P , j ) { while ( e0 !== e1 ) { let x , y ; switch ( e0 ) { case 0b0101 : e0 = 0b0100 ; continue ; case 0b0100 : ( e0 = 0b0110 ) , ( x = this . xmax ) , ( y = this . ymin ) ; break ; case 0b0110 : e0 = 0b0010 ; continue ; case 0b0010 : ( e0 = 0b1010 ) , ( x = this . xmax ) , ( y = this . ymax ) ; break ; case 0b1010 : e0 = 0b1000 ; continue ; case 0b1000 : ( e0 = 0b1001 ) , ( x = this . xmin ) , ( y = this . ymax ) ; break ; case 0b1001 : e0 = 0b0001 ; continue ; case 0b0001 : ( e0 = 0b0101 ) , ( x = this . xmin ) , ( y = this . ymin ) ; break ; } if ( ( P [ j ] !== x || P [ j + 1 ] !== y ) && this . contains ( i , x , y ) ) { P . splice ( j , 0 , x , y ) , ( j += 2 ) ; } } if ( P . length > 4 ) { for ( let i = 0 ; i < P . length ; i += 2 ) { const j = ( i + 2 ) % P . length , k = ( i + 4 ) % P . length ; if ( ( P [ i ] === P [ j ] && P [ j ] === P [ k ] ) || ( P [ i + 1 ] === P [ j + 1 ] && P [ j + 1 ] === P [ k + 1 ] ) ) P . splice ( j , 2 ) , ( i -= 2 ) ; } } return j ; } _project ( x0 , y0 , vx , vy ) { let t = Infinity , c , x , y ; if ( vy < 0 ) { if ( y0 <= this . ymin ) return null ; if ( ( c = ( this . ymin - y0 ) / vy ) < t ) ( y = this . ymin ) , ( x = x0 + ( t = c ) * vx ) ; } else if ( vy > 0 ) { if ( y0 >= this . ymax ) return null ; if ( ( c = ( this . ymax - y0 ) / vy ) < t ) ( y = this . ymax ) , ( x = x0 + ( t = c ) * vx ) ; } if ( vx > 0 ) { if ( x0 >= this . xmax ) return null ; if ( ( c = ( this . xmax - x0 ) / vx ) < t ) ( x = this . xmax ) , ( y = y0 + ( t = c ) * vy ) ; } else if ( vx < 0 ) { if ( x0 <= this . xmin ) return null ; if ( ( c = ( this . xmin - x0 ) / vx ) < t ) ( x = this . xmin ) , ( y = y0 + ( t = c ) * vy ) ; } return [ x , y ] ; } _edgecode ( x , y ) { return ( ( x === this . xmin ? 0b0001 : x === this . xmax ? 0b0010 : 0b0000 ) | ( y === this . ymin ? 0b0100 : y === this . ymax ? 0b1000 : 0b0000 ) ) ; } _regioncode ( x , y ) { return ( ( x < this . xmin ? 0b0001 : x > this . xmax ? 0b0010 : 0b0000 ) | ( y < this . ymin ? 0b0100 : y > this . ymax ? 0b1000 : 0b0000 ) ) ; } } const tau = 2 * Math . PI ; function pointX ( p ) { return p [ 0 ] ; } function pointY ( p ) { return p [ 1 ] ; } function collinear ( d ) { const { triangles , coords } = d ; for ( let i = 0 ; i < triangles . length ; i += 3 ) { const a = 2 * triangles [ i ] , b = 2 * triangles [ i + 1 ] , c = 2 * triangles [ i + 2 ] , cross = ( coords [ c ] - coords [ a ] ) * ( coords [ b + 1 ] - coords [ a + 1 ] ) - ( coords [ b ] - coords [ a ] ) * ( coords [ c + 1 ] - coords [ a + 1 ] ) ; if ( cross > 1e-10 ) return false ; } return true ; } function jitter ( x , y , r ) { return [ x + Math . sin ( x + y ) * r , y + Math . cos ( x - y ) * r ] ; } export class Delaunay < P > implements DelaunayI < P > { /**
     * The coordinates of the points as an array [x0, y0, x1, y1, ...].
     * Typically, this is a Float64Array, however you can use any array-like type in the constructor.
     */ points : ArrayLike < number > ; /**
     * The halfedge indices 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.
     */ halfedges : Int32Array ; /**
     * An arbitrary node on the convex hull.
     * The convex hull is represented as a circular doubly-linked list of nodes.
     */ hull : Node ; /**
     * The triangle vertex indices as an Uint32Array [i0, j0, k0, i1, j1, k1, ...].
     * Each contiguous triplet of indices i, j, k forms a counterclockwise triangle.
     * The coordinates of the triangle's points can be found by going through 'points'.
     */ triangles : Uint32Array ; /**
     * 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.
     */ inedges : Int32Array ; /**
     * The outgoing halfedge indexes as a Int32Array [e0, e1, e2, ...].
     * For each point i on the convex hull, outedges[i] is the halfedge index e of the corresponding outgoing halfedge; for other points, the halfedge index is -1.
     */ outedges : Int32Array ; /**
     * Returns the Delaunay triangulation for the given array or iterable of points.
     * Otherwise, the getX and getY functions are invoked for each point in order, and must return the respective x- and y-coordinate for each point.
     * If that is specified, the functions getX and getY are invoked with that as this.
     * (See Array.from for reference.)
     */ static from < P > ( points , fx = pointX , fy = pointY , that ? ) { return new Delaunay ( 'length' in points ? flatArray ( points , fx , fy , that ) : Float64Array . from ( flatIterable ( points , fx , fy , that ) ) ) ; } /**
     * Returns the Delaunay triangulation for the given flat array [x0, y0, x1, y1, …] of points.
     */ constructor ( points ) { this . _delaunator = new Delaunator ( points ) ; this . inedges = new Int32Array ( points . length / 2 ) ; this . _hullIndex = new Int32Array ( points . length / 2 ) ; this . points = this . _delaunator . coords ; this . _init ( ) ; } update ( ) { this . _delaunator . update ( ) ; this . _init ( ) ; return this ; } _init ( ) { const d = this . _delaunator , points = this . points ; if ( d . hull && d . hull . length > 2 && collinear ( d ) ) { this . collinear = Int32Array . from ( { length : points . length / 2 } , ( _ , i ) => i ) . sort ( ( i , j ) => points [ 2 * i ] - points [ 2 * j ] || points [ 2 * i + 1 ] - points [ 2 * j + 1 ] ) ; const e = this . collinear [ 0 ] , f = this . collinear [ this . collinear . length - 1 ] , bounds = [ points [ 2 * e ] , points [ 2 * e + 1 ] , points [ 2 * f ] , points [ 2 * f + 1 ] ] , r = 1e-8 * Math . sqrt ( ( bounds [ 3 ] - bounds [ 1 ] ) ** 2 + ( bounds [ 2 ] - bounds [ 0 ] ) ** 2 ) ; for ( let i = 0 , n = points . length / 2 ; i < n ; ++ i ) { const p = jitter ( points [ 2 * i ] , points [ 2 * i + 1 ] , r ) ; points [ 2 * i ] = p [ 0 ] ; points [ 2 * i + 1 ] = p [ 1 ] ; } this . _delaunator = new Delaunator ( points ) ; } else { delete this . collinear ; } const halfedges = ( this . halfedges = this . _delaunator . halfedges ) ; const hull = ( this . hull = this . _delaunator . hull ) ; const triangles = ( this . triangles = this . _delaunator . triangles ) ; const inedges = this . inedges . fill ( - 1 ) ; const hullIndex = this . _hullIndex . fill ( - 1 ) ; for ( let e = 0 , n = halfedges . length ; e < n ; ++ e ) { const p = triangles [ e % 3 === 2 ? e - 2 : e + 1 ] ; if ( halfedges [ e ] === - 1 || inedges [ p ] === - 1 ) inedges [ p ] = e ; } for ( let i = 0 , n = hull . length ; i < n ; ++ i ) { hullIndex [ hull [ i ] ] = i ; } if ( hull . length <= 2 && hull . length > 0 ) { this . triangles = new Int32Array ( 3 ) . fill ( - 1 ) ; this . halfedges = new Int32Array ( 3 ) . fill ( - 1 ) ; this . triangles [ 0 ] = hull [ 0 ] ; this . triangles [ 1 ] = hull [ 1 ] ; this . triangles [ 2 ] = hull [ 1 ] ; inedges [ hull [ 0 ] ] = 1 ; if ( hull . length === 2 ) inedges [ hull [ 1 ] ] = 0 ; } } voronoi ( bounds ) { return new Voronoi ( this , bounds ) ; } * neighbors ( i ) { const { inedges , hull , _hullIndex , halfedges , triangles , collinear } = this ; if ( collinear ) { const l = collinear . indexOf ( i ) ; if ( l > 0 ) yield collinear [ l - 1 ] ; if ( l < collinear . length - 1 ) yield collinear [ l + 1 ] ; return ; } const e0 = inedges [ i ] ; if ( e0 === - 1 ) return ; let e = e0 , p0 = - 1 ; do { yield ( p0 = triangles [ e ] ) ; e = e % 3 === 2 ? e - 2 : e + 1 ; if ( triangles [ e ] !== i ) return ; e = halfedges [ e ] ; if ( e === - 1 ) { const p = hull [ ( _hullIndex [ i ] + 1 ) % hull . length ] ; if ( p !== p0 ) yield p ; return ; } } while ( e !== e0 ) ; } find ( x , y , i = 0 ) { if ( ( ( x = + x ) , x !== x ) || ( ( y = + y ) , y !== y ) ) return - 1 ; const i0 = i ; let c ; while ( ( c = this . _step ( i , x , y ) ) >= 0 && c !== i && c !== i0 ) i = c ; return c ; } _step ( i , x , y ) { const { inedges , hull , _hullIndex , halfedges , triangles , points } = this ; if ( inedges [ i ] === - 1 || ! points . length ) return ( i + 1 ) % ( points . length >> 1 ) ; let c = i ; let dc = ( x - points [ i * 2 ] ) ** 2 + ( y - points [ i * 2 + 1 ] ) ** 2 ; const e0 = inedges [ i ] ; let e = e0 ; do { let t = triangles [ e ] ; const dt = ( x - points [ t * 2 ] ) ** 2 + ( y - points [ t * 2 + 1 ] ) ** 2 ; if ( dt < dc ) ( dc = dt ) , ( c = t ) ; e = e % 3 === 2 ? e - 2 : e + 1 ; if ( triangles [ e ] !== i ) break ; e = halfedges [ e ] ; if ( e === - 1 ) { e = hull [ ( _hullIndex [ i ] + 1 ) % hull . length ] ; if ( e !== t ) { if ( ( x - points [ e * 2 ] ) ** 2 + ( y - points [ e * 2 + 1 ] ) ** 2 < dc ) return e ; } break ; } } while ( e !== e0 ) ; return c ; } /**
     * 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.
     */ render ( context ) { const buffer = context == null ? ( context = new Path ( ) ) : undefined ; const { points , halfedges , triangles } = this ; for ( let i = 0 , n = halfedges . length ; i < n ; ++ i ) { const j = halfedges [ i ] ; if ( j < i ) continue ; const ti = triangles [ i ] * 2 ; const tj = triangles [ j ] * 2 ; context . moveTo ( points [ ti ] , points [ ti + 1 ] ) ; context . lineTo ( points [ tj ] , points [ tj + 1 ] ) ; } this . renderHull ( context ) ; return buffer && buffer . value ( ) ; } /**
     * 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.
     */ renderPoints ( context , r ? ) { const buffer = context == null ? ( context = new Path ( ) ) : undefined ; const { points } = this ; for ( let i = 0 , n = points . length ; i < n ; i += 2 ) { const x = points [ i ] , y = points [ i + 1 ] ; context . moveTo ( x + r , y ) ; context . arc ( x , y , r , 0 , tau ) ; } return buffer && buffer . value ( ) ; } /**
     * 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.
     */ renderHull ( context ) { const buffer = context == null ? ( context = new Path ( ) ) : undefined ; const { hull , points } = this ; const h = hull [ 0 ] * 2 , n = hull . length ; context . moveTo ( points [ h ] , points [ h + 1 ] ) ; for ( let i = 1 ; i < n ; ++ i ) { const h = 2 * hull [ i ] ; context . lineTo ( points [ h ] , points [ h + 1 ] ) ; } context . closePath ( ) ; return buffer && buffer . value ( ) ; } hullPolygon ( ) { const polygon = new Polygon ( ) ; this . renderHull ( polygon ) ; return polygon . value ( ) ; } /**
     * 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.
     */ renderTriangle ( i , context ) { const buffer = context == null ? ( context = new Path ( ) ) : undefined ; const { points , triangles } = this ; const t0 = triangles [ ( i *= 3 ) ] * 2 ; const t1 = triangles [ i + 1 ] * 2 ; const t2 = triangles [ i + 2 ] * 2 ; context . moveTo ( points [ t0 ] , points [ t0 + 1 ] ) ; context . lineTo ( points [ t1 ] , points [ t1 + 1 ] ) ; context . lineTo ( points [ t2 ] , points [ t2 + 1 ] ) ; context . closePath ( ) ; return buffer && buffer . value ( ) ; } * trianglePolygons ( ) { const { triangles } = this ; for ( let i = 0 , n = triangles . length / 3 ; i < n ; ++ i ) { yield this . trianglePolygon ( i ) ; } } trianglePolygon ( i ) { const polygon = new Polygon ( ) ; this . renderTriangle ( i , polygon ) ; return polygon . value ( ) ; } } function flatArray ( points , fx , fy , that ) { const n = points . length ; const array = new Float64Array ( n * 2 ) ; for ( let i = 0 ; i < n ; ++ i ) { const p = points [ i ] ; array [ i * 2 ] = fx . call ( that , p , i , points ) ; array [ i * 2 + 1 ] = fy . call ( that , p , i , points ) ; } return array ; } function * flatIterable ( points , fx , fy , that ) { let i = 0 ; for ( const p of points ) { yield fx . call ( that , p , i , points ) ; yield fy . call ( that , p , i , points ) ; ++ i ; } }