New Case Study:See how Anthropic automated 95% of dependency reviews with Socket.Learn More →
Socket
Sign inDemoInstall
Socket
Sign inDemoInstall

d3-geo-voronoi

Package Overview
Dependencies
Maintainers
1
Versions
22
Alerts
File Explorer

Advanced tools

License
Socket logo

Install Socket

Detect and block malicious and high-risk dependencies

Install

d3-geo-voronoi - npm Package Compare versions

Comparing version 0.0.2 to 0.0.3

yarn.lock

2896

build/d3-geo-voronoi.js

@@ -0,1 +1,2 @@

// https://github.com/Fil/d3-geo-voronoi Version 0.0.3. Copyright 2017 Philippe Riviere.
(function (global, factory) {

@@ -5,883 +6,922 @@ typeof exports === 'object' && typeof module !== 'undefined' ? factory(exports, require('d3-array'), require('d3-collection'), require('d3-geo'), require('d3-voronoi')) :

(factory((global.d3 = global.d3 || {}),global.d3,global.d3,global.d3,global.d3));
}(this, function (exports,d3Array,d3Collection,d3Geo,d3Voronoi) { 'use strict';
}(this, (function (exports,d3Array,d3Collection,d3Geo,d3Voronoi) { 'use strict';
//
// Copyright (c) 2016, by Loren Petrich
//
// Distributed under the terms of the MIT License
//
// http://lpetrich.org/
//
//
// Copyright (c) 2016, by Loren Petrich
//
// Distributed under the terms of the MIT License
//
// http://lpetrich.org/
//
// Calculates the spherical Delaunay triangulation of a set of points
// These points are entered as an array of arrays of coordinates: 0, 1, 2
// Any extra members are ignored
// Calculates the spherical Delaunay triangulation of a set of points
// These points are entered as an array of arrays of coordinates: 0, 1, 2
// Any extra members are ignored
// FindDelaunayTriangulation(Positions) and
// FindDelaunayTriangulationIndexed(Positions, Indices)
// work from an array of points as specified above,
// the second one working from a set of indices into the array,
// and return an object with these members:
// FindDelaunayTriangulation(Positions) and
// FindDelaunayTriangulationIndexed(Positions, Indices)
// work from an array of points as specified above,
// the second one working from a set of indices into the array,
// and return an object with these members:
// positions -- vectors on a unit sphere
// indices -- of all the vertices
// triangles -- array of TriangleObject
// edges -- array of EdgeObject
// hull -- array of vertex indices -- the convex hull
// vor_positions -- positions of triangles' circumcircle centers (Voronoi vertices)
// vor_edges -- pair of indices in vor_positions (empty one: [-1,-1])
// vor_polygons -- object indexed by vertex index,
// and containing edges (EdgeObject), triangles (TriangleObject),
// and boundary (vertices in vor_positions)
// Open ones have a -1 at each end.
// positions -- vectors on a unit sphere
// indices -- of all the vertices
// triangles -- array of TriangleObject
// edges -- array of EdgeObject
// hull -- array of vertex indices -- the convex hull
// vor_positions -- positions of triangles' circumcircle centers (Voronoi vertices)
// vor_edges -- pair of indices in vor_positions (empty one: [-1,-1])
// vor_polygons -- object indexed by vertex index,
// and containing edges (EdgeObject), triangles (TriangleObject),
// and boundary (vertices in vor_positions)
// Open ones have a -1 at each end.
// Warning: ImproveTriangulation() is mysteriously buggy
// and is effectively disabled for now
// Warning: ImproveTriangulation() is mysteriously buggy
// and is effectively disabled for now
function dotprd(x,y)
{
var sum = 0.0;
for (var ic=0; ic<3; ic++)
sum += x[ic]*y[ic];
return sum;
}
function dotprd(x,y)
{
var sum = 0.0;
for (var ic=0; ic<3; ic++)
sum += x[ic]*y[ic];
return sum;
}
function crsprd(x,y)
function crsprd(x,y)
{
var prod = new Array(3);
for (var ic=0; ic<3; ic++)
{
var prod = new Array(3);
for (var ic=0; ic<3; ic++)
{
var ic1 = ic + 1;
if (ic1 >= 3) ic1 -= 3;
var ic2 = ic + 2;
if (ic2 >= 3) ic2 -= 3;
prod[ic] = x[ic1]*y[ic2] - x[ic2]*y[ic1];
}
return prod;
var ic1 = ic + 1;
if (ic1 >= 3) ic1 -= 3;
var ic2 = ic + 2;
if (ic2 >= 3) ic2 -= 3;
prod[ic] = x[ic1]*y[ic2] - x[ic2]*y[ic1];
}
return prod;
}
function triple_prd(x,y,z)
{
return dotprd(crsprd(x,y),z);
}
function triple_prd(x,y,z)
{
return dotprd(crsprd(x,y),z);
}
// This distance formula has some nice properties:
// distance and not square of distance;
// the square roots give better numerical resolution
// distance of antipode(p) to p' = - (distance of p to p')
// Range: -2 to +2
function ptdist(x,y)
// This distance formula has some nice properties:
// distance and not square of distance;
// the square roots give better numerical resolution
// distance of antipode(p) to p' = - (distance of p to p')
// Range: -2 to +2
function ptdist(x,y)
{
var dst1 = 0.0;
var dst2 = 0.0;
for (var ic=0; ic<3; ic++)
{
var dst1 = 0.0;
var dst2 = 0.0;
for (var ic=0; ic<3; ic++)
{
var diff1 = y[ic] - x[ic];
dst1 += diff1*diff1;
var diff2 = y[ic] + x[ic];
dst2 += diff2*diff2
}
return Math.sqrt(dst1) - Math.sqrt(dst2);
var diff1 = y[ic] - x[ic];
dst1 += diff1*diff1;
var diff2 = y[ic] + x[ic];
dst2 += diff2*diff2;
}
return Math.sqrt(dst1) - Math.sqrt(dst2);
}
function Normalize(vec)
function Normalize(vec)
{
var vecres = new Array(3);
var sum = 0.0, nrmult;
for (var ic=0; ic<3; ic++)
{
var vecres = new Array(3);
var sum = 0.0, nrmult;
for (var ic=0; ic<3; ic++)
{
var val = vec[ic];
sum += val*val;
}
if (sum > 0)
nrmult = 1/Math.sqrt(sum);
else
nrmult = 0;
for (var ic=0; ic<3; ic++)
{
vecres[ic] = nrmult*vec[ic];
}
return vecres;
var val = vec[ic];
sum += val*val;
}
function crsprd_ix(Positions,ix,iy)
if (sum > 0)
nrmult = 1/Math.sqrt(sum);
else
nrmult = 0;
for (var ic=0; ic<3; ic++)
{
return crsprd(Positions[ix],Positions[iy]);
vecres[ic] = nrmult*vec[ic];
}
return vecres;
}
function triple_prd_ix(Positions,ix,iy,iz)
{
return triple_prd(Positions[ix],Positions[iy],Positions[iz]);
}
function crsprd_ix(Positions,ix,iy)
{
return crsprd(Positions[ix],Positions[iy]);
}
function ptdist_ix(Positions,ix,iy)
{
return ptdist(Positions[ix],Positions[iy]);
}
function triple_prd_ix(Positions,ix,iy,iz)
{
return triple_prd(Positions[ix],Positions[iy],Positions[iz]);
}
// Returns a zero 3-vector
function zerovec()
{
var vec = new Array(3);
for (var ic=0; ic<3; ic++)
vec[ic] = 0.0;
return vec;
}
function ptdist_ix(Positions,ix,iy)
{
return ptdist(Positions[ix],Positions[iy]);
}
// Implements copying
function vec_copy(x)
{
var vec = new Array(3);
for (var ic=0; ic<3; ic++)
vec[ic] = x[ic];
return vec;
}
// Returns a zero 3-vector
function zerovec()
{
var vec = new Array(3);
for (var ic=0; ic<3; ic++)
vec[ic] = 0.0;
return vec;
}
// Implements x += y
function vec_add_to(x,y)
{
for (var ic=0; ic<3; ic++)
x[ic] += y[ic];
}
// Implements copying
function vec_copy(x)
{
var vec = new Array(3);
for (var ic=0; ic<3; ic++)
vec[ic] = x[ic];
return vec;
}
// Implements x *= y
function vec_mult_scalar_to(x,y)
{
for (var ic=0; ic<3; ic++)
x[ic] *= y;
}
// Implements x += y
function vec_add_to(x,y)
{
for (var ic=0; ic<3; ic++)
x[ic] += y[ic];
}
// Implements x - y
function vec_difference(x,y)
{
var diff = zerovec();
for (var ic=0; ic<3; ic++)
diff[ic] = x[ic] - y[ic];
return diff;
}
// Implements x *= y
function vec_mult_scalar_to(x,y)
{
for (var ic=0; ic<3; ic++)
x[ic] *= y;
}
// JavaScript's counterpart of "null" / "None":
function IsNull(x)
{
return (typeof(x) == 'undefined');
}
// Implements x - y
function vec_difference(x,y)
{
var diff = zerovec();
for (var ic=0; ic<3; ic++)
diff[ic] = x[ic] - y[ic];
return diff;
}
function TrianglesEqual(tr1, tr2)
{
if (IsNull(tr1)) return false;
if (IsNull(tr2)) return false;
for (var iv=0; iv<3; iv++)
if (tr1.verts[iv] != tr2.verts[iv])
return false;
return true;
}
// JavaScript's counterpart of "null" / "None":
function IsNull(x)
{
return (typeof(x) == 'undefined');
}
function EdgesEqual(ed1, ed2)
{
if (IsNull(ed1)) return false;
if (IsNull(ed2)) return false;
for (var iv=0; iv<2; iv++)
if (ed1.verts[iv] != ed2.verts[iv])
return false;
return true;
}
function TrianglesEqual(tr1, tr2)
{
if (IsNull(tr1)) return false;
if (IsNull(tr2)) return false;
for (var iv=0; iv<3; iv++)
if (tr1.verts[iv] != tr2.verts[iv])
return false;
return true;
}
function max(x,y)
{
return (y > x) ? y : x;
}
function EdgesEqual(ed1, ed2)
{
if (IsNull(ed1)) return false;
if (IsNull(ed2)) return false;
for (var iv=0; iv<2; iv++)
if (ed1.verts[iv] != ed2.verts[iv])
return false;
return true;
}
function TriangleObject(Positions, verts)
{
this.verts = verts;
this.edges = new Array(3);
// Find directions for testing whether a point is inside
this.dirs = new Array(3);
for (var ic=0; ic<3; ic++)
{
var ic1 = ic + 1;
if (ic1 >= 3) ic1 -= 3;
var ic2 = ic + 2;
if (ic2 >= 3) ic2 -= 3;
this.dirs[ic] = crsprd_ix(Positions,verts[ic1],verts[ic2]);
}
// Tetrahedral volume factor
this.vol = triple_prd_ix(Positions,verts[0],verts[1],verts[2]);
// Adjust to get the signs correct for the point-inside test;
// the vertex opposite the edges' vertices ought to give a dot product of 1
for (var ic=0; ic<3; ic++)
vec_mult_scalar_to(this.dirs[ic],1/this.vol);
// Circumcircle test
var ccdir = zerovec();
for (var ic=0; ic<3; ic++)
vec_add_to(ccdir,this.dirs[ic]);
this.ccdir = Normalize(ccdir);
var ccdsq = 0;
for (var ic=0; ic<3; ic++)
ccdsq += ptdist(this.ccdir,Positions[verts[ic]]);
ccdsq /= 3;
this.ccdsq = ccdsq;
}
function max(x,y)
{
return (y > x) ? y : x;
}
// For copying in vertex info from another triangle
TriangleObject.prototype.copy_vert_info = function(src)
function TriangleObject(Positions, verts)
{
this.verts = verts;
this.edges = new Array(3);
// Find directions for testing whether a point is inside
this.dirs = new Array(3);
for (var ic=0; ic<3; ic++)
{
this.verts = src.verts;
this.dirs = src.dirs;
this.vol = src.vol;
this.ccdir = src.ccdir;
this.ccdsq = src.ccdsq;
var ic1 = ic + 1;
if (ic1 >= 3) ic1 -= 3;
var ic2 = ic + 2;
if (ic2 >= 3) ic2 -= 3;
this.dirs[ic] = crsprd_ix(Positions,verts[ic1],verts[ic2]);
}
// Tetrahedral volume factor
this.vol = triple_prd_ix(Positions,verts[0],verts[1],verts[2]);
// Adjust to get the signs correct for the point-inside test;
// the vertex opposite the edges' vertices ought to give a dot product of 1
for (var ic=0; ic<3; ic++)
vec_mult_scalar_to(this.dirs[ic],1/this.vol);
// Circumcircle test
var ccdir = zerovec();
for (var ic=0; ic<3; ic++)
vec_add_to(ccdir,this.dirs[ic]);
this.ccdir = Normalize(ccdir);
var ccdsq = 0;
for (var ic=0; ic<3; ic++)
ccdsq += ptdist(this.ccdir,Positions[verts[ic]]);
ccdsq /= 3;
this.ccdsq = ccdsq;
}
TriangleObject.prototype.IsVertexOrderCorrect = function()
{
return this.vol >= 0;
}
// For copying in vertex info from another triangle
TriangleObject.prototype.copy_vert_info = function(src)
{
this.verts = src.verts;
this.dirs = src.dirs;
this.vol = src.vol;
this.ccdir = src.ccdir;
this.ccdsq = src.ccdsq;
};
TriangleObject.prototype.IsPointInside = function(p)
{
for (var ic=0; ic<3; ic++)
if (dotprd(p,this.dirs[ic]) < 0) return false;
return true;
}
TriangleObject.prototype.IsVertexOrderCorrect = function()
{
return this.vol >= 0;
};
TriangleObject.prototype.IsPointInCircumcircle = function(p)
{
return (ptdist(this.ccdir,p) < this.ccdsq);
}
TriangleObject.prototype.IsPointInside = function(p)
{
for (var ic=0; ic<3; ic++)
if (dotprd(p,this.dirs[ic]) < 0) return false;
return true;
};
TriangleObject.prototype.IsVertex = function(ix)
{
for (var ic=0; ic<3; ic++)
if (ix == this.verts[ic]) return true;
return false;
}
TriangleObject.prototype.IsPointInCircumcircle = function(p)
{
return (ptdist(this.ccdir,p) < this.ccdsq);
};
TriangleObject.prototype.VertexIndexIn = function(ix)
{
for (var ic=0; ic<3; ic++)
if (ix == this.verts[ic]) return ic;
return -1;
}
TriangleObject.prototype.IsVertex = function(ix)
{
for (var ic=0; ic<3; ic++)
if (ix == this.verts[ic]) return true;
return false;
};
TriangleObject.prototype.EdgeIndexIn = function(ed)
{
for (var ic=0; ic<3; ic++)
if (EdgesEqual(this.edges[ic], ed)) return ic;
return -1;
}
TriangleObject.prototype.VertexIndexIn = function(ix)
{
for (var ic=0; ic<3; ic++)
if (ix == this.verts[ic]) return ic;
return -1;
};
function EdgeObject(verts)
{
this.verts = verts;
this.polys = new Array(2);
}
TriangleObject.prototype.EdgeIndexIn = function(ed)
{
for (var ic=0; ic<3; ic++)
if (EdgesEqual(this.edges[ic], ed)) return ic;
return -1;
};
EdgeObject.prototype.IsVertex = function(ix)
{
for (var ic=0; ic<2; ic++)
if (ix == this.verts[ic]) return true;
return false;
}
function EdgeObject(verts)
{
this.verts = verts;
this.polys = new Array(2);
}
EdgeObject.prototype.VertexIndexIn = function(ix)
{
for (var ic=0; ic<2; ic++)
if (ix == this.verts[ic]) return ic;
return -1;
}
EdgeObject.prototype.IsVertex = function(ix)
{
for (var ic=0; ic<2; ic++)
if (ix == this.verts[ic]) return true;
return false;
};
EdgeObject.prototype.PolyIndexIn = function(pl)
{
for (var ic=0; ic<2; ic++)
if (TrianglesEqual(this.polys[ic],pl)) return ic;
return -1;
}
EdgeObject.prototype.VertexIndexIn = function(ix)
{
for (var ic=0; ic<2; ic++)
if (ix == this.verts[ic]) return ic;
return -1;
};
function EdgeCheckObject(Positions,verts)
{
this.verts = verts;
this.pdst = ptdist_ix(Positions,verts[0],verts[1]);
this.direc = Normalize(crsprd_ix(Positions,verts[0],verts[1]));
var midpnt = zerovec();
vec_add_to(midpnt,Positions[verts[0]]);
vec_add_to(midpnt,Positions[verts[1]]);
this.midpnt = Normalize(midpnt);
}
EdgeObject.prototype.PolyIndexIn = function(pl)
{
for (var ic=0; ic<2; ic++)
if (TrianglesEqual(this.polys[ic],pl)) return ic;
return -1;
};
// Check on the possible intersection with another edge-check object
// return a boolean of whether or not it does
EdgeCheckObject.prototype.intersects = function(Positions,other)
function EdgeCheckObject(Positions,verts)
{
this.verts = verts;
this.pdst = ptdist_ix(Positions,verts[0],verts[1]);
this.direc = Normalize(crsprd_ix(Positions,verts[0],verts[1]));
var midpnt = zerovec();
vec_add_to(midpnt,Positions[verts[0]]);
vec_add_to(midpnt,Positions[verts[1]]);
this.midpnt = Normalize(midpnt);
}
// Check on the possible intersection with another edge-check object
// return a boolean of whether or not it does
EdgeCheckObject.prototype.intersects = function(Positions,other)
{
// Assume that sharing a vertex means non-intersecting
for (var ic=0; ic<2; ic++)
for (var ict=0; ict<2; ict++)
if (this.verts[ic] == other.verts[ict]) return false;
// Find intersection point; will test it and its antipode
var itsc = Normalize(crsprd(this.direc, other.direc));
// Find dot product with midpoints to test if the intersection
// is in the near hemispheres of the lines' midpoints.
// If it is in both near hemispheres or both far hemispheres, it's OK
// In both far hemispheres: antipode is in both near hemispheres
var near0 = dotprd(itsc,this.midpnt) > 0;
var near1 = dotprd(itsc,other.midpnt) > 0;
if (near1 != near0) return false;
var pd0 = [];
for (var ic=0; ic<2; ic++)
{
// Assume that sharing a vertex means non-intersecting
for (var ic=0; ic<2; ic++)
for (var ict=0; ict<2; ict++)
if (this.verts[ic] == other.verts[ict]) return false;
// Find intersection point; will test it and its antipode
var itsc = Normalize(crsprd(this.direc, other.direc));
// Find dot product with midpoints to test if the intersection
// is in the near hemispheres of the lines' midpoints.
// If it is in both near hemispheres or both far hemispheres, it's OK
// In both far hemispheres: antipode is in both near hemispheres
var near0 = dotprd(itsc,this.midpnt) > 0;
var near1 = dotprd(itsc,other.midpnt) > 0;
if (near1 != near0) return false;
var pd0 = [];
for (var ic=0; ic<2; ic++)
{
var pd = ptdist(itsc, Positions[this.verts[ic]]);
pd0.push(pd);
}
var pd1 = [];
for (var ic=0; ic<2; ic++)
{
var pd = ptdist(itsc, Positions[other.verts[ic]]);
pd1.push(pd);
}
var mxpd0 = max(pd0[0],pd0[1]);
var mxpd1 = max(pd1[0],pd1[1]);
if ((mxpd0 <= this.pdst) && (mxpd1 <= other.pdst) && near0) return true;
// Handle its antipode; use antipode-related shortcuts
// like reversing the distance value and the hemisphere-presence value
vec_mult_scalar_to(itsc, -1);
near0 = !near0;
for (var ic=0; ic<2; ic++)
{
pd0[ic] = - pd0[ic];
pd1[ic] = - pd1[ic];
}
mxpd0 = max(pd0[0],pd0[1]);
mxpd1 = max(pd1[0],pd1[1]);
if ((mxpd0 <= this.pdst) && (mxpd1 <= other.pdst) && near0) return true;
return false;
var pd = ptdist(itsc, Positions[this.verts[ic]]);
pd0.push(pd);
}
// Adds to an array if it was not already present;
// Must resort to this kludge because JavaScript doesn't have sets
function AddUnique(arr, x)
var pd1 = [];
for (var ic=0; ic<2; ic++)
{
for (var i=0; i<arr.length; i++)
if (x == arr[i]) return;
arr.push(x);
var pd = ptdist(itsc, Positions[other.verts[ic]]);
pd1.push(pd);
}
// Version for edges, since testing equality of objects
// doesn't work that well in JavaScript
function AddUniqueEdge(arr, ed)
var mxpd0 = max(pd0[0],pd0[1]);
var mxpd1 = max(pd1[0],pd1[1]);
if ((mxpd0 <= this.pdst) && (mxpd1 <= other.pdst) && near0) return true;
// Handle its antipode; use antipode-related shortcuts
// like reversing the distance value and the hemisphere-presence value
vec_mult_scalar_to(itsc, -1);
near0 = !near0;
for (var ic=0; ic<2; ic++)
{
for (var i=0; i<arr.length; i++)
if (EdgesEqual(arr[i],ed)) return;
arr.push(ed);
pd0[ic] = - pd0[ic];
pd1[ic] = - pd1[ic];
}
mxpd0 = max(pd0[0],pd0[1]);
mxpd1 = max(pd1[0],pd1[1]);
if ((mxpd0 <= this.pdst) && (mxpd1 <= other.pdst) && near0) return true;
return false;
};
// Find the set intersection
function FindShared(arr1, arr2)
// Adds to an array if it was not already present;
// Must resort to this kludge because JavaScript doesn't have sets
function AddUnique(arr, x)
{
for (var i=0; i<arr.length; i++)
if (x == arr[i]) return;
arr.push(x);
}
// Version for edges, since testing equality of objects
// doesn't work that well in JavaScript
function AddUniqueEdge(arr, ed)
{
for (var i=0; i<arr.length; i++)
if (EdgesEqual(arr[i],ed)) return;
arr.push(ed);
}
// Find the set intersection
function FindShared(arr1, arr2)
{
var resarr = [];
for (var i1=0; i1<arr1.length; i1++)
{
var resarr = [];
for (var i1=0; i1<arr1.length; i1++)
var x1 = arr1[i1];
for (var i2=0; i2<arr2.length; i2++)
{
var x1 = arr1[i1];
for (var i2=0; i2<arr2.length; i2++)
var x2 = arr2[i2];
if (x1 == x2)
{
var x2 = arr2[i2];
if (x1 == x2)
{
resarr.push(x1);
break;
}
resarr.push(x1);
break;
}
}
return resarr;
}
return resarr;
}
// Version for edges
function FindSharedEdges(arr1, arr2)
// Version for edges
function FindSharedEdges(arr1, arr2)
{
var resarr = [];
for (var i1=0; i1<arr1.length; i1++)
{
var resarr = [];
for (var i1=0; i1<arr1.length; i1++)
var x1 = arr1[i1];
for (var i2=0; i2<arr2.length; i2++)
{
var x1 = arr1[i1];
for (var i2=0; i2<arr2.length; i2++)
var x2 = arr2[i2];
if (EdgesEqual(x1,x2))
{
var x2 = arr2[i2];
if (EdgesEqual(x1,x2))
{
resarr.push(x1);
break;
}
resarr.push(x1);
break;
}
}
return resarr;
}
return resarr;
}
// Takes all the members of of arr2 out of arr1
// and ignores the arr2 members not present in arr1
function FindSetDifference(arr1, arr2)
// Takes all the members of of arr2 out of arr1
// and ignores the arr2 members not present in arr1
function FindSetDifference(arr1, arr2)
{
if (arr2.length == 0) return;
var diffarr = [];
for (var i1=0; i1<arr1.length; i1++)
{
if (arr2.length == 0) return;
var diffarr = [];
for (var i1=0; i1<arr1.length; i1++)
var x1 = arr1[i1];
var AddThisOne = true;
for (var i2=0; i2<arr2.length; i2++)
{
var x1 = arr1[i1];
var AddThisOne = true;
for (var i2=0; i2<arr2.length; i2++)
var x2 = arr2[i2];
if (x2 == x1)
{
var x2 = arr2[i2];
if (x2 == x1)
{
AddThisOne = false;
break;
}
AddThisOne = false;
break;
}
if (AddThisOne) diffarr.push(x1);
}
// Clear the array
arr1.splice(0,arr1.length);
for (var i=0; i<diffarr.length; i++)
arr1.push(diffarr[i]);
if (AddThisOne) diffarr.push(x1);
}
// Clear the array
arr1.splice(0,arr1.length);
for (var i=0; i<diffarr.length; i++)
arr1.push(diffarr[i]);
}
// Version for edges
function FindSetDifferenceEdges(arr1, arr2)
// Version for edges
function FindSetDifferenceEdges(arr1, arr2)
{
if (arr2.length == 0) return;
var diffarr = [];
for (var i1=0; i1<arr1.length; i1++)
{
if (arr2.length == 0) return;
var diffarr = [];
for (var i1=0; i1<arr1.length; i1++)
var x1 = arr1[i1];
var AddThisOne = true;
for (var i2=0; i2<arr2.length; i2++)
{
var x1 = arr1[i1];
var AddThisOne = true;
for (var i2=0; i2<arr2.length; i2++)
var x2 = arr2[i2];
if (EdgesEqual(x1,x2))
{
var x2 = arr2[i2];
if (EdgesEqual(x1,x2))
{
AddThisOne = false;
break;
}
AddThisOne = false;
break;
}
if (AddThisOne) diffarr.push(x1);
}
// Clear the array
arr1.splice(0,arr1.length);
for (var i=0; i<diffarr.length; i++)
arr1.push(diffarr[i]);
if (AddThisOne) diffarr.push(x1);
}
// Clear the array
arr1.splice(0,arr1.length);
for (var i=0; i<diffarr.length; i++)
arr1.push(diffarr[i]);
}
// Specified by index ix; returns whether it was possible to do so
function AddPointInside(TriSet, ix)
// Specified by index ix; returns whether it was possible to do so
function AddPointInside(TriSet, ix)
{
var Positions = TriSet.positions;
var p = Positions[ix];
var NumTris = TriSet.triangles.length;
for (var j=0; j<NumTris; j++)
{
var Positions = TriSet.positions;
var p = Positions[ix];
var NumTris = TriSet.triangles.length;
for (var j=0; j<NumTris; j++)
var tri = TriSet.triangles[j];
if (tri.IsPointInside(p))
{
var tri = TriSet.triangles[j];
if (tri.IsPointInside(p))
// Create three new triangles and their edges
var eds = tri.edges;
var trixs = [];
for (var ic=0; ic<3; ic++)
trixs.push(eds[ic].PolyIndexIn(tri));
var newtris = Array(3);
var neweds = Array(3);
for (var ic=0; ic<3; ic++)
{
// Create three new triangles and their edges
var eds = tri.edges;
var trixs = [];
for (var ic=0; ic<3; ic++)
trixs.push(eds[ic].PolyIndexIn(tri));
var newtris = Array(3);
var neweds = Array(3);
for (var ic=0; ic<3; ic++)
{
var ic1 = ic + 1;
if (ic1 >= 3) ic1 -= 3;
newtris[ic] = new TriangleObject(Positions,[tri.verts[ic],tri.verts[ic1],ix]);
neweds[ic] = new EdgeObject([tri.verts[ic],ix]);
}
// Connect those triangles and edges
for (var ic=0; ic<3; ic++)
{
var ic1 = ic + 1;
if (ic1 >= 3) ic1 -= 3;
newtris[ic].edges[0] = neweds[ic1];
newtris[ic].edges[1] = neweds[ic];
neweds[ic].polys[0] = newtris[ic];
neweds[ic1].polys[1] = newtris[ic];
}
var ic1 = ic + 1;
if (ic1 >= 3) ic1 -= 3;
newtris[ic] = new TriangleObject(Positions,[tri.verts[ic],tri.verts[ic1],ix]);
neweds[ic] = new EdgeObject([tri.verts[ic],ix]);
}
// Find which external edges go with which triangles
for (var ic=0; ic<3; ic++)
// Connect those triangles and edges
for (var ic=0; ic<3; ic++)
{
var ic1 = ic + 1;
if (ic1 >= 3) ic1 -= 3;
newtris[ic].edges[0] = neweds[ic1];
newtris[ic].edges[1] = neweds[ic];
neweds[ic].polys[0] = newtris[ic];
neweds[ic1].polys[1] = newtris[ic];
}
// Find which external edges go with which triangles
for (var ic=0; ic<3; ic++)
{
var ed = eds[ic];
var trix = trixs[ic];
for (var ict=0; ict<3; ict++)
{
var ed = eds[ic];
var trix = trixs[ic];
for (var ict=0; ict<3; ict++)
var newtri = newtris[ict];
var numverts = 0;
for (var iv=0; iv<2; iv++)
{
var newtri = newtris[ict];
var numverts = 0;
for (var iv=0; iv<2; iv++)
if (newtri.IsVertex(ed.verts[iv]))
numverts++;
if (numverts == 2)
{
if (newtri.IsVertex(ed.verts[iv]))
numverts++;
if (numverts == 2)
{
ed.polys[trix] = newtri;
newtri.edges[2] = ed;
break;
}
ed.polys[trix] = newtri;
newtri.edges[2] = ed;
break;
}
}
}
// Insert those triangles and edges into the lists
TriSet.triangles[j] = newtris[0];
for (var ic=1; ic<3; ic++)
TriSet.triangles.push(newtris[ic]);
for (var ic=0; ic<3; ic++)
TriSet.edges.push(neweds[ic]);
// All done; indicate that the point was added
return true;
}
// Insert those triangles and edges into the lists
TriSet.triangles[j] = newtris[0];
for (var ic=1; ic<3; ic++)
TriSet.triangles.push(newtris[ic]);
for (var ic=0; ic<3; ic++)
TriSet.edges.push(neweds[ic]);
// All done; indicate that the point was added
return true;
}
// The point was inside no triangle, and thus was not added
return false;
}
// The point was inside no triangle, and thus was not added
return false;
}
function ImproveTriangulation(TriSet)
function ImproveTriangulation(TriSet)
{
var Positions = TriSet.positions;
var quad_verts = new Array(4);
for (var itr=0; itr<100; itr++)
{
var Positions = TriSet.positions;
var quad_verts = new Array(4);
for (var itr=0; itr<100; itr++)
var numflips = 0;
for (var i=0; i<TriSet.edges.length; i++)
{
var numflips = 0;
for (var i=0; i<TriSet.edges.length; i++)
var edge = TriSet.edges[i];
var tris = edge.polys;
// Skip over external edges
if (IsNull(tris[0])) continue;
if (IsNull(tris[1])) continue;
// Find the containing quadrangle's vertices
for (var ic=0; ic<3; ic++)
{
var edge = TriSet.edges[i];
var tris = edge.polys;
// Skip over external edges
if (IsNull(tris[0])) continue;
if (IsNull(tris[1])) continue;
// Find the containing quadrangle's vertices
for (var ic=0; ic<3; ic++)
var ix = tris[0].verts[ic];
if (!edge.IsVertex(ix)) break;
}
var ic1 = ic + 1;
if (ic1 >= 3) ic1 -= 3;
var ic2 = ic + 2;
if (ic2 >= 3) ic2 -= 3;
quad_verts[0] = ix;
quad_verts[1] = tris[0].verts[ic1];
quad_verts[3] = tris[0].verts[ic2];
for (var ic=0; ic<3; ic++)
{
var ix = tris[1].verts[ic];
if (!edge.IsVertex(ix)) break;
}
quad_verts[2] = ix;
// Are the non-edge points in the other triangles' circumcircles?
var incc0 = tris[0].IsPointInCircumcircle(Positions[quad_verts[2]]);
var incc1 = tris[1].IsPointInCircumcircle(Positions[quad_verts[0]]);
if ((!incc0) && (!incc1)) continue;
// Are the would-be triangles properly oriented?
var newtri0 = new TriangleObject(Positions, [quad_verts[0],quad_verts[1],quad_verts[2]]);
if (!newtri0.IsVertexOrderCorrect()) continue;
var newtri1 = new TriangleObject(Positions, [quad_verts[0],quad_verts[2],quad_verts[3]]);
if (!newtri1.IsVertexOrderCorrect()) continue;
// If so, then flip
numflips++;
// Adjust the edge and triangle memberships:
// 0-3 goes from 0 to 1, 1-2 goes from 1 to 0
for (var ic=0; ic<3; ic++)
{
var ed = tris[0].edges[ic];
if (EdgesEqual(ed,edge)) continue;
else if (ed.IsVertex(quad_verts[3]))
{
var ix = tris[0].verts[ic];
if (!edge.IsVertex(ix)) break;
var ed03 = ed;
var edix03 = ic;
break;
}
var ic1 = ic + 1;
if (ic1 >= 3) ic1 -= 3;
var ic2 = ic + 2;
if (ic2 >= 3) ic2 -= 3;
quad_verts[0] = ix;
quad_verts[1] = tris[0].verts[ic1];
quad_verts[3] = tris[0].verts[ic2];
for (var ic=0; ic<3; ic++)
}
for (var ic=0; ic<3; ic++)
{
var ed = tris[1].edges[ic];
if (EdgesEqual(ed,edge)) continue;
else if (ed.IsVertex(quad_verts[1]))
{
var ix = tris[1].verts[ic];
if (!edge.IsVertex(ix)) break;
var ed12 = ed;
var edix12 = ic;
break;
}
quad_verts[2] = ix;
// Are the non-edge points in the other triangles' circumcircles?
var incc0 = tris[0].IsPointInCircumcircle(Positions[quad_verts[2]]);
var incc1 = tris[1].IsPointInCircumcircle(Positions[quad_verts[0]]);
if ((!incc0) && (!incc1)) continue;
// Are the would-be triangles properly oriented?
var newtri0 = new TriangleObject(Positions, [quad_verts[0],quad_verts[1],quad_verts[2]]);
if (!newtri0.IsVertexOrderCorrect()) continue;
var newtri1 = new TriangleObject(Positions, [quad_verts[0],quad_verts[2],quad_verts[3]]);
if (!newtri1.IsVertexOrderCorrect()) continue;
// If so, then flip
numflips++;
// Adjust the edge and triangle memberships:
// 0-3 goes from 0 to 1, 1-2 goes from 1 to 0
for (var ic=0; ic<3; ic++)
{
var ed = tris[0].edges[ic];
if (EdgesEqual(ed,edge)) continue;
else if (ed.IsVertex(quad_verts[3]))
{
var ed03 = ed;
var edix03 = ic;
break;
}
}
for (var ic=0; ic<3; ic++)
{
var ed = tris[1].edges[ic];
if (EdgesEqual(ed,edge)) continue;
else if (ed.IsVertex(quad_verts[1]))
{
var ed12 = ed;
var edix12 = ic;
break;
}
}
var trix0 = ed03.PolyIndexIn(tris[0]);
var trix1 = ed12.PolyIndexIn(tris[1]);
ed03.polys[trix0] = tris[1];
ed12.polys[trix1] = tris[0];
tris[0].edges[edix03] = ed12;
tris[1].edges[edix12] = ed03;
// Add the vertices
tris[0].copy_vert_info(newtri0);
tris[1].copy_vert_info(newtri1);
edge.verts = [quad_verts[0], quad_verts[2]];
}
if (numflips == 0) break;
var trix0 = ed03.PolyIndexIn(tris[0]);
var trix1 = ed12.PolyIndexIn(tris[1]);
ed03.polys[trix0] = tris[1];
ed12.polys[trix1] = tris[0];
tris[0].edges[edix03] = ed12;
tris[1].edges[edix12] = ed03;
// Add the vertices
tris[0].copy_vert_info(newtri0);
tris[1].copy_vert_info(newtri1);
edge.verts = [quad_verts[0], quad_verts[2]];
}
if (numflips == 0) break;
}
}
function FindConvexHull(TriSet)
function FindConvexHull(TriSet)
{
// var Positions = TriSet.positions;
// Find boundary loop -- use as convex hull
var NextVertex = new Object;
var VtxStart = -1;
for (var i=0; i<TriSet.edges.length; i++)
{
// var Positions = TriSet.positions;
var edge = TriSet.edges[i];
// Find boundary loop -- use as convex hull
var NextVertex = new Object;
var VtxStart = -1;
for (var i=0; i<TriSet.edges.length; i++)
// Find a boundary one -- look for the triangle that it contains
if (IsNull(edge.polys[0]))
{
var edge = TriSet.edges[i];
// Find a boundary one -- look for the triangle that it contains
if (IsNull(edge.polys[0]))
{
if (IsNull(edge.polys[1]))
continue;
else
var tri = edge.polys[1];
}
if (IsNull(edge.polys[1]))
continue;
else
{
if (IsNull(edge.polys[1]))
var tri = edge.polys[0];
else
continue;
}
// Ensure that the hull is in the same direction as the triangles
var ix0 = edge.verts[0];
var ix1 = edge.verts[1];
var posdiff = tri.VertexIndexIn(ix1) - tri.VertexIndexIn(ix0);
if (posdiff < 0) posdiff += 3;
if (posdiff != 1)
{
var ixs = ix0;
ix0 = ix1;
ix1 = ixs;
}
NextVertex[ix0] = ix1;
VtxStart = ix0;
var tri = edge.polys[1];
}
else
{
if (IsNull(edge.polys[1]))
var tri = edge.polys[0];
else
continue;
}
if (VtxStart >= 0)
// Ensure that the hull is in the same direction as the triangles
var ix0 = edge.verts[0];
var ix1 = edge.verts[1];
var posdiff = tri.VertexIndexIn(ix1) - tri.VertexIndexIn(ix0);
if (posdiff < 0) posdiff += 3;
if (posdiff != 1)
{
var ix = VtxStart;
var hull = [ix];
while(true)
{
var ixnext = NextVertex[ix];
if (ixnext == VtxStart) break;
hull.push(ixnext);
ix = ixnext;
}
TriSet.hull = hull;
var ixs = ix0;
ix0 = ix1;
ix1 = ixs;
}
NextVertex[ix0] = ix1;
VtxStart = ix0;
}
if (VtxStart >= 0)
{
var ix = VtxStart;
var hull = [ix];
while(true)
{
var ixnext = NextVertex[ix];
if (ixnext == VtxStart) break;
hull.push(ixnext);
ix = ixnext;
}
TriSet.hull = hull;
}
}
// Finds the dual of the Delaunay triangulation
// Won't bother to do the sort of connectivity
// that was necessary for the Delaunay triangulation
function FindVoronoiDiagram(TriSet)
// Finds the dual of the Delaunay triangulation
// Won't bother to do the sort of connectivity
// that was necessary for the Delaunay triangulation
function FindVoronoiDiagram(TriSet)
{
// Special cases: 3 or fewer points
if (TriSet.triangles.length == 1)
{
// Special cases: 3 or fewer points
if (TriSet.triangles.length == 1)
// A single triangle
if (TriSet.hull.length == 3)
{
// A single triangle
if (TriSet.hull.length == 3)
var tri = TriSet.triangles[0];
TriSet.vor_positions.push(tri.ccdir);
for (var k=0; k<3; k++)
{
var tri = TriSet.triangles[0];
TriSet.vor_positions.push(tri.ccdir);
for (var k=0; k<3; k++)
var kx = k + 1;
if (kx >= 3) kx = 0;
var ky = k - 1;
if (ky < 0) ky = 2;
var v1 = TriSet.positions[TriSet.hull[k]];
var v2 = TriSet.positions[TriSet.hull[kx]];
var posdiff = vec_difference(v2,v1);
TriSet.vor_positions.push(Normalize(crsprd(posdiff,tri.ccdir)));
TriSet.vor_edges.push([0, k+1, 4]);
var ix = TriSet.hull[k];
TriSet.vor_polygons[ix] = new Object;
var vor_poly = TriSet.vor_polygons[ix];
var iy = TriSet.hull[ky];
for (var l=0; l<3; l++)
{
var kx = k + 1;
if (kx >= 3) kx = 0;
var ky = k - 1;
if (ky < 0) ky = 2;
var v1 = TriSet.positions[TriSet.hull[k]];
var v2 = TriSet.positions[TriSet.hull[kx]];
var posdiff = vec_difference(v2,v1);
TriSet.vor_positions.push(Normalize(crsprd(posdiff,tri.ccdir)));
TriSet.vor_edges.push([0, k+1, 4]);
var ix = TriSet.hull[k];
TriSet.vor_polygons[ix] = new Object;
var vor_poly = TriSet.vor_polygons[ix];
var iy = TriSet.hull[ky];
for (var l=0; l<3; l++)
{
var edge = TriSet.edges[l];
var shrd = FindShared([iy,ix],edge.verts);
if (shrd.length == 2) break;
}
vor_poly.edges = [edge];
vor_poly.triangles = [tri];
vor_poly.boundary = [0, ky+1, 4, k+1];
var edge = TriSet.edges[l];
var shrd = FindShared([iy,ix],edge.verts);
if (shrd.length == 2) break;
}
var ept = vec_copy(tri.ccdir);
vec_mult_scalar_to(ept,-1);
TriSet.vor_positions.push(ept);
vor_poly.edges = [edge];
vor_poly.triangles = [tri];
vor_poly.boundary = [0, ky+1, 4, k+1];
}
return;
var ept = vec_copy(tri.ccdir);
vec_mult_scalar_to(ept,-1);
TriSet.vor_positions.push(ept);
}
else if (TriSet.triangles.length == 0)
return;
}
else if (TriSet.triangles.length == 0)
{
// A biangle
if (TriSet.hull.length == 2)
{
// A biangle
if (TriSet.hull.length == 2)
var v0 = TriSet.positions[TriSet.hull[0]];
var v1 = TriSet.positions[TriSet.hull[1]];
var vt0 = zerovec();
vec_add_to(vt0,v0);
vec_add_to(vt0,v1);
vt0 = Normalize(vt0);
TriSet.vor_positions.push(vt0);
var vt1 = Normalize(crsprd(v0,v1));
TriSet.vor_positions.push(vt1);
var vt2 = vec_copy(vt0);
vec_mult_scalar_to(vt2,-1);
TriSet.vor_positions.push(vt2);
var vt3 = vec_copy(vt1);
vec_mult_scalar_to(vt3,-1);
TriSet.vor_positions.push(vt3);
TriSet.vor_edges.push([0, 1, 2, 3, 0]);
edge = TriSet.edges[0];
for (var k=0; k<2; k++)
{
var v0 = TriSet.positions[TriSet.hull[0]];
var v1 = TriSet.positions[TriSet.hull[1]];
var vt0 = zerovec();
vec_add_to(vt0,v0);
vec_add_to(vt0,v1);
vt0 = Normalize(vt0);
TriSet.vor_positions.push(vt0);
var vt1 = Normalize(crsprd(v0,v1));
TriSet.vor_positions.push(vt1);
var vt2 = vec_copy(vt0);
vec_mult_scalar_to(vt2,-1);
TriSet.vor_positions.push(vt2);
var vt3 = vec_copy(vt1);
vec_mult_scalar_to(vt3,-1);
TriSet.vor_positions.push(vt3);
TriSet.vor_edges.push([0, 1, 2, 3, 0]);
edge = TriSet.edges[0];
for (var k=0; k<2; k++)
{
var ix = TriSet.hull[k];
TriSet.vor_polygons[ix] = new Object;
var vor_poly = TriSet.vor_polygons[ix];
vor_poly.edges = [edge];
vor_poly.triangles = [0];
if (k == 0)
vor_poly.boundary = [0, 1, 2, 3];
else if (k == 1)
vor_poly.boundary = [0, 3, 2, 1];
}
var ix = TriSet.hull[k];
TriSet.vor_polygons[ix] = new Object;
var vor_poly = TriSet.vor_polygons[ix];
vor_poly.edges = [edge];
vor_poly.triangles = [0];
if (k == 0)
vor_poly.boundary = [0, 1, 2, 3];
else if (k == 1)
vor_poly.boundary = [0, 3, 2, 1];
}
return;
}
// Create the array of Voronoi-vertex positions:
// Add indices to the triangle objects for convenience
for (var i=0; i<TriSet.triangles.length; i++)
return;
}
// Create the array of Voronoi-vertex positions:
// Add indices to the triangle objects for convenience
for (var i=0; i<TriSet.triangles.length; i++)
{
var tri = TriSet.triangles[i];
tri.index = i;
TriSet.vor_positions.push(tri.ccdir);
}
// Voronoi edges: a cinch
// Voronoi edges parallel original edges
for (var i=0; i<TriSet.edges.length; i++)
{
var edge = TriSet.edges[i];
if (!IsNull(edge.polys[0]) && !IsNull(edge.polys[1]))
{
var tri = TriSet.triangles[i];
tri.index = i;
TriSet.vor_positions.push(tri.ccdir);
var vor_edge = [edge.polys[0].index, edge.polys[1].index];
TriSet.vor_edges.push(vor_edge);
}
}
// Voronoi polygons: -1 at ends means an open one
// First, collect the edges and triangles at each vertex
// Put them into vor_polygons, because each one
// is for each original vertex
for (var i=0; i<TriSet.indices.length; i++)
{
var ix = TriSet.indices[i];
TriSet.vor_polygons[ix] = new Object;
// Voronoi edges: a cinch
// Voronoi edges parallel original edges
for (var i=0; i<TriSet.edges.length; i++)
{
var edge = TriSet.edges[i];
if (!IsNull(edge.polys[0]) && !IsNull(edge.polys[1]))
{
var vor_edge = [edge.polys[0].index, edge.polys[1].index];
TriSet.vor_edges.push(vor_edge);
}
}
var vor_poly = TriSet.vor_polygons[ix];
vor_poly.edges = [];
vor_poly.triangles = [];
vor_poly.boundary = [];
}
for (var i=0; i<TriSet.edges.length; i++)
{
var edge = TriSet.edges[i];
for (var ic=0; ic<2; ic++)
TriSet.vor_polygons[edge.verts[ic]].edges.push(edge);
}
for (var i=0; i<TriSet.triangles.length; i++)
{
var tri = TriSet.triangles[i];
for (var ic=0; ic<3; ic++)
TriSet.vor_polygons[tri.verts[ic]].triangles.push(tri);
}
for (var i=0; i<TriSet.indices.length; i++)
{
var ix = TriSet.indices[i];
var vor_poly = TriSet.vor_polygons[ix];
// Voronoi polygons: -1 at ends means an open one
// First triangle
var init_tri = vor_poly.triangles[0];
var tri = init_tri;
vor_poly.boundary.push(tri.index);
// First, collect the edges and triangles at each vertex
// Put them into vor_polygons, because each one
// is for each original vertex
for (var i=0; i<TriSet.indices.length; i++)
// First edge
for (var ic=0; ic<3; ic++)
{
var ix = TriSet.indices[i];
TriSet.vor_polygons[ix] = new Object;
var vor_poly = TriSet.vor_polygons[ix];
vor_poly.edges = [];
vor_poly.triangles = [];
vor_poly.boundary = [];
var edge = tri.edges[ic];
if (edge.IsVertex(ix))
break;
}
var init_edge = edge;
for (var i=0; i<TriSet.edges.length; i++)
// The next triangle and edge
var IsInside = false;
while(true)
{
var edge = TriSet.edges[i];
for (var ic=0; ic<2; ic++)
TriSet.vor_polygons[edge.verts[ic]].edges.push(edge);
}
for (var i=0; i<TriSet.triangles.length; i++)
{
var tri = TriSet.triangles[i];
var iv = edge.PolyIndexIn(tri);
tri = edge.polys[1-iv];
if (IsNull(tri)) break;
if (TrianglesEqual(tri,init_tri))
{
IsInside = true;
break;
}
vor_poly.boundary.push(tri.index);
for (var ic=0; ic<3; ic++)
TriSet.vor_polygons[tri.verts[ic]].triangles.push(tri);
{
var next_edge = tri.edges[ic];
if (EdgesEqual(next_edge,edge)) continue;
if (next_edge.IsVertex(ix))
{
edge = next_edge;
break;
}
}
}
for (var i=0; i<TriSet.indices.length; i++)
if (!IsInside)
{
var ix = TriSet.indices[i];
var vor_poly = TriSet.vor_polygons[ix];
vor_poly.boundary.reverse();
tri = init_tri;
// First triangle
var init_tri = vor_poly.triangles[0];
var tri = init_tri;
vor_poly.boundary.push(tri.index);
// First edge
// First edge the other way
for (var ic=0; ic<3; ic++)
{
var edge = tri.edges[ic];
edge = tri.edges[ic];
if (EdgesEqual(edge,init_edge)) continue;
if (edge.IsVertex(ix))
break;
}
var init_edge = edge;
// The next triangle and edge
var IsInside = false;
while(true)

@@ -892,7 +932,2 @@ {

if (IsNull(tri)) break;
if (TrianglesEqual(tri,init_tri))
{
IsInside = true;
break;
}

@@ -912,837 +947,810 @@ vor_poly.boundary.push(tri.index);

}
if (!IsInside)
}
// Add -1 on ends for open polygon:
if (!IsInside)
{
vor_poly.boundary.reverse();
vor_poly.boundary.push(-1);
vor_poly.boundary.reverse();
vor_poly.boundary.push(-1);
}
}
// Handle the area outside of the convex hull
if (TriSet.hull.length >= 3)
{
// Set up the initial boundary lines
// The boundary lines contain:
// Index of Voronoi vertex / triangle center / intersection (in VorPos)
// Indices of original vertices on each side of the line
var VorBdLns = new Array();
var Positions = TriSet.positions;
var hlen = TriSet.hull.length;
for (var ic=0; ic<hlen; ic++)
{
var ix = TriSet.hull[ic];
var icx = ic + 1;
if (icx >= hlen) icx = 0;
var ixa = TriSet.hull[icx];
var edset1 = TriSet.vor_polygons[ix].edges;
var edset2 = TriSet.vor_polygons[ixa].edges;
var edsetshr = FindSharedEdges(edset1,edset2);
var edge = edsetshr[0];
var tvrt = edge.polys[0].index;
var vt0 = Positions[ix];
var vt1 = Positions[ixa];
var vtdf = vec_difference(vt1,vt0);
// Contains: triangle index (Voronoi vertex),
// vertex index 1 (Voronoi region), position
// vertex index 2 (Voronoi region), position,
// great-circle normal
var VorBdLn = [tvrt, TriSet.vor_positions[tvrt], ix, vt0, ixa, vt1, vtdf];
VorBdLns.push(VorBdLn);
}
// Find intersections
while (VorBdLns.length > 3)
{
// Check all combinations of neighbors
var n = VorBdLns.length;
var itscpts = new Array();
var ptitscs = new Array();
for (var k=0; k<n; k++)
ptitscs.push(new Array());
for (var k=0; k<n; k++)
{
vor_poly.boundary.reverse();
tri = init_tri;
// First edge the other way
for (var ic=0; ic<3; ic++)
// Find the intersection point; use the convex hull's direction
var kx = k + 1;
if (kx >= n) kx = 0;
var itscpt = Normalize(crsprd(VorBdLns[k][6],VorBdLns[kx][6]));
vec_mult_scalar_to(itscpt,-1);
ptitscs[k].push(itscpts.length);
ptitscs[kx].push(itscpts.length);
itscpts.push(itscpt);
}
// Find the intersection points that are the closest to their parent points
for (var k=0; k<n; k++)
{
var ptitsc = ptitscs[k];
if (ptitsc.length >= 2)
{
edge = tri.edges[ic];
if (EdgesEqual(edge,init_edge)) continue;
if (edge.IsVertex(ix))
break;
}
while(true)
{
var iv = edge.PolyIndexIn(tri);
tri = edge.polys[1-iv];
if (IsNull(tri)) break;
vor_poly.boundary.push(tri.index);
for (var ic=0; ic<3; ic++)
var dists = new Array();
for (var kp=0; kp<ptitsc.length; kp++)
dists.push(ptdist(itscpts[ptitsc[kp]],VorBdLns[k][1]));
var dx = 0;
var dmin = dists[dx];
for (var dxi=0; dxi<dists.length; dxi++)
{
var next_edge = tri.edges[ic];
if (EdgesEqual(next_edge,edge)) continue;
if (next_edge.IsVertex(ix))
var dst = dists[dxi];
if (dst < dmin)
{
edge = next_edge;
break;
dx = dxi; dmin = dst;
}
}
var ptitscrd = ptitsc[dx];
}
else if (ptitsc.length == 1)
var ptitscrd = ptitsc[0];
else
var ptitscrd = -1;
ptitscs[k] = ptitscrd;
}
// Add -1 on ends for open polygon:
if (!IsInside)
var NewVorBdLns = new Array();
for (var k=0; k<n; k++)
{
vor_poly.boundary.reverse();
vor_poly.boundary.push(-1);
vor_poly.boundary.reverse();
vor_poly.boundary.push(-1);
}
}
// Handle the area outside of the convex hull
if (TriSet.hull.length >= 3)
{
// Set up the initial boundary lines
// The boundary lines contain:
// Index of Voronoi vertex / triangle center / intersection (in VorPos)
// Indices of original vertices on each side of the line
var VorBdLns = new Array();
var Positions = TriSet.positions;
var hlen = TriSet.hull.length;
for (var ic=0; ic<hlen; ic++)
{
var ix = TriSet.hull[ic];
var icx = ic + 1;
if (icx >= hlen) icx = 0;
var ixa = TriSet.hull[icx];
var edset1 = TriSet.vor_polygons[ix].edges;
var edset2 = TriSet.vor_polygons[ixa].edges;
var edsetshr = FindSharedEdges(edset1,edset2);
var edge = edsetshr[0];
var tvrt = edge.polys[0].index;
var vt0 = Positions[ix];
var vt1 = Positions[ixa];
var vtdf = vec_difference(vt1,vt0);
// Contains: triangle index (Voronoi vertex),
// vertex index 1 (Voronoi region), position
// vertex index 2 (Voronoi region), position,
// great-circle normal
var VorBdLn = [tvrt, TriSet.vor_positions[tvrt], ix, vt0, ixa, vt1, vtdf];
VorBdLns.push(VorBdLn);
}
// Find intersections
while (VorBdLns.length > 3)
{
// Check all combinations of neighbors
var n = VorBdLns.length;
var itscpts = new Array();
var ptitscs = new Array();
for (var k=0; k<n; k++)
ptitscs.push(new Array());
for (var k=0; k<n; k++)
// Find all matched intersection points and add them
var kx = k + 1;
if (kx >= n) kx = 0;
var ky = k - 1;
if (ky < 0) ky = n - 1;
// 0 is lone, 1 is leading, 2 is trailing
// vorvtidx is the index of the Voronoi vertex
var pstat = 0;
var ptitsc = ptitscs[k], ptitsc_next;
if (ptitsc != -1)
{
// Find the intersection point; use the convex hull's direction
var kx = k + 1;
if (kx >= n) kx = 0;
var itscpt = Normalize(crsprd(VorBdLns[k][6],VorBdLns[kx][6]));
vec_mult_scalar_to(itscpt,-1);
ptitscs[k].push(itscpts.length)
ptitscs[kx].push(itscpts.length)
itscpts.push(itscpt)
var ptitsc_prev = ptitscs[ky];
if (ptitsc == ptitsc_prev)
pstat = 2;
else
{
ptitsc_next = ptitscs[kx];
if (ptitsc == ptitsc_next)
pstat = 1;
}
}
// Find the intersection points that are the closest to their parent points
for (var k=0; k<n; k++)
if (pstat == 0)
{
var ptitsc = ptitscs[k];
if (ptitsc.length >= 2)
// Keep the Voronoi line without merging
NewVorBdLns.push(VorBdLns[k]);
}
else if (pstat == 1)
{
// Merge the Voronoi lines and create a new one
var VorBdLn0 = VorBdLns[k];
var VorBdLn1 = VorBdLns[kx];
var itscpt = itscpts[k];
var tvrt0 = VorBdLn0[0];
var tvrt1 = VorBdLn1[0];
var PointOK = (tvrt1 != tvrt0);
if (PointOK)
{
var dists = new Array();
for (var kp=0; kp<ptitsc.length; kp++)
dists.push(ptdist(itscpts[ptitsc[kp]],VorBdLns[k][1]));
var dx = 0;
var dmin = dists[dx];
for (var dxi=0; dxi<dists.length; dxi++)
var nitx = TriSet.vor_positions.length;
var ix0 = VorBdLn0[2];
var vt0 = VorBdLn0[3];
var ix1 = VorBdLn1[4];
var vt1 = VorBdLn1[5];
var dst_in = undefined;
var dst_out = undefined;
for (var m=0; m<n; m++)
{
var dst = dists[dxi];
if (dst < dmin)
var ptstm = ptdist(VorBdLns[m][3],itscpt);
var mrl = m - k;
while (mrl < 0) mrl += n;
while (mrl >= n) mrl -= n;
if (mrl <= 2)
{
dx = dxi; dmin = dst;
if (dst_in == undefined)
dst_in = ptstm;
else if (ptstm < dst_in)
dst_in = ptstm;
}
else
{
if (dst_out == undefined)
dst_out = ptstm;
else if (ptstm < dst_out)
dst_out = ptstm;
}
}
var ptitscrd = ptitsc[dx];
PointOK = (dst_in < dst_out);
}
else if (ptitsc.length == 1)
var ptitscrd = ptitsc[0];
else
var ptitscrd = -1;
ptitscs[k] = ptitscrd;
}
var NewVorBdLns = new Array();
for (var k=0; k<n; k++)
{
// Find all matched intersection points and add them
var kx = k + 1;
if (kx >= n) kx = 0;
var ky = k - 1;
if (ky < 0) ky = n - 1;
// 0 is lone, 1 is leading, 2 is trailing
// vorvtidx is the index of the Voronoi vertex
var pstat = 0
var ptitsc = ptitscs[k], ptitsc_next;
if (ptitsc != -1)
if (PointOK)
{
var ptitsc_prev = ptitscs[ky];
if (ptitsc == ptitsc_prev)
pstat = 2;
else
var vtdf = vec_difference(vt1,vt0);
var VorBdLn = [nitx, itscpt, ix0, vt0, ix1, vt1, vtdf];
NewVorBdLns.push(VorBdLn);
TriSet.vor_positions.push(itscpt);
var ixi = VorBdLn0[4];
// Should be equal:
// ixi = VorBdLn2[2];
TriSet.vor_edges.push([tvrt0, nitx]);
TriSet.vor_edges.push([tvrt1, nitx]);
// Add the point to the center Voronoi region and close it
TriSet.vor_polygons[ixi].boundary.shift();
var vpln = TriSet.vor_polygons[ixi].boundary.length;
TriSet.vor_polygons[ixi].boundary[vpln-1] = nitx;
// Add the point to the left Voronoi region
if (TriSet.vor_polygons[ix0].boundary[1] == tvrt0)
{
ptitsc_next = ptitscs[kx];
if (ptitsc == ptitsc_next)
pstat = 1;
TriSet.vor_polygons[ix0].boundary.unshift(-1);
TriSet.vor_polygons[ix0].boundary[1] = nitx;
}
}
if (pstat == 0)
{
// Keep the Voronoi line without merging
NewVorBdLns.push(VorBdLns[k]);
}
else if (pstat == 1)
{
// Merge the Voronoi lines and create a new one
var VorBdLn0 = VorBdLns[k];
var VorBdLn1 = VorBdLns[kx];
var itscpt = itscpts[k];
var tvrt0 = VorBdLn0[0];
var tvrt1 = VorBdLn1[0];
var PointOK = (tvrt1 != tvrt0);
if (PointOK)
else
{
var nitx = TriSet.vor_positions.length;
var ix0 = VorBdLn0[2];
var vt0 = VorBdLn0[3];
var ix1 = VorBdLn1[4];
var vt1 = VorBdLn1[5];
var dst_in = undefined;
var dst_out = undefined;
for (var m=0; m<n; m++)
vpln = TriSet.vor_polygons[ix0].boundary.length;
if (TriSet.vor_polygons[ix0].boundary[vpln-2] == tvrt0)
{
var ptstm = ptdist(VorBdLns[m][3],itscpt);
var mrl = m - k;
while (mrl < 0) mrl += n;
while (mrl >= n) mrl -= n;
if (mrl <= 2)
{
if (dst_in == undefined)
dst_in = ptstm;
else if (ptstm < dst_in)
dst_in = ptstm;
}
else
{
if (dst_out == undefined)
dst_out = ptstm;
else if (ptstm < dst_out)
dst_out = ptstm;
}
TriSet.vor_polygons[ix0].boundary.push(-1);
vpln = TriSet.vor_polygons[ix0].boundary.length;
TriSet.vor_polygons[ix0].boundary[vpln-2] = nitx;
}
PointOK = (dst_in < dst_out);
}
if (PointOK)
// Add the point to the right Voronoi region
if (TriSet.vor_polygons[ix1].boundary[1] == tvrt1)
{
var vtdf = vec_difference(vt1,vt0);
var VorBdLn = [nitx, itscpt, ix0, vt0, ix1, vt1, vtdf];
NewVorBdLns.push(VorBdLn);
TriSet.vor_positions.push(itscpt);
var ixi = VorBdLn0[4];
// Should be equal:
// ixi = VorBdLn2[2];
TriSet.vor_edges.push([tvrt0, nitx]);
TriSet.vor_edges.push([tvrt1, nitx]);
// Add the point to the center Voronoi region and close it
TriSet.vor_polygons[ixi].boundary.shift();
var vpln = TriSet.vor_polygons[ixi].boundary.length;
TriSet.vor_polygons[ixi].boundary[vpln-1] = nitx;
// Add the point to the left Voronoi region
if (TriSet.vor_polygons[ix0].boundary[1] == tvrt0)
TriSet.vor_polygons[ix1].boundary.unshift(-1);
TriSet.vor_polygons[ix1].boundary[1] = nitx;
}
else
{
vpln = TriSet.vor_polygons[ix1].boundary.length;
if (TriSet.vor_polygons[ix1].boundary[vpln-2] == tvrt1)
{
TriSet.vor_polygons[ix0].boundary.unshift(-1);
TriSet.vor_polygons[ix0].boundary[1] = nitx;
}
else
{
vpln = TriSet.vor_polygons[ix0].boundary.length;
if (TriSet.vor_polygons[ix0].boundary[vpln-2] == tvrt0)
{
TriSet.vor_polygons[ix0].boundary.push(-1);
vpln = TriSet.vor_polygons[ix0].boundary.length;
TriSet.vor_polygons[ix0].boundary[vpln-2] = nitx;
}
}
// Add the point to the right Voronoi region
if (TriSet.vor_polygons[ix1].boundary[1] == tvrt1)
{
TriSet.vor_polygons[ix1].boundary.unshift(-1);
TriSet.vor_polygons[ix1].boundary[1] = nitx;
}
else
{
TriSet.vor_polygons[ix1].boundary.push(-1);
vpln = TriSet.vor_polygons[ix1].boundary.length;
if (TriSet.vor_polygons[ix1].boundary[vpln-2] == tvrt1)
{
TriSet.vor_polygons[ix1].boundary.push(-1);
vpln = TriSet.vor_polygons[ix1].boundary.length;
TriSet.vor_polygons[ix1].boundary[vpln-2] = nitx;
}
TriSet.vor_polygons[ix1].boundary[vpln-2] = nitx;
}
}
else
{
NewVorBdLns.push(VorBdLn0);
NewVorBdLns.push(VorBdLn1);
}
}
/*
else if (pstat == 2)
else
{
// Do nothing
NewVorBdLns.push(VorBdLn0);
NewVorBdLns.push(VorBdLn1);
}
*/
}
if (NewVorBdLns.length == VorBdLns.length) break;
VorBdLns = NewVorBdLns;
/*
else if (pstat == 2)
{
// Do nothing
}
*/
}
// Special cases: only two or three points left
if (VorBdLns.length == 2)
if (NewVorBdLns.length == VorBdLns.length) break;
VorBdLns = NewVorBdLns;
}
// Special cases: only two or three points left
if (VorBdLns.length == 2)
{
if (VorBdLns[0][0] != VorBdLns[1][0])
{
if (VorBdLns[0][0] != VorBdLns[1][0])
var VorLn = [];
for (var k=0; k<2; k++)
{
var VorLn = [];
for (var k=0; k<2; k++)
{
// Connecting line
var kx = VorBdLns[k][0];
VorLn.push(kx);
// Close the Voronoi region by deleting the end -1's
kx = VorBdLns[k][2];
TriSet.vor_polygons[kx].boundary.shift();
TriSet.vor_polygons[kx].boundary.pop();
}
TriSet.vor_edges.push(VorLn);
// Connecting line
var kx = VorBdLns[k][0];
VorLn.push(kx);
// Close the Voronoi region by deleting the end -1's
kx = VorBdLns[k][2];
TriSet.vor_polygons[kx].boundary.shift();
TriSet.vor_polygons[kx].boundary.pop();
}
TriSet.vor_edges.push(VorLn);
}
else if (VorBdLns.length == 3)
}
else if (VorBdLns.length == 3)
{
var ic0 = VorBdLns[0][0];
var ic1 = VorBdLns[1][0];
var ic2 = VorBdLns[2][0];
if (ic0 != ic1 && ic0 != ic2 && ic1 != ic2)
{
var ic0 = VorBdLns[0][0];
var ic1 = VorBdLns[1][0];
var ic2 = VorBdLns[2][0];
if (ic0 != ic1 && ic0 != ic2 && ic1 != ic2)
var nitx = TriSet.vor_positions.length;
var v0 = VorBdLns[0][3];
var v1 = VorBdLns[1][3];
var v2 = VorBdLns[2][3];
var itscpt = zerovec();
vec_add_to(itscpt,crsprd(v0,v1));
vec_add_to(itscpt,crsprd(v1,v2));
vec_add_to(itscpt,crsprd(v2,v0));
itscpt = Normalize(itscpt);
vec_mult_scalar_to(itscpt,-1);
TriSet.vor_positions.push(itscpt);
for (var k=0; k<3; k++)
{
var nitx = TriSet.vor_positions.length;
var v0 = VorBdLns[0][3];
var v1 = VorBdLns[1][3];
var v2 = VorBdLns[2][3];
var itscpt = zerovec();
vec_add_to(itscpt,crsprd(v0,v1));
vec_add_to(itscpt,crsprd(v1,v2));
vec_add_to(itscpt,crsprd(v2,v0));
itscpt = Normalize(itscpt);
vec_mult_scalar_to(itscpt,-1);
TriSet.vor_positions.push(itscpt);
for (var k=0; k<3; k++)
{
// Connecting line
var VorBdLn = VorBdLns[k];
TriSet.vor_edges.push([VorBdLn[0], nitx]);
// Add the point to the Voronoi region and close it
var ix = VorBdLn[2];
TriSet.vor_polygons[ix].boundary.shift();
var vpln = TriSet.vor_polygons[ix].boundary.length;
TriSet.vor_polygons[ix].boundary[vpln-1] = nitx;
}
// Connecting line
var VorBdLn = VorBdLns[k];
TriSet.vor_edges.push([VorBdLn[0], nitx]);
// Add the point to the Voronoi region and close it
var ix = VorBdLn[2];
TriSet.vor_polygons[ix].boundary.shift();
var vpln = TriSet.vor_polygons[ix].boundary.length;
TriSet.vor_polygons[ix].boundary[vpln-1] = nitx;
}
}
}
// Adjust the orientations
for (var k=0; k<TriSet.vor_polygons.length; k++)
}
// Adjust the orientations
for (var k=0; k<TriSet.vor_polygons.length; k++)
{
vor_poly = TriSet.vor_polygons[k];
if (vor_poly.boundary.length >= 3 && vor_poly.boundary[0] >= 0)
{
vor_poly = TriSet.vor_polygons[k];
if (vor_poly.boundary.length >= 3 && vor_poly.boundary[0] >= 0)
{
tri = new TriangleObject(TriSet.vor_positions,vor_poly.boundary.slice(0,3));
if (!tri.IsVertexOrderCorrect())
vor_poly.boundary.reverse();
}
tri = new TriangleObject(TriSet.vor_positions,vor_poly.boundary.slice(0,3));
if (!tri.IsVertexOrderCorrect())
vor_poly.boundary.reverse();
}
}
}
function FindDelaunayTriangulationIndexed(Positions, Indices)
function FindDelaunayTriangulationIndexed(Positions, Indices)
{
// Create the triangle-set object
var TriSet = new Object;
TriSet.positions = Positions;
TriSet.indices = Indices;
TriSet.triangles = [];
TriSet.edges = [];
TriSet.hull = [];
TriSet.vor_positions = [];
TriSet.vor_edges = [];
TriSet.vor_polygons = new Object;
// Create the first triangle, if it is possible to create any
if (Indices.length < 3)
{
// Create the triangle-set object
var TriSet = new Object;
TriSet.positions = Positions;
TriSet.indices = Indices;
TriSet.triangles = [];
TriSet.edges = [];
TriSet.hull = [];
TriSet.vor_positions = [];
TriSet.vor_edges = [];
TriSet.vor_polygons = new Object;
// Create the first triangle, if it is possible to create any
if (Indices.length < 3)
if (Indices.length == 2)
{
if (Indices.length == 2)
{
TriSet.edges.push(new EdgeObject(Indices));
TriSet.hull = Indices;
}
FindVoronoiDiagram(TriSet);
return TriSet;
TriSet.edges.push(new EdgeObject(Indices));
TriSet.hull = Indices;
}
FindVoronoiDiagram(TriSet);
return TriSet;
}
var tri = new TriangleObject(Positions, Indices.slice(0,3));
if (!tri.IsVertexOrderCorrect())
tri = new TriangleObject(Positions, [Indices[0],Indices[2],Indices[1]]);
TriSet.triangles.push(tri);
var echs = new Array(3);
for (var ic=0; ic<3; ic++)
{
var ic1 = ic + 1;
if (ic1 >= 3) ic1 -= 3;
var ix = Indices[ic];
var ix1 = Indices[ic1];
var vts = [ix, ix1];
var edge = new EdgeObject(vts);
var echeck = new EdgeCheckObject(Positions,vts);
echeck.edge = edge;
echs[ic] = echeck;
tri.edges[ic] = edge;
edge.polys[0] = tri;
TriSet.edges.push(edge);
}
// Place those crossing checkers in a boundary object;
// will have to use various kludges since JavaScript doesn't have sets
var BoundaryVerts = Indices.slice(0,3);
var BoundaryEdges = echs;
var Verts = Object;
for (var ic=0; ic<3; ic++)
{
var ic1 = ic + 2;
if (ic1 >= 3) ic1 -= 3;
var ix = Indices[ic];
Verts[ix] = [echs[ic],echs[ic+1]];
}
// Add points until it is no longer possible
for (var i=3; i<Indices.length; i++)
{
var ix = Indices[i];
var tri = new TriangleObject(Positions, Indices.slice(0,3));
if (!tri.IsVertexOrderCorrect())
tri = new TriangleObject(Positions, [Indices[0],Indices[2],Indices[1]]);
TriSet.triangles.push(tri);
// If possible, add the point inside
if (AddPointInside(TriSet, ix)) continue;
var echs = new Array(3);
// Point was not inside
Verts[ix] = [];
var NewEdges = [];
var VertsAddedTo = [];
var EdgesToDelete = [];
for (var ic=0; ic<3; ic++)
// Find all the non-intersecting edges
for (var j=0; j<BoundaryVerts.length; j++)
{
var ic1 = ic + 1;
if (ic1 >= 3) ic1 -= 3;
var ix = Indices[ic];
var ix1 = Indices[ic1];
var vts = [ix, ix1];
var edge = new EdgeObject(vts);
var echeck = new EdgeCheckObject(Positions,vts);
echeck.edge = edge;
echs[ic] = echeck;
tri.edges[ic] = edge;
edge.polys[0] = tri;
TriSet.edges.push(edge);
var ix1 = BoundaryVerts[j];
var echk = new EdgeCheckObject(Positions, [ix, ix1]);
var DoesIntersect = false;
for (var k=0; k<BoundaryEdges.length; k++)
{
var echk1 = BoundaryEdges[k];
DoesIntersect = echk.intersects(Positions,echk1);
if (DoesIntersect) break;
}
if (DoesIntersect) continue;
var edge = new EdgeObject(echk.verts);
echk.edge = edge;
AddUniqueEdge(NewEdges,echk);
AddUniqueEdge(Verts[ix],echk);
AddUnique(VertsAddedTo,ix);
AddUniqueEdge(Verts[ix1],echk);
AddUnique(VertsAddedTo,ix1);
}
// Place those crossing checkers in a boundary object;
// will have to use various kludges since JavaScript doesn't have sets
var BoundaryVerts = Indices.slice(0,3);
var BoundaryEdges = echs;
var Verts = Object;
for (var ic=0; ic<3; ic++)
{
var ic1 = ic + 2;
if (ic1 >= 3) ic1 -= 3;
var ix = Indices[ic];
Verts[ix] = [echs[ic],echs[ic+1]];
}
// Add the new vertex itself
AddUnique(BoundaryVerts,ix);
// Add points until it is no longer possible
for (var i=3; i<Indices.length; i++)
// Find all the triangles
for (var j=0; j<BoundaryEdges.length; j++)
{
var ix = Indices[i];
var echk = BoundaryEdges[j];
var echks = [];
// If possible, add the point inside
if (AddPointInside(TriSet, ix)) continue;
for (var iv=0; iv<2; iv++)
{
var vset = FindSharedEdges(Verts[ix],Verts[echk.verts[iv]]);
if (vset.length == 0) continue;
echks.push(vset[0]);
}
if (echks.length < 2) continue;
// Point was not inside
Verts[ix] = [];
var NewEdges = [];
var VertsAddedTo = [];
var EdgesToDelete = [];
// Find all the non-intersecting edges
for (var j=0; j<BoundaryVerts.length; j++)
var empt_indx = -1;
for (var iv=0; iv<2; iv++)
{
var ix1 = BoundaryVerts[j];
var echk = new EdgeCheckObject(Positions, [ix, ix1]);
var DoesIntersect = false;
for (var k=0; k<BoundaryEdges.length; k++)
if (IsNull(echk.edge.polys[iv]))
{
var echk1 = BoundaryEdges[k];
DoesIntersect = echk.intersects(Positions,echk1);
if (DoesIntersect) break;
empt_indx = iv;
break;
}
if (DoesIntersect) continue;
var edge = new EdgeObject(echk.verts);
echk.edge = edge;
AddUniqueEdge(NewEdges,echk);
AddUniqueEdge(Verts[ix],echk);
AddUnique(VertsAddedTo,ix);
AddUniqueEdge(Verts[ix1],echk);
AddUnique(VertsAddedTo,ix1);
}
if (empt_indx < 0) continue;
// Add the new vertex itself
AddUnique(BoundaryVerts,ix);
var oldtri = echk.edge.polys[1-empt_indx];
var v0 = echk.verts[0];
var i0 = oldtri.VertexIndexIn(v0);
var v1 = echk.verts[1];
var i1 = oldtri.VertexIndexIn(v1);
var i01 = i1 - i0;
if (i01 < 0) i01 += 3;
if (i01 == 1)
{
// Order in original: other, v0, v1
var NewTriVerts = [ix, v1, v0];
}
else if (i01 == 2)
{
// Order in original: other, v1, v0
var NewTriVerts = [ix, v0, v1];
}
var tri = new TriangleObject(Positions, NewTriVerts);
if (!tri.IsVertexOrderCorrect()) continue;
// Find all the triangles
for (var j=0; j<BoundaryEdges.length; j++)
// Add the new triangle
// Also, add the new edges,
// or remove them from the lists if necessary
TriSet.triangles.push(tri);
echk.edge.polys[empt_indx] = tri;
tri.edges[0] = echk.edge;
tri.edges[1] = echks[0].edge;
tri.edges[2] = echks[1].edge;
AddUniqueEdge(EdgesToDelete, echk);
for (var iv=0; iv<2; iv++)
{
var echk = BoundaryEdges[j];
var echks = [];
for (var iv=0; iv<2; iv++)
var echki = echks[iv];
if (IsNull(echki.edge.polys[0]))
{
var vset = FindSharedEdges(Verts[ix],Verts[echk.verts[iv]]);
if (vset.length == 0) continue;
echks.push(vset[0]);
echki.edge.polys[0] = tri;
TriSet.edges.push(echki.edge);
}
if (echks.length < 2) continue;
var empt_indx = -1;
for (var iv=0; iv<2; iv++)
else
{
if (IsNull(echk.edge.polys[iv]))
{
empt_indx = iv;
break;
}
echki.edge.polys[1] = tri;
AddUniqueEdge(EdgesToDelete,echki);
}
if (empt_indx < 0) continue;
var oldtri = echk.edge.polys[1-empt_indx];
var v0 = echk.verts[0];
var i0 = oldtri.VertexIndexIn(v0);
var v1 = echk.verts[1];
var i1 = oldtri.VertexIndexIn(v1);
var i01 = i1 - i0;
if (i01 < 0) i01 += 3;
if (i01 == 1)
{
// Order in original: other, v0, v1
var NewTriVerts = [ix, v1, v0];
}
else if (i01 == 2)
{
// Order in original: other, v1, v0
var NewTriVerts = [ix, v0, v1];
}
var tri = new TriangleObject(Positions, NewTriVerts);
if (!tri.IsVertexOrderCorrect()) continue;
// Add the new triangle
// Also, add the new edges,
// or remove them from the lists if necessary
TriSet.triangles.push(tri);
echk.edge.polys[empt_indx] = tri;
tri.edges[0] = echk.edge;
tri.edges[1] = echks[0].edge;
tri.edges[2] = echks[1].edge;
AddUniqueEdge(EdgesToDelete, echk);
for (var iv=0; iv<2; iv++)
{
var echki = echks[iv];
if (IsNull(echki.edge.polys[0]))
{
echki.edge.polys[0] = tri;
TriSet.edges.push(echki.edge);
}
else
{
echki.edge.polys[1] = tri;
AddUniqueEdge(EdgesToDelete,echki);
}
}
}
// Add the new edges and remove the edges and vertices
// that are now in the interior
for (var j=0; j<NewEdges.length; j++)
AddUniqueEdge(BoundaryEdges,NewEdges[j]);
FindSetDifferenceEdges(BoundaryEdges, EdgesToDelete);
var BoundaryVertsToRemove = [];
for (var j=0; j<VertsAddedTo.length; j++)
{
var ixa = VertsAddedTo[j];
FindSetDifferenceEdges(Verts[ixa],EdgesToDelete);
if (Verts[ixa].length == 0)
BoundaryVertsToRemove.push(ixa);
}
FindSetDifference(BoundaryVerts, BoundaryVertsToRemove);
}
// Improve it iteratively
ImproveTriangulation(TriSet);
// Add the new edges and remove the edges and vertices
// that are now in the interior
for (var j=0; j<NewEdges.length; j++)
AddUniqueEdge(BoundaryEdges,NewEdges[j]);
FindSetDifferenceEdges(BoundaryEdges, EdgesToDelete);
// Find the boundary line of this region
FindConvexHull(TriSet);
// Find the regions around each point:
FindVoronoiDiagram(TriSet);
return TriSet;
var BoundaryVertsToRemove = [];
for (var j=0; j<VertsAddedTo.length; j++)
{
var ixa = VertsAddedTo[j];
FindSetDifferenceEdges(Verts[ixa],EdgesToDelete);
if (Verts[ixa].length == 0)
BoundaryVertsToRemove.push(ixa);
}
FindSetDifference(BoundaryVerts, BoundaryVertsToRemove);
}
// Improve it iteratively
ImproveTriangulation(TriSet);
// Find the boundary line of this region
FindConvexHull(TriSet);
// Find the regions around each point:
FindVoronoiDiagram(TriSet);
return TriSet;
}
function FindDelaunayTriangulation(Positions)
{
var Indices = new Array(Positions.length);
for (var i=0; i<Indices.length; i++)
Indices[i] = i;
return FindDelaunayTriangulationIndexed(Positions, Indices);
}
function FindDelaunayTriangulation(Positions)
{
var Indices = new Array(Positions.length);
for (var i=0; i<Indices.length; i++)
Indices[i] = i;
return FindDelaunayTriangulationIndexed(Positions, Indices);
}
function geoVoronoi () {
var radians = Math.PI / 180;
//
// (c) 2016 Philippe Riviere
//
// https://github.com/Fil/
//
// This software is distributed under the terms of the MIT License
var cartesian = function (spherical) {
var lambda = spherical[0] * radians,
phi = spherical[1] * radians,
cosphi = Math.cos(phi);
return [
cosphi * Math.cos(lambda),
cosphi * Math.sin(lambda),
Math.sin(phi)
];
}
var geoVoronoi = function () {
var radians = Math.PI / 180;
var spherical = function (cartesian) {
var r = Math.sqrt(cartesian[0] * cartesian[0] + cartesian[1] * cartesian[1]),
lat = Math.atan2(cartesian[2], r),
lng = Math.atan2(cartesian[1], cartesian[0]);
return [lng / radians, lat / radians];
}
var cartesian = function (spherical) {
var lambda = spherical[0] * radians,
phi = spherical[1] * radians,
cosphi = Math.cos(phi);
return [
cosphi * Math.cos(lambda),
cosphi * Math.sin(lambda),
Math.sin(phi)
];
};
var mapline = function (Positions, Verts) {
return Verts
.map(function (v) {
return spherical(Positions[v]);
});
}
var spherical = function (cartesian) {
var r = Math.sqrt(cartesian[0] * cartesian[0] + cartesian[1] * cartesian[1]),
lat = Math.atan2(cartesian[2], r),
lng = Math.atan2(cartesian[1], cartesian[0]);
return [lng / radians, lat / radians];
};
var mapline = function (Positions, Verts) {
return Verts
.map(function (v) {
return spherical(Positions[v]);
});
};
var diagram = d3Voronoi.voronoi()([]);
var DT = diagram.DT = null,
sites = diagram.sites = [],
pos = diagram.pos = [],
x = function (d) {
if (typeof d == 'object' && 'type' in d) {
return d3Geo.geoCentroid(d)[0];
}
if (0 in d) return d[0];
},
y = function (d) {
if (typeof d == 'object' && 'type' in d) {
return d3Geo.geoCentroid(d)[1];
}
if (0 in d) return d[1];
};
var diagram = d3Voronoi.voronoi()([]);
var DT = diagram.DT = null,
sites = diagram.sites = [],
pos = diagram.pos = [],
x = function (d) {
if (typeof d == 'object' && 'type' in d) {
return d3Geo.geoCentroid(d)[0];
}
if (0 in d) return d[0];
},
y = function (d) {
if (typeof d == 'object' && 'type' in d) {
return d3Geo.geoCentroid(d)[1];
}
if (0 in d) return d[1];
};
var voro = function (data) {
diagram._hull = diagram._polygons = diagram._links = diagram._triangles = null;
if (typeof data == 'object' && data.type == 'FeatureCollection') {
data = data.features;
}
sites = data.map(function (site, i) {
site.index = i;
return site;
});
pos = data.map(function (site) {
return [x(site), y(site)];
});
DT = FindDelaunayTriangulation(pos.map(cartesian));
return diagram;
}
var voro = function (data) {
diagram._hull = diagram._polygons = diagram._links = diagram._triangles = null;
diagram.links = voro.links = function (s) {
if (s) voro(s);
if (diagram._links) return diagram._links;
if (typeof data == 'object' && data.type == 'FeatureCollection') {
data = data.features;
}
sites = data.map(function (site, i) {
site.index = i;
return site;
});
pos = data.map(function (site) {
return [x(site), y(site)];
});
DT = FindDelaunayTriangulation(pos.map(cartesian));
return diagram;
};
var _index = d3Collection.map();
diagram.links = voro.links = function (s) {
if (s) voro(s);
if (diagram._links) return diagram._links;
var features = DT.edges.map(function (i, n) {
var _index = d3Collection.map();
_index.set(d3Array.extent(i.verts), n);
var features = DT.edges.map(function (i, n) {
var properties = {
source: sites[i.verts[0]],
target: sites[i.verts[1]],
urquhart: true, // will be changed to false later
length: d3Geo.geoDistance(pos[i.verts[0]], pos[i.verts[1]])
}
_index.set(d3Array.extent(i.verts), n);
// add left and right sites (?)
var properties = {
source: sites[i.verts[0]],
target: sites[i.verts[1]],
urquhart: true, // will be changed to false later
length: d3Geo.geoDistance(pos[i.verts[0]], pos[i.verts[1]])
};
// make GeoJSON
return {
type: "Feature",
geometry: {
type: 'LineString',
coordinates: [spherical(DT.positions[i.verts[0]]), spherical(DT.positions[i.verts[1]])]
},
properties: properties
};
});
// add left and right sites (?)
// Urquhart Graph? tag longer link from each triangle
DT.triangles.forEach(function (t) {
var l = 0,
length = 0,
remove, v;
for (var j = 0; j < 3; j++) {
v = d3Array.extent([t.verts[j], t.verts[(j + 1) % 3]]);
var n = _index.get(v);
length = features[n].properties.length;
if (length > l) {
l = length;
remove = n;
}
}
features[remove].properties.urquhart = false;
});
// make GeoJSON
return {
type: "Feature",
geometry: {
type: 'LineString',
coordinates: [spherical(DT.positions[i.verts[0]]), spherical(DT.positions[i.verts[1]])]
},
properties: properties
};
});
return diagram._links = {
type: "FeatureCollection",
features: features
};
};
// Urquhart Graph? tag longer link from each triangle
DT.triangles.forEach(function (t) {
var l = 0,
length = 0,
remove, v;
for (var j = 0; j < 3; j++) {
v = d3Array.extent([t.verts[j], t.verts[(j + 1) % 3]]);
var n = _index.get(v);
length = features[n].properties.length;
if (length > l) {
l = length;
remove = n;
}
}
features[remove].properties.urquhart = false;
});
diagram.triangles = voro.triangles = function (s) {
if (s) voro(s);
if (diagram._triangles) return diagram._triangles;
return diagram._links = {
type: "FeatureCollection",
features: features
};
};
var features = DT.triangles
.map(function (t) {
t.spherical = t.verts.map(function (v) {
return DT.positions[v];
})
.map(spherical);
diagram.triangles = voro.triangles = function (s) {
if (s) voro(s);
if (diagram._triangles) return diagram._triangles;
// correct winding order
if (t.ccdsq < 0) {
t.spherical = t.spherical.reverse();
t.ccdsq *= -1;
}
var features = DT.triangles
.map(function (t) {
t.spherical = t.verts.map(function (v) {
return DT.positions[v];
})
.map(spherical);
return t;
})
// correct winding order
if (t.ccdsq < 0) {
t.spherical = t.spherical.reverse();
t.ccdsq *= -1;
}
// make geojson
.map(function (t) {
return {
type: "Feature",
geometry: {
type: "Polygon",
coordinates: [t.spherical.concat([t.spherical[0]])]
},
properties: {
sites: t.verts.map(function (i) {
return sites[i];
}),
area: t.vol, // steradians
circumcenter: spherical(t.ccdir),
// ccdsq is *not* the geodesic distance
/* circumradius: (2-t.ccdsq) * 53 */
}
}
});
return t;
})
return diagram._triangles = {
type: "FeatureCollection",
features: features
};
// make geojson
.map(function (t) {
return {
type: "Feature",
geometry: {
type: "Polygon",
coordinates: [t.spherical.concat([t.spherical[0]])]
},
properties: {
sites: t.verts.map(function (i) {
return sites[i];
}),
area: t.vol, // steradians
circumcenter: spherical(t.ccdir),
// ccdsq is *not* the geodesic distance
/* circumradius: (2-t.ccdsq) * 53 */
}
}
});
};
return diagram._triangles = {
type: "FeatureCollection",
features: features
};
diagram.polygons = voro.polygons = function (s) {
if (s) voro(s);
if (diagram._polygons) return diagram._polygons;
};
var features = DT.indices.map(function (i, n) {
var vor_poly = DT.vor_polygons[DT.indices[i]];
var geometry = {}
diagram.polygons = voro.polygons = function (s) {
if (s) voro(s);
if (diagram._polygons) return diagram._polygons;
if (vor_poly == undefined) {
geometry.type = "Sphere";
} else {
var line = mapline(DT.vor_positions,
vor_poly.boundary.concat([vor_poly.boundary[0]])
);
var features = DT.indices.map(function (i, n) {
var vor_poly = DT.vor_polygons[DT.indices[i]];
var geometry = {};
// correct winding order
var b = {
type: "Polygon",
coordinates: [[pos[i], line[0], line[1], pos[i]]]
};
if (d3Geo.geoArea(b) > 2 * Math.PI + 1e-10) {
line = line.reverse();
}
if (vor_poly == undefined) {
geometry.type = "Sphere";
} else {
var line = mapline(DT.vor_positions,
vor_poly.boundary.concat([vor_poly.boundary[0]])
);
geometry.type = "Polygon";
geometry.coordinates = [line];
}
// correct winding order
var b = {
type: "Polygon",
coordinates: [[pos[i], line[0], line[1], pos[i]]]
};
if (d3Geo.geoArea(b) > 2 * Math.PI + 1e-10) {
line = line.reverse();
}
return {
type: "Feature",
geometry: geometry,
properties: {
site: sites[i],
sitecoordinates: pos[i],
neighbours: vor_poly.edges.map(function (e) {
return e.verts.filter(function (j) {
return j !== i;
})[0];
})
}
};
});
geometry.type = "Polygon";
geometry.coordinates = [line];
}
return diagram._polygons = {
type: "FeatureCollection",
features: features
};
};
return {
type: "Feature",
geometry: geometry,
properties: {
site: sites[i],
sitecoordinates: pos[i],
neighbours: vor_poly.edges.map(function (e) {
return e.verts.filter(function (j) {
return j !== i;
})[0];
})
}
};
});
diagram.hull = voro.hull = function (s) {
if (s) voro(s);
if (diagram._hull) return diagram._hull;
return diagram._polygons = {
type: "FeatureCollection",
features: features
};
};
if (!DT.hull.length) {
return null; // What is a null GeoJSON?
}
diagram.hull = voro.hull = function (s) {
if (s) voro(s);
if (diagram._hull) return diagram._hull;
// seems that DT.hull is always clockwise
var hull = DT.hull.reverse();
if (!DT.hull.length) {
return null; // What is a null GeoJSON?
}
// make GeoJSON
return diagram._hull = {
type: "Feature",
geometry: {
type: "Polygon",
coordinates: [hull.concat([hull[0]]).map(function (i) {
return pos[i];
})]
},
properties: {
sites: hull.map(function (i) {
return sites[i];
})
}
};
}
// seems that DT.hull is always clockwise
var hull = DT.hull.reverse();
// make GeoJSON
return diagram._hull = {
type: "Feature",
geometry: {
type: "Polygon",
coordinates: [hull.concat([hull[0]]).map(function (i) {
return pos[i];
})]
},
properties: {
sites: hull.map(function (i) {
return sites[i];
})
}
};
};
diagram.find = function (x, y, radius) {
var features = diagram.polygons().features;
// optimization: start from most recent result
var i, next = diagram.find.found || 0;
var cell = features[next] || features[next = 0];
diagram.find = function (x, y, radius) {
var features = diagram.polygons().features;
var dist = d3Geo.geoDistance([x, y], cell.properties.sitecoordinates);
do {
cell = features[i = next];
next = null;
cell.properties.neighbours.forEach(function (e) {
var ndist = d3Geo.geoDistance([x, y], features[e].properties.sitecoordinates);
if (ndist < dist) {
dist = ndist;
next = e;
return;
}
});
// optimization: start from most recent result
var i, next = diagram.find.found || 0;
var cell = features[next] || features[next = 0];
} while (next !== null);
diagram.find.found = i;
if (!radius || dist < radius * radius) return cell.properties.site;
}
var dist = d3Geo.geoDistance([x, y], cell.properties.sitecoordinates);
do {
cell = features[i = next];
next = null;
cell.properties.neighbours.forEach(function (e) {
var ndist = d3Geo.geoDistance([x, y], features[e].properties.sitecoordinates);
if (ndist < dist) {
dist = ndist;
next = e;
return;
}
});
voro.x = function (f) {
if (!f) return x;
x = f;
return voro;
}
voro.y = function (f) {
if (!f) return y;
y = f;
return voro;
}
voro.extent = function (f) {
if (!f) return null;
return voro;
}
voro.size = function (f) {
if (!f) return null;
return voro;
}
} while (next !== null);
diagram.find.found = i;
if (!radius || dist < radius * radius) return cell.properties.site;
};
return voro;
voro.x = function (f) {
if (!f) return x;
x = f;
return voro;
};
voro.y = function (f) {
if (!f) return y;
y = f;
return voro;
};
voro.extent = function (f) {
if (!f) return null;
return voro;
};
voro.size = function (f) {
if (!f) return null;
return voro;
};
}
return voro;
exports.geoVoronoi = geoVoronoi;
};
Object.defineProperty(exports, '__esModule', { value: true });
exports.geoVoronoi = geoVoronoi;
}));
Object.defineProperty(exports, '__esModule', { value: true });
})));

3

build/d3-geo-voronoi.min.js

@@ -1,1 +0,2 @@

!function(r,e){"object"==typeof exports&&"undefined"!=typeof module?e(exports,require("d3-array"),require("d3-collection"),require("d3-geo"),require("d3-voronoi")):"function"==typeof define&&define.amd?define(["exports","d3-array","d3-collection","d3-geo","d3-voronoi"],e):e(r.d3=r.d3||{},r.d3,r.d3,r.d3,r.d3)}(this,function(r,e,n,o,t){"use strict";function s(r,e){for(var n=0,o=0;o<3;o++)n+=r[o]*e[o];return n}function i(r,e){for(var n=new Array(3),o=0;o<3;o++){var t=o+1;t>=3&&(t-=3);var s=o+2;s>=3&&(s-=3),n[o]=r[t]*e[s]-r[s]*e[t]}return n}function a(r,e,n){return s(i(r,e),n)}function v(r,e){for(var n=0,o=0,t=0;t<3;t++){var s=e[t]-r[t];n+=s*s;var i=e[t]+r[t];o+=i*i}return Math.sqrt(n)-Math.sqrt(o)}function u(r){for(var e,n=new Array(3),o=0,t=0;t<3;t++){var s=r[t];o+=s*s}e=o>0?1/Math.sqrt(o):0;for(var t=0;t<3;t++)n[t]=e*r[t];return n}function f(r,e,n){return i(r[e],r[n])}function l(r,e,n,o){return a(r[e],r[n],r[o])}function p(r,e,n){return v(r[e],r[n])}function g(){for(var r=new Array(3),e=0;e<3;e++)r[e]=0;return r}function d(r){for(var e=new Array(3),n=0;n<3;n++)e[n]=r[n];return e}function h(r,e){for(var n=0;n<3;n++)r[n]+=e[n]}function c(r,e){for(var n=0;n<3;n++)r[n]*=e}function y(r,e){for(var n=g(),o=0;o<3;o++)n[o]=r[o]-e[o];return n}function _(r){return"undefined"==typeof r}function b(r,e){if(_(r))return!1;if(_(e))return!1;for(var n=0;n<3;n++)if(r.verts[n]!=e.verts[n])return!1;return!0}function I(r,e){if(_(r))return!1;if(_(e))return!1;for(var n=0;n<2;n++)if(r.verts[n]!=e.verts[n])return!1;return!0}function x(r,e){return e>r?e:r}function w(r,e){this.verts=e,this.edges=new Array(3),this.dirs=new Array(3);for(var n=0;n<3;n++){var o=n+1;o>=3&&(o-=3);var t=n+2;t>=3&&(t-=3),this.dirs[n]=f(r,e[o],e[t])}this.vol=l(r,e[0],e[1],e[2]);for(var n=0;n<3;n++)c(this.dirs[n],1/this.vol);for(var s=g(),n=0;n<3;n++)h(s,this.dirs[n]);this.ccdir=u(s);for(var i=0,n=0;n<3;n++)i+=v(this.ccdir,r[e[n]]);i/=3,this.ccdsq=i}function m(r){this.verts=r,this.polys=new Array(2)}function k(r,e){this.verts=e,this.pdst=p(r,e[0],e[1]),this.direc=u(f(r,e[0],e[1]));var n=g();h(n,r[e[0]]),h(n,r[e[1]]),this.midpnt=u(n)}function V(r,e){for(var n=0;n<r.length;n++)if(e==r[n])return;r.push(e)}function A(r,e){for(var n=0;n<r.length;n++)if(I(r[n],e))return;r.push(e)}function P(r,e){for(var n=[],o=0;o<r.length;o++)for(var t=r[o],s=0;s<e.length;s++){var i=e[s];if(t==i){n.push(t);break}}return n}function q(r,e){for(var n=[],o=0;o<r.length;o++)for(var t=r[o],s=0;s<e.length;s++){var i=e[s];if(I(t,i)){n.push(t);break}}return n}function C(r,e){if(0!=e.length){for(var n=[],o=0;o<r.length;o++){for(var t=r[o],s=!0,i=0;i<e.length;i++){var a=e[i];if(a==t){s=!1;break}}s&&n.push(t)}r.splice(0,r.length);for(var v=0;v<n.length;v++)r.push(n[v])}}function O(r,e){if(0!=e.length){for(var n=[],o=0;o<r.length;o++){for(var t=r[o],s=!0,i=0;i<e.length;i++){var a=e[i];if(I(t,a)){s=!1;break}}s&&n.push(t)}r.splice(0,r.length);for(var v=0;v<n.length;v++)r.push(n[v])}}function M(r,e){for(var n=r.positions,o=n[e],t=r.triangles.length,s=0;s<t;s++){var i=r.triangles[s];if(i.IsPointInside(o)){for(var a=i.edges,v=[],u=0;u<3;u++)v.push(a[u].PolyIndexIn(i));for(var f=Array(3),l=Array(3),u=0;u<3;u++){var p=u+1;p>=3&&(p-=3),f[u]=new w(n,[i.verts[u],i.verts[p],e]),l[u]=new m([i.verts[u],e])}for(var u=0;u<3;u++){var p=u+1;p>=3&&(p-=3),f[u].edges[0]=l[p],f[u].edges[1]=l[u],l[u].polys[0]=f[u],l[p].polys[1]=f[u]}for(var u=0;u<3;u++)for(var g=a[u],d=v[u],h=0;h<3;h++)for(var c=f[h],y=0,_=0;_<2;_++)if(c.IsVertex(g.verts[_])&&y++,2==y){g.polys[d]=c,c.edges[2]=g;break}r.triangles[s]=f[0];for(var u=1;u<3;u++)r.triangles.push(f[u]);for(var u=0;u<3;u++)r.edges.push(l[u]);return!0}}return!1}function j(r){for(var e=r.positions,n=new Array(4),o=0;o<100;o++){for(var t=0,s=0;s<r.edges.length;s++){var i=r.edges[s],a=i.polys;if(!_(a[0])&&!_(a[1])){for(var v=0;v<3;v++){var u=a[0].verts[v];if(!i.IsVertex(u))break}var f=v+1;f>=3&&(f-=3);var l=v+2;l>=3&&(l-=3),n[0]=u,n[1]=a[0].verts[f],n[3]=a[0].verts[l];for(var v=0;v<3;v++){var u=a[1].verts[v];if(!i.IsVertex(u))break}n[2]=u;var p=a[0].IsPointInCircumcircle(e[n[2]]),g=a[1].IsPointInCircumcircle(e[n[0]]);if(p||g){var d=new w(e,[n[0],n[1],n[2]]);if(d.IsVertexOrderCorrect()){var h=new w(e,[n[0],n[2],n[3]]);if(h.IsVertexOrderCorrect()){t++;for(var v=0;v<3;v++){var c=a[0].edges[v];if(!I(c,i)&&c.IsVertex(n[3])){var y=c,b=v;break}}for(var v=0;v<3;v++){var c=a[1].edges[v];if(!I(c,i)&&c.IsVertex(n[1])){var x=c,m=v;break}}var k=y.PolyIndexIn(a[0]),V=x.PolyIndexIn(a[1]);y.polys[k]=a[1],x.polys[V]=a[0],a[0].edges[b]=x,a[1].edges[m]=y,a[0].copy_vert_info(d),a[1].copy_vert_info(h),i.verts=[n[0],n[2]]}}}}}if(0==t)break}}function F(r){for(var e=new Object,n=-1,o=0;o<r.edges.length;o++){var t=r.edges[o];if(_(t.polys[0])){if(_(t.polys[1]))continue;var s=t.polys[1]}else{if(!_(t.polys[1]))continue;var s=t.polys[0]}var i=t.verts[0],a=t.verts[1],v=s.VertexIndexIn(a)-s.VertexIndexIn(i);if(v<0&&(v+=3),1!=v){var u=i;i=a,a=u}e[i]=a,n=i}if(n>=0){for(var f=n,l=[f];;){var p=e[f];if(p==n)break;l.push(p),f=p}r.hull=l}}function D(r){if(1!=r.triangles.length){if(0!=r.triangles.length){for(var e=0;e<r.triangles.length;e++){var n=r.triangles[e];n.index=e,r.vor_positions.push(n.ccdir)}for(var e=0;e<r.edges.length;e++){var o=r.edges[e];if(!_(o.polys[0])&&!_(o.polys[1])){var t=[o.polys[0].index,o.polys[1].index];r.vor_edges.push(t)}}for(var e=0;e<r.indices.length;e++){var s=r.indices[e];r.vor_polygons[s]=new Object;var a=r.vor_polygons[s];a.edges=[],a.triangles=[],a.boundary=[]}for(var e=0;e<r.edges.length;e++)for(var o=r.edges[e],f=0;f<2;f++)r.vor_polygons[o.verts[f]].edges.push(o);for(var e=0;e<r.triangles.length;e++)for(var n=r.triangles[e],f=0;f<3;f++)r.vor_polygons[n.verts[f]].triangles.push(n);for(var e=0;e<r.indices.length;e++){var s=r.indices[e],a=r.vor_polygons[s],l=a.triangles[0],n=l;a.boundary.push(n.index);for(var f=0;f<3;f++){var o=n.edges[f];if(o.IsVertex(s))break}for(var p=o,x=!1;;){var m=o.PolyIndexIn(n);if(n=o.polys[1-m],_(n))break;if(b(n,l)){x=!0;break}a.boundary.push(n.index);for(var f=0;f<3;f++){var k=n.edges[f];if(!I(k,o)&&k.IsVertex(s)){o=k;break}}}if(!x){a.boundary.reverse(),n=l;for(var f=0;f<3&&(o=n.edges[f],I(o,p)||!o.IsVertex(s));f++);for(;;){var m=o.PolyIndexIn(n);if(n=o.polys[1-m],_(n))break;a.boundary.push(n.index);for(var f=0;f<3;f++){var k=n.edges[f];if(!I(k,o)&&k.IsVertex(s)){o=k;break}}}}x||(a.boundary.reverse(),a.boundary.push(-1),a.boundary.reverse(),a.boundary.push(-1))}if(r.hull.length>=3){for(var V=new Array,A=r.positions,C=r.hull.length,f=0;f<C;f++){var s=r.hull[f],O=f+1;O>=C&&(O=0);var M=r.hull[O],j=r.vor_polygons[s].edges,F=r.vor_polygons[M].edges,D=q(j,F),o=D[0],E=o.polys[0].index,S=A[s],z=A[M],L=y(z,S),T=[E,r.vor_positions[E],s,S,M,z,L];V.push(T)}for(;V.length>3;){for(var B=V.length,G=new Array,H=new Array,J=0;J<B;J++)H.push(new Array);for(var J=0;J<B;J++){var K=J+1;K>=B&&(K=0);var N=u(i(V[J][6],V[K][6]));c(N,-1),H[J].push(G.length),H[K].push(G.length),G.push(N)}for(var J=0;J<B;J++){var Q=H[J];if(Q.length>=2){for(var R=new Array,U=0;U<Q.length;U++)R.push(v(G[Q[U]],V[J][1]));for(var W=0,X=R[W],Y=0;Y<R.length;Y++){var Z=R[Y];Z<X&&(W=Y,X=Z)}var $=Q[W]}else if(1==Q.length)var $=Q[0];else var $=-1;H[J]=$}for(var rr=new Array,J=0;J<B;J++){var K=J+1;K>=B&&(K=0);var er=J-1;er<0&&(er=B-1);var nr,or=0,Q=H[J];if(Q!=-1){var tr=H[er];Q==tr?or=2:(nr=H[K],Q==nr&&(or=1))}if(0==or)rr.push(V[J]);else if(1==or){var sr=V[J],ir=V[K],N=G[J],ar=sr[0],vr=ir[0],ur=vr!=ar;if(ur){for(var fr=r.vor_positions.length,lr=sr[2],S=sr[3],pr=ir[4],z=ir[5],gr=void 0,dr=void 0,hr=0;hr<B;hr++){for(var cr=v(V[hr][3],N),yr=hr-J;yr<0;)yr+=B;for(;yr>=B;)yr-=B;yr<=2?void 0==gr?gr=cr:cr<gr&&(gr=cr):void 0==dr?dr=cr:cr<dr&&(dr=cr)}ur=gr<dr}if(ur){var L=y(z,S),T=[fr,N,lr,S,pr,z,L];rr.push(T),r.vor_positions.push(N);var _r=sr[4];r.vor_edges.push([ar,fr]),r.vor_edges.push([vr,fr]),r.vor_polygons[_r].boundary.shift();var br=r.vor_polygons[_r].boundary.length;r.vor_polygons[_r].boundary[br-1]=fr,r.vor_polygons[lr].boundary[1]==ar?(r.vor_polygons[lr].boundary.unshift(-1),r.vor_polygons[lr].boundary[1]=fr):(br=r.vor_polygons[lr].boundary.length,r.vor_polygons[lr].boundary[br-2]==ar&&(r.vor_polygons[lr].boundary.push(-1),br=r.vor_polygons[lr].boundary.length,r.vor_polygons[lr].boundary[br-2]=fr)),r.vor_polygons[pr].boundary[1]==vr?(r.vor_polygons[pr].boundary.unshift(-1),r.vor_polygons[pr].boundary[1]=fr):(br=r.vor_polygons[pr].boundary.length,r.vor_polygons[pr].boundary[br-2]==vr&&(r.vor_polygons[pr].boundary.push(-1),br=r.vor_polygons[pr].boundary.length,r.vor_polygons[pr].boundary[br-2]=fr))}else rr.push(sr),rr.push(ir)}}if(rr.length==V.length)break;V=rr}if(2==V.length){if(V[0][0]!=V[1][0]){for(var Ir=[],J=0;J<2;J++){var K=V[J][0];Ir.push(K),K=V[J][2],r.vor_polygons[K].boundary.shift(),r.vor_polygons[K].boundary.pop()}r.vor_edges.push(Ir)}}else if(3==V.length){var xr=V[0][0],wr=V[1][0],mr=V[2][0];if(xr!=wr&&xr!=mr&&wr!=mr){var fr=r.vor_positions.length,kr=V[0][3],Vr=V[1][3],Ar=V[2][3],N=g();h(N,i(kr,Vr)),h(N,i(Vr,Ar)),h(N,i(Ar,kr)),N=u(N),c(N,-1),r.vor_positions.push(N);for(var J=0;J<3;J++){var T=V[J];r.vor_edges.push([T[0],fr]);var s=T[2];r.vor_polygons[s].boundary.shift();var br=r.vor_polygons[s].boundary.length;r.vor_polygons[s].boundary[br-1]=fr}}}}for(var J=0;J<r.vor_polygons.length;J++)a=r.vor_polygons[J],a.boundary.length>=3&&a.boundary[0]>=0&&(n=new w(r.vor_positions,a.boundary.slice(0,3)),n.IsVertexOrderCorrect()||a.boundary.reverse())}else if(2==r.hull.length){var kr=r.positions[r.hull[0]],Vr=r.positions[r.hull[1]],S=g();h(S,kr),h(S,Vr),S=u(S),r.vor_positions.push(S);var z=u(i(kr,Vr));r.vor_positions.push(z);var Pr=d(S);c(Pr,-1),r.vor_positions.push(Pr);var qr=d(z);c(qr,-1),r.vor_positions.push(qr),r.vor_edges.push([0,1,2,3,0]),o=r.edges[0];for(var J=0;J<2;J++){var s=r.hull[J];r.vor_polygons[s]=new Object;var a=r.vor_polygons[s];a.edges=[o],a.triangles=[0],0==J?a.boundary=[0,1,2,3]:1==J&&(a.boundary=[0,3,2,1])}}}else if(3==r.hull.length){var n=r.triangles[0];r.vor_positions.push(n.ccdir);for(var J=0;J<3;J++){var K=J+1;K>=3&&(K=0);var er=J-1;er<0&&(er=2);var Vr=r.positions[r.hull[J]],Ar=r.positions[r.hull[K]],Cr=y(Ar,Vr);r.vor_positions.push(u(i(Cr,n.ccdir))),r.vor_edges.push([0,J+1,4]);var s=r.hull[J];r.vor_polygons[s]=new Object;for(var a=r.vor_polygons[s],Or=r.hull[er],Mr=0;Mr<3;Mr++){var o=r.edges[Mr],jr=P([Or,s],o.verts);if(2==jr.length)break}a.edges=[o],a.triangles=[n],a.boundary=[0,er+1,4,J+1]}var Fr=d(n.ccdir);c(Fr,-1),r.vor_positions.push(Fr)}}function E(r,e){var n=new Object;if(n.positions=r,n.indices=e,n.triangles=[],n.edges=[],n.hull=[],n.vor_positions=[],n.vor_edges=[],n.vor_polygons=new Object,e.length<3)return 2==e.length&&(n.edges.push(new m(e)),n.hull=e),D(n),n;var o=new w(r,e.slice(0,3));o.IsVertexOrderCorrect()||(o=new w(r,[e[0],e[2],e[1]])),n.triangles.push(o);for(var t=new Array(3),s=0;s<3;s++){var i=s+1;i>=3&&(i-=3);var a=e[s],v=e[i],u=[a,v],f=new m(u),l=new k(r,u);l.edge=f,t[s]=l,o.edges[s]=f,f.polys[0]=o,n.edges.push(f)}for(var p=e.slice(0,3),g=t,d=Object,s=0;s<3;s++){var i=s+2;i>=3&&(i-=3);var a=e[s];d[a]=[t[s],t[s+1]]}for(var h=3;h<e.length;h++){var a=e[h];if(!M(n,a)){d[a]=[];for(var c=[],y=[],b=[],I=0;I<p.length;I++){for(var v=p[I],x=new k(r,[a,v]),P=!1,E=0;E<g.length;E++){var S=g[E];if(P=x.intersects(r,S))break}if(!P){var f=new m(x.verts);x.edge=f,A(c,x),A(d[a],x),V(y,a),A(d[v],x),V(y,v)}}V(p,a);for(var I=0;I<g.length;I++){for(var x=g[I],z=[],L=0;L<2;L++){var T=q(d[a],d[x.verts[L]]);0!=T.length&&z.push(T[0])}if(!(z.length<2)){for(var B=-1,L=0;L<2;L++)if(_(x.edge.polys[L])){B=L;break}if(!(B<0)){var G=x.edge.polys[1-B],H=x.verts[0],J=G.VertexIndexIn(H),K=x.verts[1],N=G.VertexIndexIn(K),Q=N-J;if(Q<0&&(Q+=3),1==Q)var R=[a,K,H];else if(2==Q)var R=[a,H,K];var o=new w(r,R);if(o.IsVertexOrderCorrect()){n.triangles.push(o),x.edge.polys[B]=o,o.edges[0]=x.edge,o.edges[1]=z[0].edge,o.edges[2]=z[1].edge,A(b,x);for(var L=0;L<2;L++){var U=z[L];_(U.edge.polys[0])?(U.edge.polys[0]=o,n.edges.push(U.edge)):(U.edge.polys[1]=o,A(b,U))}}}}}for(var I=0;I<c.length;I++)A(g,c[I]);O(g,b);for(var W=[],I=0;I<y.length;I++){var X=y[I];O(d[X],b),0==d[X].length&&W.push(X)}C(p,W)}}return j(n),F(n),D(n),n}function S(r){for(var e=new Array(r.length),n=0;n<e.length;n++)e[n]=n;return E(r,e)}function z(){var r=Math.PI/180,s=function(e){var n=e[0]*r,o=e[1]*r,t=Math.cos(o);return[t*Math.cos(n),t*Math.sin(n),Math.sin(o)]},i=function(e){var n=Math.sqrt(e[0]*e[0]+e[1]*e[1]),o=Math.atan2(e[2],n),t=Math.atan2(e[1],e[0]);return[t/r,o/r]},a=function(r,e){return e.map(function(e){return i(r[e])})},v=t.voronoi()([]),u=v.DT=null,f=v.sites=[],l=v.pos=[],p=function(r){return"object"==typeof r&&"type"in r?o.geoCentroid(r)[0]:0 in r?r[0]:void 0},g=function(r){return"object"==typeof r&&"type"in r?o.geoCentroid(r)[1]:0 in r?r[1]:void 0},d=function(r){return v._hull=v._polygons=v._links=v._triangles=null,"object"==typeof r&&"FeatureCollection"==r.type&&(r=r.features),f=r.map(function(r,e){return r.index=e,r}),l=r.map(function(r){return[p(r),g(r)]}),u=S(l.map(s)),v};return v.links=d.links=function(r){if(r&&d(r),v._links)return v._links;var t=n.map(),s=u.edges.map(function(r,n){t.set(e.extent(r.verts),n);var s={source:f[r.verts[0]],target:f[r.verts[1]],urquhart:!0,length:o.geoDistance(l[r.verts[0]],l[r.verts[1]])};return{type:"Feature",geometry:{type:"LineString",coordinates:[i(u.positions[r.verts[0]]),i(u.positions[r.verts[1]])]},properties:s}});return u.triangles.forEach(function(r){for(var n,o,i=0,a=0,v=0;v<3;v++){o=e.extent([r.verts[v],r.verts[(v+1)%3]]);var u=t.get(o);a=s[u].properties.length,a>i&&(i=a,n=u)}s[n].properties.urquhart=!1}),v._links={type:"FeatureCollection",features:s}},v.triangles=d.triangles=function(r){if(r&&d(r),v._triangles)return v._triangles;var e=u.triangles.map(function(r){return r.spherical=r.verts.map(function(r){return u.positions[r]}).map(i),r.ccdsq<0&&(r.spherical=r.spherical.reverse(),r.ccdsq*=-1),r}).map(function(r){return{type:"Feature",geometry:{type:"Polygon",coordinates:[r.spherical.concat([r.spherical[0]])]},properties:{sites:r.verts.map(function(r){return f[r]}),area:r.vol,circumcenter:i(r.ccdir)}}});return v._triangles={type:"FeatureCollection",features:e}},v.polygons=d.polygons=function(r){if(r&&d(r),v._polygons)return v._polygons;var e=u.indices.map(function(r,e){var n=u.vor_polygons[u.indices[r]],t={};if(void 0==n)t.type="Sphere";else{var s=a(u.vor_positions,n.boundary.concat([n.boundary[0]])),i={type:"Polygon",coordinates:[[l[r],s[0],s[1],l[r]]]};o.geoArea(i)>2*Math.PI+1e-10&&(s=s.reverse()),t.type="Polygon",t.coordinates=[s]}return{type:"Feature",geometry:t,properties:{site:f[r],sitecoordinates:l[r],neighbours:n.edges.map(function(e){return e.verts.filter(function(e){return e!==r})[0]})}}});return v._polygons={type:"FeatureCollection",features:e}},v.hull=d.hull=function(r){if(r&&d(r),v._hull)return v._hull;if(!u.hull.length)return null;var e=u.hull.reverse();return v._hull={type:"Feature",geometry:{type:"Polygon",coordinates:[e.concat([e[0]]).map(function(r){return l[r]})]},properties:{sites:e.map(function(r){return f[r]})}}},v.find=function(r,e,n){var t,s=v.polygons().features,i=v.find.found||0,a=s[i]||s[i=0],u=o.geoDistance([r,e],a.properties.sitecoordinates);do a=s[t=i],i=null,a.properties.neighbours.forEach(function(n){var t=o.geoDistance([r,e],s[n].properties.sitecoordinates);if(t<u)return u=t,void(i=n)});while(null!==i);if(v.find.found=t,!n||u<n*n)return a.properties.site},d.x=function(r){return r?(p=r,d):p},d.y=function(r){return r?(g=r,d):g},d.extent=function(r){return r?d:null},d.size=function(r){return r?d:null},d}w.prototype.copy_vert_info=function(r){this.verts=r.verts,this.dirs=r.dirs,this.vol=r.vol,this.ccdir=r.ccdir,this.ccdsq=r.ccdsq},w.prototype.IsVertexOrderCorrect=function(){return this.vol>=0},w.prototype.IsPointInside=function(r){for(var e=0;e<3;e++)if(s(r,this.dirs[e])<0)return!1;return!0},w.prototype.IsPointInCircumcircle=function(r){return v(this.ccdir,r)<this.ccdsq},w.prototype.IsVertex=function(r){for(var e=0;e<3;e++)if(r==this.verts[e])return!0;return!1},w.prototype.VertexIndexIn=function(r){for(var e=0;e<3;e++)if(r==this.verts[e])return e;return-1},w.prototype.EdgeIndexIn=function(r){for(var e=0;e<3;e++)if(I(this.edges[e],r))return e;return-1},m.prototype.IsVertex=function(r){for(var e=0;e<2;e++)if(r==this.verts[e])return!0;return!1},m.prototype.VertexIndexIn=function(r){for(var e=0;e<2;e++)if(r==this.verts[e])return e;return-1},m.prototype.PolyIndexIn=function(r){for(var e=0;e<2;e++)if(b(this.polys[e],r))return e;return-1},k.prototype.intersects=function(r,e){for(var n=0;n<2;n++)for(var o=0;o<2;o++)if(this.verts[n]==e.verts[o])return!1;var t=u(i(this.direc,e.direc)),a=s(t,this.midpnt)>0,f=s(t,e.midpnt)>0;if(f!=a)return!1;for(var l=[],n=0;n<2;n++){var p=v(t,r[this.verts[n]]);l.push(p)}for(var g=[],n=0;n<2;n++){var p=v(t,r[e.verts[n]]);g.push(p)}var d=x(l[0],l[1]),h=x(g[0],g[1]);if(d<=this.pdst&&h<=e.pdst&&a)return!0;c(t,-1),a=!a;for(var n=0;n<2;n++)l[n]=-l[n],g[n]=-g[n];return d=x(l[0],l[1]),h=x(g[0],g[1]),!!(d<=this.pdst&&h<=e.pdst&&a)},r.geoVoronoi=z,Object.defineProperty(r,"__esModule",{value:!0})});
// https://github.com/Fil/d3-geo-voronoi Version 0.0.3. Copyright 2017 Philippe Riviere.
(function(r,e){"object"==typeof exports&&"undefined"!=typeof module?e(exports,require("d3-array"),require("d3-collection"),require("d3-geo"),require("d3-voronoi")):"function"==typeof define&&define.amd?define(["exports","d3-array","d3-collection","d3-geo","d3-voronoi"],e):e(r.d3=r.d3||{},r.d3,r.d3,r.d3,r.d3)})(this,function(r,e,o,n,t){"use strict";function s(r,e){for(var o=0,n=0;n<3;n++)o+=r[n]*e[n];return o}function i(r,e){for(var o=new Array(3),n=0;n<3;n++){var t=n+1;t>=3&&(t-=3);var s=n+2;s>=3&&(s-=3),o[n]=r[t]*e[s]-r[s]*e[t]}return o}function a(r,e,o){return s(i(r,e),o)}function v(r,e){for(var o=0,n=0,t=0;t<3;t++){var s=e[t]-r[t];o+=s*s;var i=e[t]+r[t];n+=i*i}return Math.sqrt(o)-Math.sqrt(n)}function u(r){for(var e,o=new Array(3),n=0,t=0;t<3;t++){var s=r[t];n+=s*s}e=n>0?1/Math.sqrt(n):0;for(var t=0;t<3;t++)o[t]=e*r[t];return o}function f(r,e,o){return i(r[e],r[o])}function l(r,e,o,n){return a(r[e],r[o],r[n])}function p(r,e,o){return v(r[e],r[o])}function g(){for(var r=new Array(3),e=0;e<3;e++)r[e]=0;return r}function d(r){for(var e=new Array(3),o=0;o<3;o++)e[o]=r[o];return e}function h(r,e){for(var o=0;o<3;o++)r[o]+=e[o]}function c(r,e){for(var o=0;o<3;o++)r[o]*=e}function y(r,e){for(var o=g(),n=0;n<3;n++)o[n]=r[n]-e[n];return o}function _(r){return void 0===r}function b(r,e){if(_(r))return!1;if(_(e))return!1;for(var o=0;o<3;o++)if(r.verts[o]!=e.verts[o])return!1;return!0}function I(r,e){if(_(r))return!1;if(_(e))return!1;for(var o=0;o<2;o++)if(r.verts[o]!=e.verts[o])return!1;return!0}function x(r,e){return e>r?e:r}function w(r,e){this.verts=e,this.edges=new Array(3),this.dirs=new Array(3);for(var o=0;o<3;o++){var n=o+1;n>=3&&(n-=3);var t=o+2;t>=3&&(t-=3),this.dirs[o]=f(r,e[n],e[t])}this.vol=l(r,e[0],e[1],e[2]);for(var o=0;o<3;o++)c(this.dirs[o],1/this.vol);for(var s=g(),o=0;o<3;o++)h(s,this.dirs[o]);this.ccdir=u(s);for(var i=0,o=0;o<3;o++)i+=v(this.ccdir,r[e[o]]);i/=3,this.ccdsq=i}function m(r){this.verts=r,this.polys=new Array(2)}function k(r,e){this.verts=e,this.pdst=p(r,e[0],e[1]),this.direc=u(f(r,e[0],e[1]));var o=g();h(o,r[e[0]]),h(o,r[e[1]]),this.midpnt=u(o)}function V(r,e){for(var o=0;o<r.length;o++)if(e==r[o])return;r.push(e)}function A(r,e){for(var o=0;o<r.length;o++)if(I(r[o],e))return;r.push(e)}function P(r,e){for(var o=[],n=0;n<r.length;n++)for(var t=r[n],s=0;s<e.length;s++){var i=e[s];if(t==i){o.push(t);break}}return o}function q(r,e){for(var o=[],n=0;n<r.length;n++)for(var t=r[n],s=0;s<e.length;s++){var i=e[s];if(I(t,i)){o.push(t);break}}return o}function C(r,e){if(0!=e.length){for(var o=[],n=0;n<r.length;n++){for(var t=r[n],s=!0,i=0;i<e.length;i++){if(e[i]==t){s=!1;break}}s&&o.push(t)}r.splice(0,r.length);for(var a=0;a<o.length;a++)r.push(o[a])}}function O(r,e){if(0!=e.length){for(var o=[],n=0;n<r.length;n++){for(var t=r[n],s=!0,i=0;i<e.length;i++){if(I(t,e[i])){s=!1;break}}s&&o.push(t)}r.splice(0,r.length);for(var a=0;a<o.length;a++)r.push(o[a])}}function M(r,e){for(var o=r.positions,n=o[e],t=r.triangles.length,s=0;s<t;s++){var i=r.triangles[s];if(i.IsPointInside(n)){for(var a=i.edges,v=[],u=0;u<3;u++)v.push(a[u].PolyIndexIn(i));for(var f=Array(3),l=Array(3),u=0;u<3;u++){var p=u+1;p>=3&&(p-=3),f[u]=new w(o,[i.verts[u],i.verts[p],e]),l[u]=new m([i.verts[u],e])}for(var u=0;u<3;u++){var p=u+1;p>=3&&(p-=3),f[u].edges[0]=l[p],f[u].edges[1]=l[u],l[u].polys[0]=f[u],l[p].polys[1]=f[u]}for(var u=0;u<3;u++)for(var g=a[u],d=v[u],h=0;h<3;h++)for(var c=f[h],y=0,_=0;_<2;_++)if(c.IsVertex(g.verts[_])&&y++,2==y){g.polys[d]=c,c.edges[2]=g;break}r.triangles[s]=f[0];for(var u=1;u<3;u++)r.triangles.push(f[u]);for(var u=0;u<3;u++)r.edges.push(l[u]);return!0}}return!1}function j(r){for(var e=r.positions,o=new Array(4),n=0;n<100;n++){for(var t=0,s=0;s<r.edges.length;s++){var i=r.edges[s],a=i.polys;if(!_(a[0])&&!_(a[1])){for(var v=0;v<3;v++){var u=a[0].verts[v];if(!i.IsVertex(u))break}var f=v+1;f>=3&&(f-=3);var l=v+2;l>=3&&(l-=3),o[0]=u,o[1]=a[0].verts[f],o[3]=a[0].verts[l];for(var v=0;v<3;v++){var u=a[1].verts[v];if(!i.IsVertex(u))break}o[2]=u;var p=a[0].IsPointInCircumcircle(e[o[2]]),g=a[1].IsPointInCircumcircle(e[o[0]]);if(p||g){var d=new w(e,[o[0],o[1],o[2]]);if(d.IsVertexOrderCorrect()){var h=new w(e,[o[0],o[2],o[3]]);if(h.IsVertexOrderCorrect()){t++;for(var v=0;v<3;v++){var c=a[0].edges[v];if(!I(c,i)&&c.IsVertex(o[3])){var y=c,b=v;break}}for(var v=0;v<3;v++){var c=a[1].edges[v];if(!I(c,i)&&c.IsVertex(o[1])){var x=c,m=v;break}}var k=y.PolyIndexIn(a[0]),V=x.PolyIndexIn(a[1]);y.polys[k]=a[1],x.polys[V]=a[0],a[0].edges[b]=x,a[1].edges[m]=y,a[0].copy_vert_info(d),a[1].copy_vert_info(h),i.verts=[o[0],o[2]]}}}}}if(0==t)break}}function F(r){for(var e=new Object,o=-1,n=0;n<r.edges.length;n++){var t=r.edges[n];if(_(t.polys[0])){if(_(t.polys[1]))continue;var s=t.polys[1]}else{if(!_(t.polys[1]))continue;var s=t.polys[0]}var i=t.verts[0],a=t.verts[1],v=s.VertexIndexIn(a)-s.VertexIndexIn(i);if(v<0&&(v+=3),1!=v){var u=i;i=a,a=u}e[i]=a,o=i}if(o>=0){for(var f=o,l=[f];;){var p=e[f];if(p==o)break;l.push(p),f=p}r.hull=l}}function D(r){if(1!=r.triangles.length){if(0!=r.triangles.length){for(var e=0;e<r.triangles.length;e++){var o=r.triangles[e];o.index=e,r.vor_positions.push(o.ccdir)}for(var e=0;e<r.edges.length;e++){var n=r.edges[e];if(!_(n.polys[0])&&!_(n.polys[1])){var t=[n.polys[0].index,n.polys[1].index];r.vor_edges.push(t)}}for(var e=0;e<r.indices.length;e++){var s=r.indices[e];r.vor_polygons[s]=new Object;var a=r.vor_polygons[s];a.edges=[],a.triangles=[],a.boundary=[]}for(var e=0;e<r.edges.length;e++)for(var n=r.edges[e],f=0;f<2;f++)r.vor_polygons[n.verts[f]].edges.push(n);for(var e=0;e<r.triangles.length;e++)for(var o=r.triangles[e],f=0;f<3;f++)r.vor_polygons[o.verts[f]].triangles.push(o);for(var e=0;e<r.indices.length;e++){var s=r.indices[e],a=r.vor_polygons[s],l=a.triangles[0],o=l;a.boundary.push(o.index);for(var f=0;f<3;f++){var n=o.edges[f];if(n.IsVertex(s))break}for(var p=n,x=!1;;){var m=n.PolyIndexIn(o);if(o=n.polys[1-m],_(o))break;if(b(o,l)){x=!0;break}a.boundary.push(o.index);for(var f=0;f<3;f++){var k=o.edges[f];if(!I(k,n)&&k.IsVertex(s)){n=k;break}}}if(!x){a.boundary.reverse(),o=l;for(var f=0;f<3&&(n=o.edges[f],I(n,p)||!n.IsVertex(s));f++);for(;;){var m=n.PolyIndexIn(o);if(o=n.polys[1-m],_(o))break;a.boundary.push(o.index);for(var f=0;f<3;f++){var k=o.edges[f];if(!I(k,n)&&k.IsVertex(s)){n=k;break}}}}x||(a.boundary.reverse(),a.boundary.push(-1),a.boundary.reverse(),a.boundary.push(-1))}if(r.hull.length>=3){for(var V=new Array,A=r.positions,C=r.hull.length,f=0;f<C;f++){var s=r.hull[f],O=f+1;O>=C&&(O=0);var M=r.hull[O],j=r.vor_polygons[s].edges,F=r.vor_polygons[M].edges,D=q(j,F),n=D[0],E=n.polys[0].index,S=A[s],z=A[M],L=y(z,S),T=[E,r.vor_positions[E],s,S,M,z,L];V.push(T)}for(;V.length>3;){for(var B=V.length,G=new Array,H=new Array,J=0;J<B;J++)H.push(new Array);for(var J=0;J<B;J++){var K=J+1;K>=B&&(K=0);var N=u(i(V[J][6],V[K][6]));c(N,-1),H[J].push(G.length),H[K].push(G.length),G.push(N)}for(var J=0;J<B;J++){var Q=H[J];if(Q.length>=2){for(var R=new Array,U=0;U<Q.length;U++)R.push(v(G[Q[U]],V[J][1]));for(var W=0,X=R[W],Y=0;Y<R.length;Y++){var Z=R[Y];Z<X&&(W=Y,X=Z)}var $=Q[W]}else if(1==Q.length)var $=Q[0];else var $=-1;H[J]=$}for(var rr=new Array,J=0;J<B;J++){var K=J+1;K>=B&&(K=0);var er=J-1;er<0&&(er=B-1);var or,nr=0,Q=H[J];if(-1!=Q){var tr=H[er];Q==tr?nr=2:(or=H[K],Q==or&&(nr=1))}if(0==nr)rr.push(V[J]);else if(1==nr){var sr=V[J],ir=V[K],N=G[J],ar=sr[0],vr=ir[0],ur=vr!=ar;if(ur){for(var fr=r.vor_positions.length,lr=sr[2],S=sr[3],pr=ir[4],z=ir[5],gr=void 0,dr=void 0,hr=0;hr<B;hr++){for(var cr=v(V[hr][3],N),yr=hr-J;yr<0;)yr+=B;for(;yr>=B;)yr-=B;yr<=2?void 0==gr?gr=cr:cr<gr&&(gr=cr):void 0==dr?dr=cr:cr<dr&&(dr=cr)}ur=gr<dr}if(ur){var L=y(z,S),T=[fr,N,lr,S,pr,z,L];rr.push(T),r.vor_positions.push(N);var _r=sr[4];r.vor_edges.push([ar,fr]),r.vor_edges.push([vr,fr]),r.vor_polygons[_r].boundary.shift();var br=r.vor_polygons[_r].boundary.length;r.vor_polygons[_r].boundary[br-1]=fr,r.vor_polygons[lr].boundary[1]==ar?(r.vor_polygons[lr].boundary.unshift(-1),r.vor_polygons[lr].boundary[1]=fr):(br=r.vor_polygons[lr].boundary.length,r.vor_polygons[lr].boundary[br-2]==ar&&(r.vor_polygons[lr].boundary.push(-1),br=r.vor_polygons[lr].boundary.length,r.vor_polygons[lr].boundary[br-2]=fr)),r.vor_polygons[pr].boundary[1]==vr?(r.vor_polygons[pr].boundary.unshift(-1),r.vor_polygons[pr].boundary[1]=fr):(br=r.vor_polygons[pr].boundary.length,r.vor_polygons[pr].boundary[br-2]==vr&&(r.vor_polygons[pr].boundary.push(-1),br=r.vor_polygons[pr].boundary.length,r.vor_polygons[pr].boundary[br-2]=fr))}else rr.push(sr),rr.push(ir)}}if(rr.length==V.length)break;V=rr}if(2==V.length){if(V[0][0]!=V[1][0]){for(var Ir=[],J=0;J<2;J++){var K=V[J][0];Ir.push(K),K=V[J][2],r.vor_polygons[K].boundary.shift(),r.vor_polygons[K].boundary.pop()}r.vor_edges.push(Ir)}}else if(3==V.length){var xr=V[0][0],wr=V[1][0],mr=V[2][0];if(xr!=wr&&xr!=mr&&wr!=mr){var fr=r.vor_positions.length,kr=V[0][3],Vr=V[1][3],Ar=V[2][3],N=g();h(N,i(kr,Vr)),h(N,i(Vr,Ar)),h(N,i(Ar,kr)),N=u(N),c(N,-1),r.vor_positions.push(N);for(var J=0;J<3;J++){var T=V[J];r.vor_edges.push([T[0],fr]);var s=T[2];r.vor_polygons[s].boundary.shift();var br=r.vor_polygons[s].boundary.length;r.vor_polygons[s].boundary[br-1]=fr}}}}for(var J=0;J<r.vor_polygons.length;J++)a=r.vor_polygons[J],a.boundary.length>=3&&a.boundary[0]>=0&&(o=new w(r.vor_positions,a.boundary.slice(0,3)),o.IsVertexOrderCorrect()||a.boundary.reverse())}else if(2==r.hull.length){var kr=r.positions[r.hull[0]],Vr=r.positions[r.hull[1]],S=g();h(S,kr),h(S,Vr),S=u(S),r.vor_positions.push(S);var z=u(i(kr,Vr));r.vor_positions.push(z);var Pr=d(S);c(Pr,-1),r.vor_positions.push(Pr);var qr=d(z);c(qr,-1),r.vor_positions.push(qr),r.vor_edges.push([0,1,2,3,0]),n=r.edges[0];for(var J=0;J<2;J++){var s=r.hull[J];r.vor_polygons[s]=new Object;var a=r.vor_polygons[s];a.edges=[n],a.triangles=[0],0==J?a.boundary=[0,1,2,3]:1==J&&(a.boundary=[0,3,2,1])}}}else if(3==r.hull.length){var o=r.triangles[0];r.vor_positions.push(o.ccdir);for(var J=0;J<3;J++){var K=J+1;K>=3&&(K=0);var er=J-1;er<0&&(er=2);var Vr=r.positions[r.hull[J]],Ar=r.positions[r.hull[K]],Cr=y(Ar,Vr);r.vor_positions.push(u(i(Cr,o.ccdir))),r.vor_edges.push([0,J+1,4]);var s=r.hull[J];r.vor_polygons[s]=new Object;for(var a=r.vor_polygons[s],Or=r.hull[er],Mr=0;Mr<3;Mr++){var n=r.edges[Mr],jr=P([Or,s],n.verts);if(2==jr.length)break}a.edges=[n],a.triangles=[o],a.boundary=[0,er+1,4,J+1]}var Fr=d(o.ccdir);c(Fr,-1),r.vor_positions.push(Fr)}}function E(r,e){var o=new Object;if(o.positions=r,o.indices=e,o.triangles=[],o.edges=[],o.hull=[],o.vor_positions=[],o.vor_edges=[],o.vor_polygons=new Object,e.length<3)return 2==e.length&&(o.edges.push(new m(e)),o.hull=e),D(o),o;var n=new w(r,e.slice(0,3));n.IsVertexOrderCorrect()||(n=new w(r,[e[0],e[2],e[1]])),o.triangles.push(n);for(var t=new Array(3),s=0;s<3;s++){var i=s+1;i>=3&&(i-=3);var a=e[s],v=e[i],u=[a,v],f=new m(u),l=new k(r,u);l.edge=f,t[s]=l,n.edges[s]=f,f.polys[0]=n,o.edges.push(f)}for(var p=e.slice(0,3),g=t,d=Object,s=0;s<3;s++){var i=s+2;i>=3&&(i-=3);var a=e[s];d[a]=[t[s],t[s+1]]}for(var h=3;h<e.length;h++){var a=e[h];if(!M(o,a)){d[a]=[];for(var c=[],y=[],b=[],I=0;I<p.length;I++){for(var v=p[I],x=new k(r,[a,v]),P=!1,E=0;E<g.length;E++){var S=g[E];if(P=x.intersects(r,S))break}if(!P){var f=new m(x.verts);x.edge=f,A(c,x),A(d[a],x),V(y,a),A(d[v],x),V(y,v)}}V(p,a);for(var I=0;I<g.length;I++){for(var x=g[I],z=[],L=0;L<2;L++){var T=q(d[a],d[x.verts[L]]);0!=T.length&&z.push(T[0])}if(!(z.length<2)){for(var B=-1,L=0;L<2;L++)if(_(x.edge.polys[L])){B=L;break}if(!(B<0)){var G=x.edge.polys[1-B],H=x.verts[0],J=G.VertexIndexIn(H),K=x.verts[1],N=G.VertexIndexIn(K),Q=N-J;if(Q<0&&(Q+=3),1==Q)var R=[a,K,H];else if(2==Q)var R=[a,H,K];var n=new w(r,R);if(n.IsVertexOrderCorrect()){o.triangles.push(n),x.edge.polys[B]=n,n.edges[0]=x.edge,n.edges[1]=z[0].edge,n.edges[2]=z[1].edge,A(b,x);for(var L=0;L<2;L++){var U=z[L];_(U.edge.polys[0])?(U.edge.polys[0]=n,o.edges.push(U.edge)):(U.edge.polys[1]=n,A(b,U))}}}}}for(var I=0;I<c.length;I++)A(g,c[I]);O(g,b);for(var W=[],I=0;I<y.length;I++){var X=y[I];O(d[X],b),0==d[X].length&&W.push(X)}C(p,W)}}return j(o),F(o),D(o),o}function S(r){for(var e=new Array(r.length),o=0;o<e.length;o++)e[o]=o;return E(r,e)}w.prototype.copy_vert_info=function(r){this.verts=r.verts,this.dirs=r.dirs,this.vol=r.vol,this.ccdir=r.ccdir,this.ccdsq=r.ccdsq},w.prototype.IsVertexOrderCorrect=function(){return this.vol>=0},w.prototype.IsPointInside=function(r){for(var e=0;e<3;e++)if(s(r,this.dirs[e])<0)return!1;return!0},w.prototype.IsPointInCircumcircle=function(r){return v(this.ccdir,r)<this.ccdsq},w.prototype.IsVertex=function(r){for(var e=0;e<3;e++)if(r==this.verts[e])return!0;return!1},w.prototype.VertexIndexIn=function(r){for(var e=0;e<3;e++)if(r==this.verts[e])return e;return-1},w.prototype.EdgeIndexIn=function(r){for(var e=0;e<3;e++)if(I(this.edges[e],r))return e;return-1},m.prototype.IsVertex=function(r){for(var e=0;e<2;e++)if(r==this.verts[e])return!0;return!1},m.prototype.VertexIndexIn=function(r){for(var e=0;e<2;e++)if(r==this.verts[e])return e;return-1},m.prototype.PolyIndexIn=function(r){for(var e=0;e<2;e++)if(b(this.polys[e],r))return e;return-1},k.prototype.intersects=function(r,e){for(var o=0;o<2;o++)for(var n=0;n<2;n++)if(this.verts[o]==e.verts[n])return!1;var t=u(i(this.direc,e.direc)),a=s(t,this.midpnt)>0;if(s(t,e.midpnt)>0!=a)return!1;for(var f=[],o=0;o<2;o++){var l=v(t,r[this.verts[o]]);f.push(l)}for(var p=[],o=0;o<2;o++){var l=v(t,r[e.verts[o]]);p.push(l)}var g=x(f[0],f[1]),d=x(p[0],p[1]);if(g<=this.pdst&&d<=e.pdst&&a)return!0;c(t,-1),a=!a;for(var o=0;o<2;o++)f[o]=-f[o],p[o]=-p[o];return g=x(f[0],f[1]),d=x(p[0],p[1]),!!(g<=this.pdst&&d<=e.pdst&&a)};var z=function(){var r=Math.PI/180,s=function(e){var o=e[0]*r,n=e[1]*r,t=Math.cos(n);return[t*Math.cos(o),t*Math.sin(o),Math.sin(n)]},i=function(e){var o=Math.sqrt(e[0]*e[0]+e[1]*e[1]),n=Math.atan2(e[2],o);return[Math.atan2(e[1],e[0])/r,n/r]},a=function(r,e){return e.map(function(e){return i(r[e])})},v=t.voronoi()([]),u=v.DT=null,f=v.sites=[],l=v.pos=[],p=function(r){return"object"==typeof r&&"type"in r?n.geoCentroid(r)[0]:0 in r?r[0]:void 0},g=function(r){return"object"==typeof r&&"type"in r?n.geoCentroid(r)[1]:0 in r?r[1]:void 0},d=function(r){return v._hull=v._polygons=v._links=v._triangles=null,"object"==typeof r&&"FeatureCollection"==r.type&&(r=r.features),f=r.map(function(r,e){return r.index=e,r}),l=r.map(function(r){return[p(r),g(r)]}),u=S(l.map(s)),v};return v.links=d.links=function(r){if(r&&d(r),v._links)return v._links;var t=o.map(),s=u.edges.map(function(r,o){t.set(e.extent(r.verts),o);var s={source:f[r.verts[0]],target:f[r.verts[1]],urquhart:!0,length:n.geoDistance(l[r.verts[0]],l[r.verts[1]])};return{type:"Feature",geometry:{type:"LineString",coordinates:[i(u.positions[r.verts[0]]),i(u.positions[r.verts[1]])]},properties:s}});return u.triangles.forEach(function(r){for(var o,n,i=0,a=0,v=0;v<3;v++){n=e.extent([r.verts[v],r.verts[(v+1)%3]]);var u=t.get(n);a=s[u].properties.length,a>i&&(i=a,o=u)}s[o].properties.urquhart=!1}),v._links={type:"FeatureCollection",features:s}},v.triangles=d.triangles=function(r){if(r&&d(r),v._triangles)return v._triangles;var e=u.triangles.map(function(r){return r.spherical=r.verts.map(function(r){return u.positions[r]}).map(i),r.ccdsq<0&&(r.spherical=r.spherical.reverse(),r.ccdsq*=-1),r}).map(function(r){return{type:"Feature",geometry:{type:"Polygon",coordinates:[r.spherical.concat([r.spherical[0]])]},properties:{sites:r.verts.map(function(r){return f[r]}),area:r.vol,circumcenter:i(r.ccdir)}}});return v._triangles={type:"FeatureCollection",features:e}},v.polygons=d.polygons=function(r){if(r&&d(r),v._polygons)return v._polygons;var e=u.indices.map(function(r,e){var o=u.vor_polygons[u.indices[r]],t={};if(void 0==o)t.type="Sphere";else{var s=a(u.vor_positions,o.boundary.concat([o.boundary[0]])),i={type:"Polygon",coordinates:[[l[r],s[0],s[1],l[r]]]};n.geoArea(i)>2*Math.PI+1e-10&&(s=s.reverse()),t.type="Polygon",t.coordinates=[s]}return{type:"Feature",geometry:t,properties:{site:f[r],sitecoordinates:l[r],neighbours:o.edges.map(function(e){return e.verts.filter(function(e){return e!==r})[0]})}}});return v._polygons={type:"FeatureCollection",features:e}},v.hull=d.hull=function(r){if(r&&d(r),v._hull)return v._hull;if(!u.hull.length)return null;var e=u.hull.reverse();return v._hull={type:"Feature",geometry:{type:"Polygon",coordinates:[e.concat([e[0]]).map(function(r){return l[r]})]},properties:{sites:e.map(function(r){return f[r]})}}},v.find=function(r,e,o){var t,s=v.polygons().features,i=v.find.found||0,a=s[i]||s[i=0],u=n.geoDistance([r,e],a.properties.sitecoordinates);do{a=s[t=i],i=null,a.properties.neighbours.forEach(function(o){var t=n.geoDistance([r,e],s[o].properties.sitecoordinates);if(t<u)return u=t,void(i=o)})}while(null!==i);if(v.find.found=t,!o||u<o*o)return a.properties.site},d.x=function(r){return r?(p=r,d):p},d.y=function(r){return r?(g=r,d):g},d.extent=function(r){return r?d:null},d.size=function(r){return r?d:null},d};r.geoVoronoi=z,Object.defineProperty(r,"__esModule",{value:!0})});

23

package.json
{
"name": "d3-geo-voronoi",
"version": "0.0.2",
"version": "0.0.3",
"description": "Spherical Voronoi Diagram and Delaunay Triangulation",

@@ -13,2 +13,3 @@ "keywords": [

"main": "build/d3-geo-voronoi.js",
"module": "index",
"jsnext:main": "index",

@@ -31,19 +32,19 @@ "homepage": "https://github.com/Fil/d3-geo-voronoi",

"scripts": {
"pretest": "rm -rf build && mkdir build && rollup -g d3-array:d3,d3-collection:d3,d3-geo:d3,d3-voronoi:d3 -f umd -n d3 -o build/d3-geo-voronoi.js -- index.js",
"pretest": "rm -rf build && mkdir build && rollup --banner \"$(preamble)\" -g d3-array:d3,d3-collection:d3,d3-geo:d3,d3-voronoi:d3 -f umd -n d3 -o build/d3-geo-voronoi.js -- index.js",
"test": "tape 'test/**/*-test.js'",
"prepublish": "npm run test && uglifyjs build/d3-geo-voronoi.js -c -m -o build/d3-geo-voronoi.min.js",
"prepublish": "npm run test && uglifyjs --preamble \"$(preamble)\" build/d3-geo-voronoi.js -c negate_iife=false -m -o build/d3-geo-voronoi.min.js",
"postpublish": "zip -j build/d3-geo-voronoi.zip -- LICENSE README.md build/d3-geo-voronoi.js build/d3-geo-voronoi.min.js"
},
"dependencies": {
"d3": "4.0",
"d3-array": "1.0",
"d3-geo": "1.0",
"d3-voronoi": "1.0",
"rollup": "^0.27.1"
"d3": "^4.0",
"d3-array": "^1.0",
"d3-geo": "^1.0",
"d3-voronoi": "^1.0"
},
"devDependencies": {
"rollup": "0.27",
"tape": "4",
"uglify-js": "2"
"package-preamble": "0.1",
"rollup": "0.41",
"tape": "^4",
"uglify-js": "^2"
}
}

4

README.md

@@ -12,3 +12,3 @@ # d3-geo-voronoi

If you use NPM, `npm install d3-geo-voronoi`. Otherwise, download the [latest release](https://github.com/Fil/d3-geo-voronoi/releases/latest).
If you use NPM, `npm install d3-geo-voronoi`. Otherwise, download the [latest release](https://unpkg.com/d3-geo-voronoi).

@@ -107,3 +107,3 @@

- geoVoronoi offers methods to compute the [convex hull](#geo_voronoi_hull), the [Urquhart graph](#geo_voronoi_links), and to find the [nearest neighbour](#geo_voronoi_find) of a point. These can be achieved with the planar Voronoi ([hull](http://bl.ocks.org/mbostock/6f14f7b7f267a85f7cdc), [Urquhart](http://bl.ocks.org/Fil/df20827f817abd161c768fa18dcafcf5), [find](http://bl.ocks.org/Fil/1b7ddbcd71454d685d1259781968aefc)), but are not part of d3-voronoi.
- geoVoronoi offers methods to compute the [convex hull](#geo_voronoi_hull), the [Urquhart graph](#geo_voronoi_links). These can be achieved with the planar Voronoi ([hull](http://bl.ocks.org/mbostock/6f14f7b7f267a85f7cdc), [Urquhart](http://bl.ocks.org/Fil/df20827f817abd161c768fa18dcafcf5), but are not part of d3-voronoi.
SocketSocket SOC 2 Logo

Product

  • Package Alerts
  • Integrations
  • Docs
  • Pricing
  • FAQ
  • Roadmap
  • Changelog

About

Packages

npm

Go

Maven

PyPI

Rubygems

Stay in touch

Get open source security insights delivered straight into your inbox.

  • Terms
  • Privacy
  • Security

Made with ⚡️ by Socket Inc