Huge News!Announcing our $40M Series B led by Abstract Ventures.Learn More →
d3-geo-voronoi
Advanced tools
d3-geo-voronoi - npm Package Compare versions
Comparing version 0.0.6 to 1.0.0
@@ -1,1749 +0,576 @@ | ||
| // https://github.com/Fil/d3-geo-voronoi Version 0.0.6. Copyright 2017 Philippe Riviere. | ||
| // https://github.com/Fil/d3-geo-voronoi Version 1.0.0. Copyright 2018 Philippe Riviere. | ||
| (function (global, factory) { | ||
| typeof exports === 'object' && typeof module !== 'undefined' ? factory(exports, require('d3-array'), require('d3-collection'), require('d3-geo'), require('d3-voronoi')) : | ||
| typeof define === 'function' && define.amd ? define(['exports', 'd3-array', 'd3-collection', 'd3-geo', 'd3-voronoi'], factory) : | ||
| (factory((global.d3 = global.d3 || {}),global.d3,global.d3,global.d3,global.d3)); | ||
| }(this, (function (exports,d3Array,d3Collection,d3Geo,d3Voronoi) { 'use strict'; | ||
| typeof exports === 'object' && typeof module !== 'undefined' ? factory(exports, require('d3-delaunay'), require('d3-geo'), require('d3-array')) : | ||
| typeof define === 'function' && define.amd ? define(['exports', 'd3-delaunay', 'd3-geo', 'd3-array'], factory) : | ||
| (factory((global.d3 = global.d3 || {}),global.d3,global.d3,global.d3)); | ||
| }(this, (function (exports,d3Delaunay,d3Geo,d3Array) { 'use strict'; | ||
| // | ||
| // Copyright (c) 2016, by Loren Petrich | ||
| // | ||
| // Distributed under the terms of the MIT License | ||
| // | ||
| // http://lpetrich.org/ | ||
| // | ||
| var pi = Math.PI; | ||
| // 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: | ||
| var tau = pi * 2; | ||
| // 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. | ||
| var degrees = 180 / pi; | ||
| var radians = pi / 180; | ||
| // 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 crsprd(x,y) | ||
| { | ||
| 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; | ||
| } | ||
| function triple_prd(x,y,z) | ||
| { | ||
| return dotprd(crsprd(x,y),z); | ||
| } | ||
| var cos = Math.cos; | ||
| // 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 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) | ||
| { | ||
| 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; | ||
| } | ||
| function crsprd_ix(Positions,ix,iy) | ||
| { | ||
| return crsprd(Positions[ix],Positions[iy]); | ||
| } | ||
| function triple_prd_ix(Positions,ix,iy,iz) | ||
| { | ||
| return triple_prd(Positions[ix],Positions[iy],Positions[iz]); | ||
| } | ||
| function ptdist_ix(Positions,ix,iy) | ||
| { | ||
| return ptdist(Positions[ix],Positions[iy]); | ||
| } | ||
| var sin = Math.sin; | ||
| var sign = | ||
| Math.sign || | ||
| function(x) { | ||
| return x > 0 ? 1 : x < 0 ? -1 : 0; | ||
| }; | ||
| var sqrt = Math.sqrt; | ||
| // 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 cartesianDot(a, b) { | ||
| return a[0] * b[0] + a[1] * b[1] + a[2] * b[2]; | ||
| } | ||
| // Implements copying | ||
| function vec_copy(x) | ||
| { | ||
| var vec = new Array(3); | ||
| for (var ic=0; ic<3; ic++) | ||
| vec[ic] = x[ic]; | ||
| return vec; | ||
| function cartesianCross(a, b) { | ||
| return [ | ||
| a[1] * b[2] - a[2] * b[1], | ||
| a[2] * b[0] - a[0] * b[2], | ||
| a[0] * b[1] - a[1] * b[0] | ||
| ]; | ||
| } | ||
| // Implements x += y | ||
| function vec_add_to(x,y) | ||
| { | ||
| for (var ic=0; ic<3; ic++) | ||
| x[ic] += y[ic]; | ||
| } | ||
| // TODO return a | ||
| // 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_difference(x,y) | ||
| { | ||
| var diff = zerovec(); | ||
| for (var ic=0; ic<3; ic++) | ||
| diff[ic] = x[ic] - y[ic]; | ||
| return diff; | ||
| function cartesianAdd(a, b) { | ||
| return [a[0] + b[0], a[1] + b[1], a[2] + b[2]]; | ||
| } | ||
| // JavaScript's counterpart of "null" / "None": | ||
| function IsNull(x) | ||
| { | ||
| return (typeof(x) == 'undefined'); | ||
| } | ||
| 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 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; | ||
| } | ||
| // TODO return d | ||
| function max(x,y) | ||
| { | ||
| return (y > x) ? y : x; | ||
| } | ||
| 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 cartesianNormalize(d) { | ||
| var l = sqrt(d[0] * d[0] + d[1] * d[1] + d[2] * d[2]); | ||
| return [d[0] / l, d[1] / l, d[2] / l]; | ||
| } | ||
| // 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; | ||
| }; | ||
| // | ||
| // (c) 2018 Philippe Riviere | ||
| // | ||
| // https://github.com/Fil/ | ||
| // | ||
| // This software is distributed under the terms of the MIT License | ||
| TriangleObject.prototype.IsVertexOrderCorrect = function() | ||
| { | ||
| return this.vol >= 0; | ||
| }; | ||
| // Converts 3D Cartesian to spherical coordinates (degrees). | ||
| function spherical(cartesian) { | ||
| return [ | ||
| Math.atan2(cartesian[1], cartesian[0]) * degrees, | ||
| Math.asin(Math.max(-1, Math.min(1, cartesian[2]))) * degrees | ||
| ]; | ||
| } | ||
| TriangleObject.prototype.IsPointInside = function(p) | ||
| { | ||
| for (var ic=0; ic<3; ic++) | ||
| if (dotprd(p,this.dirs[ic]) < 0) return false; | ||
| return true; | ||
| }; | ||
| // Converts spherical coordinates (degrees) to 3D Cartesian. | ||
| function cartesian(coordinates) { | ||
| var lambda = coordinates[0] * radians, | ||
| phi = coordinates[1] * radians, | ||
| cosphi = Math.cos(phi); | ||
| return [cosphi * Math.cos(lambda), cosphi * Math.sin(lambda), Math.sin(phi)]; | ||
| } | ||
| TriangleObject.prototype.IsPointInCircumcircle = function(p) | ||
| { | ||
| return (ptdist(this.ccdir,p) < this.ccdsq); | ||
| }; | ||
| TriangleObject.prototype.IsVertex = function(ix) | ||
| { | ||
| for (var ic=0; ic<3; ic++) | ||
| if (ix == this.verts[ic]) return true; | ||
| return false; | ||
| }; | ||
| TriangleObject.prototype.VertexIndexIn = function(ix) | ||
| { | ||
| for (var ic=0; ic<3; ic++) | ||
| if (ix == this.verts[ic]) return ic; | ||
| return -1; | ||
| }; | ||
| TriangleObject.prototype.EdgeIndexIn = function(ed) | ||
| { | ||
| for (var ic=0; ic<3; ic++) | ||
| if (EdgesEqual(this.edges[ic], ed)) return ic; | ||
| return -1; | ||
| }; | ||
| function EdgeObject(verts) | ||
| { | ||
| this.verts = verts; | ||
| this.polys = new Array(2); | ||
| function geoDelaunay(points) { | ||
| const delaunay = geo_delaunay_from(points), | ||
| edges = geo_edges(delaunay, points.length), | ||
| triangles = geo_triangles(delaunay, points.length), | ||
| neighbors = geo_neighbors(triangles, points.length), | ||
| find = geo_find(neighbors, points), | ||
| // Voronoi ; could take a center function as an argument | ||
| circumcenters = geo_circumcenters(triangles, points), | ||
| { polygons, centers } = geo_polygons(circumcenters, triangles, points), | ||
| mesh = geo_mesh(polygons), | ||
| hull = geo_hull(triangles,points), | ||
| // Urquhart ; returns a function that takes a distance array as argument. | ||
| urquhart = geo_urquhart(edges, triangles); | ||
| return { | ||
| delaunay, | ||
| edges, | ||
| triangles, | ||
| centers, | ||
| neighbors, | ||
| polygons, | ||
| mesh, | ||
| hull, | ||
| urquhart, | ||
| find | ||
| }; | ||
| } | ||
| EdgeObject.prototype.IsVertex = function(ix) | ||
| { | ||
| for (var ic=0; ic<2; ic++) | ||
| if (ix == this.verts[ic]) return true; | ||
| return false; | ||
| }; | ||
| function geo_find(neighbors, points) { | ||
| return function find(x, y, next) { | ||
| let cell, | ||
| dist, | ||
| found = 0; | ||
| if (next === undefined) next = 0; | ||
| EdgeObject.prototype.VertexIndexIn = function(ix) | ||
| { | ||
| for (var ic=0; ic<2; ic++) | ||
| if (ix == this.verts[ic]) return ic; | ||
| return -1; | ||
| }; | ||
| do { | ||
| cell = next; | ||
| next = null; | ||
| dist = d3Geo.geoDistance([x, y], points[cell]); | ||
| neighbors[cell].forEach(i => { | ||
| let ndist = d3Geo.geoDistance([x, y], points[i]); | ||
| if (ndist < dist) { | ||
| dist = ndist; | ||
| next = i; | ||
| found = i; | ||
| return; | ||
| } | ||
| }); | ||
| } while (next !== null); | ||
| EdgeObject.prototype.PolyIndexIn = function(pl) | ||
| { | ||
| for (var ic=0; ic<2; ic++) | ||
| if (TrianglesEqual(this.polys[ic],pl)) 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); | ||
| return found; | ||
| }; | ||
| } | ||
| // 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++) | ||
| { | ||
| 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; | ||
| }; | ||
| function geo_delaunay_from(points) { | ||
| if (points.length < 2) return {}; | ||
| // 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); | ||
| } | ||
| const r = d3Geo.geoRotation(points[0]), | ||
| projection = d3Geo.geoStereographic() | ||
| .translate([0, 0]) | ||
| .scale(1) | ||
| .rotate(r.invert([180, 0])); | ||
| points = points.map(projection); | ||
| // 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); | ||
| } | ||
| const zeros = [0]; | ||
| let max2 = 1; | ||
| for (let i = 1, n = points.length; i < n; i++) { | ||
| let m = points[i][0] * points[i][0] + points[i][1] * points[i][1]; | ||
| if (isNaN(m)) zeros.push(i); | ||
| if (m > max2) max2 = m; | ||
| } | ||
| const FAR = 1e6 * sqrt(max2); | ||
| // Find the set intersection | ||
| function FindShared(arr1, arr2) | ||
| { | ||
| var resarr = []; | ||
| for (var i1=0; i1<arr1.length; i1++) | ||
| { | ||
| var x1 = arr1[i1]; | ||
| for (var i2=0; i2<arr2.length; i2++) | ||
| { | ||
| var x2 = arr2[i2]; | ||
| if (x1 == x2) | ||
| { | ||
| resarr.push(x1); | ||
| break; | ||
| } | ||
| } | ||
| } | ||
| return resarr; | ||
| } | ||
| zeros.forEach((_, i) => (points[i] = [FAR / 2, 0])); | ||
| // Version for edges | ||
| function FindSharedEdges(arr1, arr2) | ||
| { | ||
| var resarr = []; | ||
| for (var i1=0; i1<arr1.length; i1++) | ||
| { | ||
| var x1 = arr1[i1]; | ||
| for (var i2=0; i2<arr2.length; i2++) | ||
| { | ||
| var x2 = arr2[i2]; | ||
| if (EdgesEqual(x1,x2)) | ||
| { | ||
| resarr.push(x1); | ||
| break; | ||
| } | ||
| } | ||
| } | ||
| return resarr; | ||
| } | ||
| // infinite horizon points | ||
| for (let i = 0; i < 4; i++) { | ||
| points.push([FAR * cos((i / 2) * pi), FAR * sin((i / 2) * pi)]); | ||
| } | ||
| // 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++) | ||
| { | ||
| var x1 = arr1[i1]; | ||
| var AddThisOne = true; | ||
| for (var i2=0; i2<arr2.length; i2++) | ||
| { | ||
| var x2 = arr2[i2]; | ||
| if (x2 == x1) | ||
| { | ||
| 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]); | ||
| } | ||
| const delaunay = d3Delaunay.Delaunay.from(points); | ||
| delaunay.projection = projection; | ||
| // Version for edges | ||
| function FindSetDifferenceEdges(arr1, arr2) | ||
| { | ||
| 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 x2 = arr2[i2]; | ||
| if (EdgesEqual(x1,x2)) | ||
| { | ||
| 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]); | ||
| return delaunay; | ||
| } | ||
| function geo_edges(delaunay, npoints) { | ||
| const geo_edges = [], | ||
| halfedges = delaunay.halfedges, | ||
| triangles = delaunay.triangles, | ||
| seen = {}; | ||
| // 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 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++) | ||
| { | ||
| 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]; | ||
| } | ||
| // 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 newtri = newtris[ict]; | ||
| var numverts = 0; | ||
| for (var iv=0; iv<2; iv++) | ||
| { | ||
| if (newtri.IsVertex(ed.verts[iv])) | ||
| numverts++; | ||
| if (numverts == 2) | ||
| { | ||
| 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; | ||
| } | ||
| } | ||
| // The point was inside no triangle, and thus was not added | ||
| return false; | ||
| } | ||
| if (!halfedges) return geo_edges; | ||
| function ImproveTriangulation(TriSet) | ||
| { | ||
| 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 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 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; | ||
| } | ||
| for (let i = 0, n = halfedges.length; i < n; ++i) { | ||
| const j = halfedges[i]; | ||
| if (j < i) continue; | ||
| let [a, b] = d3Array.extent([triangles[i], triangles[j]]); | ||
| if (b >= npoints && a < npoints) (b = a), (a = 0); | ||
| if (b > 0 && b < npoints && (a > 0 || (!seen[b]++ && (seen[b] = true)))) | ||
| geo_edges.push([a, b]); | ||
| } | ||
| return geo_edges; | ||
| } | ||
| function geo_triangles(delaunay, npoints) { | ||
| if (!delaunay.triangles) return []; | ||
| 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 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]; | ||
| } | ||
| 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; | ||
| } | ||
| 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; | ||
| } | ||
| const triangles = delaunay.triangles.slice().map(d => (d >= npoints ? 0 : d)); | ||
| const geo_triangles = []; | ||
| for (let i = 0, n = triangles.length / 3; i < n; i++) { | ||
| const a = triangles[3 * i], | ||
| b = triangles[3 * i + 1], | ||
| c = triangles[3 * i + 2]; | ||
| if (a !== b && b !== c && c !== a) { | ||
| geo_triangles.push([a, c, b]); | ||
| } | ||
| } | ||
| return geo_triangles; | ||
| } | ||
| // 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) | ||
| { | ||
| // 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 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 ept = vec_copy(tri.ccdir); | ||
| vec_mult_scalar_to(ept,-1); | ||
| TriSet.vor_positions.push(ept); | ||
| } | ||
| return; | ||
| } | ||
| else if (TriSet.triangles.length == 0) | ||
| { | ||
| // 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 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++) | ||
| { | ||
| 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 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; | ||
| 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]; | ||
| // First triangle | ||
| var init_tri = vor_poly.triangles[0]; | ||
| var tri = init_tri; | ||
| vor_poly.boundary.push(tri.index); | ||
| // First edge | ||
| for (var ic=0; ic<3; ic++) | ||
| { | ||
| var edge = tri.edges[ic]; | ||
| if (edge.IsVertex(ix)) | ||
| break; | ||
| } | ||
| var init_edge = edge; | ||
| // The next triangle and edge | ||
| var IsInside = false; | ||
| while(true) | ||
| { | ||
| 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++) | ||
| { | ||
| var next_edge = tri.edges[ic]; | ||
| if (EdgesEqual(next_edge,edge)) continue; | ||
| if (next_edge.IsVertex(ix)) | ||
| { | ||
| edge = next_edge; | ||
| break; | ||
| } | ||
| } | ||
| } | ||
| if (!IsInside) | ||
| { | ||
| vor_poly.boundary.reverse(); | ||
| tri = init_tri; | ||
| // First edge the other way | ||
| for (var ic=0; ic<3; ic++) | ||
| { | ||
| 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 next_edge = tri.edges[ic]; | ||
| if (EdgesEqual(next_edge,edge)) continue; | ||
| if (next_edge.IsVertex(ix)) | ||
| { | ||
| edge = next_edge; | ||
| break; | ||
| } | ||
| } | ||
| } | ||
| } | ||
| // 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++) | ||
| { | ||
| // 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) | ||
| { | ||
| 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 dst = dists[dxi]; | ||
| if (dst < dmin) | ||
| { | ||
| dx = dxi; dmin = dst; | ||
| } | ||
| } | ||
| var ptitscrd = ptitsc[dx]; | ||
| } | ||
| 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) | ||
| { | ||
| var ptitsc_prev = ptitscs[ky]; | ||
| if (ptitsc == ptitsc_prev) | ||
| pstat = 2; | ||
| else | ||
| { | ||
| ptitsc_next = ptitscs[kx]; | ||
| if (ptitsc == ptitsc_next) | ||
| pstat = 1; | ||
| } | ||
| } | ||
| 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) | ||
| { | ||
| 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 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; | ||
| } | ||
| } | ||
| PointOK = (dst_in < dst_out); | ||
| } | ||
| if (PointOK) | ||
| { | ||
| 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[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 | ||
| { | ||
| 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; | ||
| } | ||
| } | ||
| } | ||
| else | ||
| { | ||
| NewVorBdLns.push(VorBdLn0); | ||
| NewVorBdLns.push(VorBdLn1); | ||
| } | ||
| } | ||
| /* | ||
| else if (pstat == 2) | ||
| { | ||
| // Do nothing | ||
| } | ||
| */ | ||
| } | ||
| 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]) | ||
| { | ||
| 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); | ||
| } | ||
| } | ||
| 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 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; | ||
| } | ||
| } | ||
| } | ||
| } | ||
| // 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) | ||
| { | ||
| tri = new TriangleObject(TriSet.vor_positions,vor_poly.boundary.slice(0,3)); | ||
| if (!tri.IsVertexOrderCorrect()) | ||
| vor_poly.boundary.reverse(); | ||
| } | ||
| } | ||
| function geo_circumcenters(triangles, points) { | ||
| // if (!use_centroids) { | ||
| return triangles.map(tri => { | ||
| const c = tri.map(i => points[i]).map(cartesian), | ||
| V = cartesianAdd( | ||
| cartesianAdd(cartesianCross(c[1], c[0]), cartesianCross(c[2], c[1])), | ||
| cartesianCross(c[0], c[2]) | ||
| ); | ||
| return spherical(cartesianNormalize(V)); | ||
| }); | ||
| /*} else { | ||
| return triangles.map(tri => { | ||
| return d3.geoCentroid({ | ||
| type: "MultiPoint", | ||
| coordinates: tri.map(i => points[i]) | ||
| }); | ||
| }); | ||
| }*/ | ||
| } | ||
| function geo_neighbors(triangles, npoints) { | ||
| const neighbors = []; | ||
| triangles.forEach((tri, i) => { | ||
| for (let j = 0; j < 3; j++) { | ||
| const a = tri[j], | ||
| b = tri[(j + 1) % 3]; | ||
| neighbors[a] = neighbors[a] || []; | ||
| neighbors[a].push(b); | ||
| } | ||
| }); | ||
| 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) | ||
| { | ||
| if (Indices.length == 2) | ||
| { | ||
| 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]; | ||
| // If possible, add the point inside | ||
| if (AddPointInside(TriSet, ix)) 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 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); | ||
| } | ||
| // Add the new vertex itself | ||
| AddUnique(BoundaryVerts,ix); | ||
| // Find all the triangles | ||
| for (var j=0; j<BoundaryEdges.length; j++) | ||
| { | ||
| var echk = BoundaryEdges[j]; | ||
| var echks = []; | ||
| 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; | ||
| var empt_indx = -1; | ||
| for (var iv=0; iv<2; iv++) | ||
| { | ||
| if (IsNull(echk.edge.polys[iv])) | ||
| { | ||
| empt_indx = iv; | ||
| break; | ||
| } | ||
| } | ||
| 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); | ||
| // Find the boundary line of this region | ||
| FindConvexHull(TriSet); | ||
| // Find the regions around each point: | ||
| FindVoronoiDiagram(TriSet); | ||
| return TriSet; | ||
| } | ||
| // degenerate cases | ||
| if (triangles.length === 0) { | ||
| if (npoints === 2) (neighbors[0] = [1]), (neighbors[1] = [0]); | ||
| else if (npoints === 1) neighbors[0] = []; | ||
| } | ||
| function FindDelaunayTriangulation(Positions) | ||
| { | ||
| var Indices = new Array(Positions.length); | ||
| for (var i=0; i<Indices.length; i++) | ||
| Indices[i] = i; | ||
| return FindDelaunayTriangulationIndexed(Positions, Indices); | ||
| return neighbors; | ||
| } | ||
| // | ||
| // (c) 2016 Philippe Riviere | ||
| // | ||
| // https://github.com/Fil/ | ||
| // | ||
| // This software is distributed under the terms of the MIT License | ||
| function geo_polygons(circumcenters, triangles, points) { | ||
| const polygons = []; | ||
| var geoVoronoi = function () { | ||
| var radians = Math.PI / 180; | ||
| const centers = circumcenters.slice(); | ||
| 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) | ||
| ]; | ||
| }; | ||
| // supplementary centers for degenerate cases like n = 1,2,3 | ||
| if (triangles.length === 0) { | ||
| if (points.length < 2) return { polygons, centers }; | ||
| if (points.length === 2) { | ||
| // two hemispheres | ||
| const a = cartesian(points[0]), | ||
| b = cartesian(points[1]), | ||
| m = cartesianNormalize(cartesianAdd(a, b)), | ||
| d = cartesianNormalize(cartesianCross(a, b)), | ||
| c = cartesianCross(m, d); | ||
| const poly = [ | ||
| m, | ||
| cartesianCross(m, c), | ||
| cartesianCross(cartesianCross(m, c), c), | ||
| cartesianCross(cartesianCross(cartesianCross(m, c), c), c) | ||
| ] | ||
| .map(spherical) | ||
| .map(supplement); | ||
| return ( | ||
| polygons.push(poly), | ||
| polygons.push(poly.slice().reverse()), | ||
| { polygons, centers } | ||
| ); | ||
| } | ||
| } | ||
| 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]; | ||
| }; | ||
| triangles.forEach((tri, t) => { | ||
| for (let j = 0; j < 3; j++) { | ||
| const a = tri[j], | ||
| b = tri[(j + 1) % 3], | ||
| c = tri[(j + 2) % 3]; | ||
| polygons[a] = polygons[a] || []; | ||
| polygons[a].push([b, c, t, [a, b, c]]); | ||
| } | ||
| }); | ||
| 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 voro = function (data) { | ||
| diagram._hull = diagram._polygons = diagram._links = diagram._triangles = null; | ||
| if (typeof data == 'object' && data.type == 'FeatureCollection') { | ||
| data = data.features; | ||
| // reorder each polygon | ||
| const reordered = polygons.map(poly => { | ||
| const p = [poly[0][2]]; // t | ||
| let k = poly[0][1]; // k = c | ||
| for (let i = 1; i < poly.length; i++) { | ||
| // look for b = k | ||
| for (let j = 0; j < poly.length; j++) { | ||
| if (poly[j][0] == k) { | ||
| k = poly[j][1]; | ||
| p.push(poly[j][2]); | ||
| break; | ||
| } | ||
| 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; | ||
| }; | ||
| } | ||
| } | ||
| diagram.links = voro.links = function (s) { | ||
| if (s) voro(s); | ||
| if (diagram._links) return diagram._links; | ||
| if (p.length > 2) { | ||
| return p; | ||
| } else if (p.length == 2) { | ||
| const R0 = o_midpoint( | ||
| points[poly[0][3][0]], | ||
| points[poly[0][3][1]], | ||
| centers[p[0]] | ||
| ), | ||
| R1 = o_midpoint( | ||
| points[poly[0][3][2]], | ||
| points[poly[0][3][0]], | ||
| centers[p[0]] | ||
| ); | ||
| const i0 = supplement(R0), | ||
| i1 = supplement(R1); | ||
| return [p[0], i1, p[1], i0]; | ||
| } else { | ||
| // I don't think we'll ever reach this(?) | ||
| console && console.warn({ here: "unreachable", poly }); | ||
| } | ||
| }); | ||
| var _index = d3Collection.map(); | ||
| function supplement(point) { | ||
| let f = -1; | ||
| centers.slice(triangles.length, Infinity).forEach((p, i) => { | ||
| if (p[0] === point[0] && p[1] === point[1]) f = i + triangles.length; | ||
| }); | ||
| if (f < 0) (f = centers.length), centers.push(point); | ||
| return f; | ||
| } | ||
| var features = DT.edges.map(function (i, n) { | ||
| return { polygons: reordered, centers }; | ||
| } | ||
| _index.set(d3Array.extent(i.verts), n); | ||
| function o_midpoint(a, b, c) { | ||
| a = cartesian(a); | ||
| b = cartesian(b); | ||
| c = cartesian(c); | ||
| const s = sign(cartesianDot(cartesianCross(b, a), c)); | ||
| return spherical(cartesianNormalize(cartesianAdd(a, b)).map(d => s * d)); | ||
| } | ||
| 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]]) | ||
| }; | ||
| function geo_mesh(polygons) { | ||
| const mesh = []; | ||
| polygons.forEach(poly => { | ||
| if (!poly) return; | ||
| let p = poly[poly.length - 1]; | ||
| for (let q of poly) { | ||
| if (q > p) mesh.push([p, q]); | ||
| p = q; | ||
| } | ||
| }); | ||
| return mesh; | ||
| } | ||
| // add left and right sites (?) | ||
| function geo_urquhart(edges, triangles) { | ||
| return function(distances) { | ||
| const _lengths = {}, | ||
| _urquhart = {}; | ||
| edges.forEach((edge, i) => { | ||
| const u = edge.join("-"); | ||
| _lengths[u] = distances[i]; | ||
| _urquhart[u] = true; | ||
| }); | ||
| // make GeoJSON | ||
| return { | ||
| type: "Feature", | ||
| geometry: { | ||
| type: 'LineString', | ||
| coordinates: [spherical(DT.positions[i.verts[0]]), spherical(DT.positions[i.verts[1]])] | ||
| }, | ||
| properties: properties | ||
| }; | ||
| }); | ||
| triangles.forEach(tri => { | ||
| let l = 0, | ||
| remove = -1; | ||
| for (var j = 0; j < 3; j++) { | ||
| let u = d3Array.extent([tri[j], tri[(j + 1) % 3]]).join("-"); | ||
| if (_lengths[u] > l) { | ||
| l = _lengths[u]; | ||
| remove = u; | ||
| } | ||
| } | ||
| _urquhart[remove] = false; | ||
| }); | ||
| // 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; | ||
| }); | ||
| return edges.map(edge => _urquhart[edge.join("-")]); | ||
| }; | ||
| } | ||
| return diagram._links = { | ||
| type: "FeatureCollection", | ||
| features: features | ||
| }; | ||
| }; | ||
| diagram.triangles = voro.triangles = function (s) { | ||
| if (s) voro(s); | ||
| if (diagram._triangles) return diagram._triangles; | ||
| var features = DT.triangles | ||
| .map(function (t) { | ||
| t.spherical = t.verts.map(function (v) { | ||
| return DT.positions[v]; | ||
| }) | ||
| .map(spherical); | ||
| // correct winding order | ||
| if (t.ccdsq < 0) { | ||
| t.spherical = t.spherical.reverse(); | ||
| t.ccdsq *= -1; | ||
| } | ||
| return t; | ||
| }) | ||
| // 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 | ||
| }; | ||
| function geo_hull(triangles, points) { | ||
| const _hull = {}, | ||
| hull = []; | ||
| triangles.map(tri => { | ||
| const p = { | ||
| type: "Polygon", | ||
| coordinates: [ | ||
| [points[tri[0]], points[tri[1]], points[tri[2]], points[tri[0]]] | ||
| ] | ||
| }; | ||
| diagram.polygons = voro.polygons = function (s) { | ||
| if (s) voro(s); | ||
| if (diagram._polygons) return diagram._polygons; | ||
| if (d3Geo.geoArea(p) > tau) return; | ||
| for (let i = 0; i < 3; i++) { | ||
| let e = [tri[i], tri[(i + 1) % 3]], | ||
| code = `${e[1]}-${e[0]}`; | ||
| if (_hull[code]) delete _hull[code]; | ||
| else _hull[e.join("-")] = true; | ||
| } | ||
| }); | ||
| var features = DT.indices.map(function (i, n) { | ||
| var vor_poly = DT.vor_polygons[DT.indices[i]]; | ||
| var geometry = {}; | ||
| const _index = {}; | ||
| let start; | ||
| Object.keys(_hull).forEach(e => { | ||
| e = e.split("-").map(Number); | ||
| _index[e[0]] = e[1]; | ||
| start = e[0]; | ||
| }); | ||
| if (vor_poly == undefined) { | ||
| geometry.type = "Sphere"; | ||
| } else { | ||
| var line = mapline(DT.vor_positions, | ||
| vor_poly.boundary.concat([vor_poly.boundary[0]]) | ||
| ); | ||
| if (start === undefined) return hull; | ||
| // 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(); | ||
| } | ||
| let next = start; | ||
| do { | ||
| hull.push(next); | ||
| next = _index[next]; | ||
| } while (next !== start); | ||
| geometry.type = "Polygon"; | ||
| geometry.coordinates = [line]; | ||
| } | ||
| return hull; | ||
| } | ||
| 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]; | ||
| }) | ||
| } | ||
| }; | ||
| }); | ||
| // | ||
| // (c) 2018 Philippe Riviere | ||
| // | ||
| // https://github.com/Fil/ | ||
| // | ||
| // This software is distributed under the terms of the MIT License | ||
| return diagram._polygons = { | ||
| type: "FeatureCollection", | ||
| features: features | ||
| }; | ||
| }; | ||
| function geoVoronoi(data) { | ||
| const v = function(data) { | ||
| v.delaunay = null; | ||
| v._data = data; | ||
| diagram.hull = voro.hull = function (s) { | ||
| if (s) voro(s); | ||
| if (diagram._hull) return diagram._hull; | ||
| if (typeof v._data === "object" && v._data.type === "FeatureCollection") { | ||
| v._data = v._data.features; | ||
| } | ||
| if (typeof v._data === "object") { | ||
| v.points = v._data.map(i => [v._vx(i), v._vy(i)]); | ||
| v.delaunay = geoDelaunay(v.points); | ||
| } | ||
| return v; | ||
| }; | ||
| if (!DT.hull.length) { | ||
| return null; // What is a null GeoJSON? | ||
| } | ||
| v._vx = function(d) { | ||
| if (typeof d == "object" && "type" in d) { | ||
| return d3Geo.geoCentroid(d)[0]; | ||
| } | ||
| if (0 in d) return d[0]; | ||
| }; | ||
| v._vy = function(d) { | ||
| if (typeof d == "object" && "type" in d) { | ||
| return d3Geo.geoCentroid(d)[1]; | ||
| } | ||
| if (1 in d) return d[1]; | ||
| }; | ||
| // seems that DT.hull is always clockwise | ||
| var hull = DT.hull.reverse(); | ||
| v.x = function(f) { | ||
| if (!f) return v._vx; | ||
| v._vx = f; | ||
| return v; | ||
| }; | ||
| v.y = function(f) { | ||
| if (!f) return v._vy; | ||
| v._vy = f; | ||
| return v; | ||
| }; | ||
| // make GeoJSON | ||
| return diagram._hull = { | ||
| type: "Feature", | ||
| geometry: { | ||
| type: "Polygon", | ||
| coordinates: [hull.concat([hull[0]]).map(function (i) { | ||
| return pos[i]; | ||
| })] | ||
| v.polygons = function(data) { | ||
| if (data !== undefined) { | ||
| v(data); | ||
| } | ||
| if (!v.delaunay) return false; | ||
| if (v._data.length === 0) return null; | ||
| if (v._data.length === 1) return { type: "Sphere" }; | ||
| return { | ||
| type: "FeatureCollection", | ||
| features: v.delaunay.polygons.map((poly, i) => ({ | ||
| type: "Feature", | ||
| geometry: !poly | ||
| ? null | ||
| : { | ||
| type: "Polygon", | ||
| coordinates: [[...poly, poly[0]].map(i => v.delaunay.centers[i])] | ||
| }, | ||
| properties: { | ||
| sites: hull.map(function (i) { | ||
| return sites[i]; | ||
| }) | ||
| } | ||
| }; | ||
| properties: { | ||
| site: v._data[i], | ||
| sitecoordinates: v.points[i], | ||
| neighbours: v.delaunay.neighbors[i] // not part of the public API | ||
| } | ||
| })) | ||
| }; | ||
| }; | ||
| v.triangles = function(data) { | ||
| if (data !== undefined) { | ||
| v(data); | ||
| } | ||
| if (!v.delaunay) return false; | ||
| 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]; | ||
| 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; | ||
| } | ||
| }); | ||
| } while (next !== null); | ||
| diagram.find.found = i; | ||
| if (!radius || dist < radius * radius) return cell.properties.site; | ||
| return { | ||
| type: "FeatureCollection", | ||
| features: v.delaunay.triangles | ||
| .map((tri, i) => ({ | ||
| type: "Feature", | ||
| properties: { | ||
| circumcenter: v.delaunay.centers[i] | ||
| }, | ||
| geometry: { | ||
| type: "Polygon", | ||
| coordinates: [ | ||
| [ | ||
| v.points[tri[0]], | ||
| v.points[tri[1]], | ||
| v.points[tri[2]], | ||
| v.points[tri[0]] | ||
| ] | ||
| ] | ||
| } | ||
| })) | ||
| .filter(d => d3Geo.geoArea(d) <= tau) | ||
| }; | ||
| }; | ||
| voro.x = function (f) { | ||
| if (!f) return x; | ||
| x = f; | ||
| return voro; | ||
| v.links = function(data) { | ||
| if (data !== undefined) { | ||
| v(data); | ||
| } | ||
| if (!v.delaunay) return false; | ||
| const _distances = v.delaunay.edges.map(e => | ||
| d3Geo.geoDistance(v.points[e[0]], v.points[e[1]]) | ||
| ), | ||
| _urquart = v.delaunay.urquhart(_distances); | ||
| return { | ||
| type: "FeatureCollection", | ||
| features: v.delaunay.edges.map((e, i) => ({ | ||
| type: "Feature", | ||
| properties: { | ||
| source: v._data[e[0]], | ||
| target: v._data[e[1]], | ||
| length: _distances[i], | ||
| urquhart: !!_urquart[i] | ||
| }, | ||
| geometry: { | ||
| type: "LineString", | ||
| coordinates: [v.points[e[0]], v.points[e[1]]] | ||
| } | ||
| })) | ||
| }; | ||
| 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; | ||
| v._found = undefined; | ||
| v.find = function(x, y, radius) { | ||
| v._found = v.delaunay.find(x, y, v._found); | ||
| if (!radius || d3Geo.geoDistance([x, y], v.points[v._found]) < radius) | ||
| return v._found; | ||
| }; | ||
| }; | ||
| v.hull = function(data) { | ||
| if (data !== undefined) { | ||
| v(data); | ||
| } | ||
| const hull = v.delaunay.hull, points = v.points; | ||
| return hull.length === 0 | ||
| ? null | ||
| : { | ||
| type: "Polygon", | ||
| coordinates: [[...hull.map(i => points[i]), points[hull[0]]]] | ||
| }; | ||
| }; | ||
| return data ? v(data) : v; | ||
| } | ||
| exports.geoDelaunay = geoDelaunay; | ||
| exports.geoVoronoi = geoVoronoi; | ||
@@ -1750,0 +577,0 @@ |
@@ -1,1 +0,1 @@ | ||
| (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 u(r,e,o){return s(i(r,e),o)}function a(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 l(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(t=0;t<3;t++)o[t]=e*r[t];return o}function f(r,e,o){return i(r[e],r[o])}function v(r,e,o,n){return u(r[e],r[o],r[n])}function p(r,e,o){return a(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(s=0;s<3;s++){var o=s+1;o>=3&&(o-=3);var n=s+2;n>=3&&(n-=3),this.dirs[s]=f(r,e[o],e[n])}this.vol=v(r,e[0],e[1],e[2]);for(s=0;s<3;s++)c(this.dirs[s],1/this.vol);for(var t=g(),s=0;s<3;s++)h(t,this.dirs[s]);this.ccdir=l(t);for(var i=0,s=0;s<3;s++)i+=a(this.ccdir,r[e[s]]);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=l(f(r,e[0],e[1]));var o=g();h(o,r[e[0]]),h(o,r[e[1]]),this.midpnt=l(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++)if(t==e[s]){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++)if(I(t,e[s])){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 u=0;u<o.length;u++)r.push(o[u])}}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 u=0;u<o.length;u++)r.push(o[u])}}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 u=i.edges,a=[],l=0;l<3;l++)a.push(u[l].PolyIndexIn(i));for(var f=Array(3),v=Array(3),l=0;l<3;l++)(p=l+1)>=3&&(p-=3),f[l]=new w(o,[i.verts[l],i.verts[p],e]),v[l]=new m([i.verts[l],e]);for(l=0;l<3;l++){var p=l+1;p>=3&&(p-=3),f[l].edges[0]=v[p],f[l].edges[1]=v[l],v[l].polys[0]=f[l],v[p].polys[1]=f[l]}for(l=0;l<3;l++)for(var g=u[l],d=a[l],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(l=1;l<3;l++)r.triangles.push(f[l]);for(l=0;l<3;l++)r.edges.push(v[l]);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],u=i.polys;if(!_(u[0])&&!_(u[1])){for(y=0;y<3;y++){f=u[0].verts[y];if(!i.IsVertex(f))break}var a=y+1;a>=3&&(a-=3);var l=y+2;l>=3&&(l-=3),o[0]=f,o[1]=u[0].verts[a],o[3]=u[0].verts[l];for(y=0;y<3;y++){var f=u[1].verts[y];if(!i.IsVertex(f))break}o[2]=f;var v=u[0].IsPointInCircumcircle(e[o[2]]),p=u[1].IsPointInCircumcircle(e[o[0]]);if(v||p){var g=new w(e,[o[0],o[1],o[2]]);if(g.IsVertexOrderCorrect()){var d=new w(e,[o[0],o[2],o[3]]);if(d.IsVertexOrderCorrect()){t++;for(y=0;y<3;y++)if(!I(b=u[0].edges[y],i)&&b.IsVertex(o[3])){var h=b,c=y;break}for(var y=0;y<3;y++){var b=u[1].edges[y];if(!I(b,i)&&b.IsVertex(o[1])){var x=b,m=y;break}}var k=h.PolyIndexIn(u[0]),V=x.PolyIndexIn(u[1]);h.polys[k]=u[1],x.polys[V]=u[0],u[0].edges[c]=x,u[1].edges[m]=h,u[0].copy_vert_info(g),u[1].copy_vert_info(d),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;s=t.polys[1]}else{if(!_(t.polys[1]))continue;var s=t.polys[0]}var i=t.verts[0],u=t.verts[1],a=s.VertexIndexIn(u)-s.VertexIndexIn(i);if(a<0&&(a+=3),1!=a){var l=i;i=u,u=l}e[i]=u,o=i}if(o>=0){for(var f=o,v=[f];;){var p=e[f];if(p==o)break;v.push(p),f=p}r.hull=v}}function D(r){if(1!=r.triangles.length){if(0!=r.triangles.length){for(s=0;s<r.triangles.length;s++)(t=r.triangles[s]).index=s,r.vor_positions.push(t.ccdir);for(s=0;s<r.edges.length;s++)if(!_((o=r.edges[s]).polys[0])&&!_(o.polys[1])){var e=[o.polys[0].index,o.polys[1].index];r.vor_edges.push(e)}for(s=0;s<r.indices.length;s++){u=r.indices[s];r.vor_polygons[u]=new Object,(kr=r.vor_polygons[u]).edges=[],kr.triangles=[],kr.boundary=[]}for(s=0;s<r.edges.length;s++)for(var o=r.edges[s],n=0;n<2;n++)r.vor_polygons[o.verts[n]].edges.push(o);for(s=0;s<r.triangles.length;s++)for(var t=r.triangles[s],n=0;n<3;n++)r.vor_polygons[t.verts[n]].triangles.push(t);for(var s=0;s<r.indices.length;s++){var u=r.indices[s],f=(kr=r.vor_polygons[u]).triangles[0],t=f;kr.boundary.push(t.index);for(n=0;n<3&&!(o=t.edges[n]).IsVertex(u);n++);for(var v=o,p=!1;;){x=o.PolyIndexIn(t);if(t=o.polys[1-x],_(t))break;if(b(t,f)){p=!0;break}kr.boundary.push(t.index);for(n=0;n<3;n++)if(!I(m=t.edges[n],o)&&m.IsVertex(u)){o=m;break}}if(!p){kr.boundary.reverse(),t=f;for(n=0;n<3&&(o=t.edges[n],I(o,v)||!o.IsVertex(u));n++);for(;;){var x=o.PolyIndexIn(t);if(t=o.polys[1-x],_(t))break;kr.boundary.push(t.index);for(n=0;n<3;n++){var m=t.edges[n];if(!I(m,o)&&m.IsVertex(u)){o=m;break}}}}p||(kr.boundary.reverse(),kr.boundary.push(-1),kr.boundary.reverse(),kr.boundary.push(-1))}if(r.hull.length>=3){for(var k=new Array,V=r.positions,A=r.hull.length,n=0;n<A;n++){var u=r.hull[n],C=n+1;C>=A&&(C=0);var O=r.hull[C],M=(o=q(r.vor_polygons[u].edges,r.vor_polygons[O].edges)[0]).polys[0].index,j=V[u],F=y(sr=V[O],j),D=[M,r.vor_positions[M],u,j,O,sr,F];k.push(D)}for(;k.length>3;){for(var E=k.length,S=new Array,z=new Array,L=0;L<E;L++)z.push(new Array);for(L=0;L<E;L++)(gr=L+1)>=E&&(gr=0),c(Z=l(i(k[L][6],k[gr][6])),-1),z[L].push(S.length),z[gr].push(S.length),S.push(Z);for(L=0;L<E;L++){if((W=z[L]).length>=2){for(var T=new Array,B=0;B<W.length;B++)T.push(a(S[W[B]],k[L][1]));for(var G=0,H=T[G],J=0;J<T.length;J++){var K=T[J];K<H&&(G=J,H=K)}N=W[G]}else if(1==W.length)N=W[0];else var N=-1;z[L]=N}for(var Q=new Array,L=0;L<E;L++){(gr=L+1)>=E&&(gr=0);var R=L-1;R<0&&(R=E-1);var U=0,W=z[L];if(-1!=W&&(W==z[R]?U=2:W==z[gr]&&(U=1)),0==U)Q.push(k[L]);else if(1==U){var X=k[L],Y=k[gr],Z=S[L],$=X[0],rr=Y[0],er=rr!=$;if(er){for(var or=r.vor_positions.length,nr=X[2],j=X[3],tr=Y[4],sr=Y[5],ir=void 0,ur=void 0,ar=0;ar<E;ar++){for(var lr=a(k[ar][3],Z),fr=ar-L;fr<0;)fr+=E;for(;fr>=E;)fr-=E;fr<=2?void 0==ir?ir=lr:lr<ir&&(ir=lr):void 0==ur?ur=lr:lr<ur&&(ur=lr)}er=ir<ur}if(er){D=[or,Z,nr,j,tr,sr,F=y(sr,j)];Q.push(D),r.vor_positions.push(Z);var vr=X[4];r.vor_edges.push([$,or]),r.vor_edges.push([rr,or]),r.vor_polygons[vr].boundary.shift();Ir=r.vor_polygons[vr].boundary.length;r.vor_polygons[vr].boundary[Ir-1]=or,r.vor_polygons[nr].boundary[1]==$?(r.vor_polygons[nr].boundary.unshift(-1),r.vor_polygons[nr].boundary[1]=or):(Ir=r.vor_polygons[nr].boundary.length,r.vor_polygons[nr].boundary[Ir-2]==$&&(r.vor_polygons[nr].boundary.push(-1),Ir=r.vor_polygons[nr].boundary.length,r.vor_polygons[nr].boundary[Ir-2]=or)),r.vor_polygons[tr].boundary[1]==rr?(r.vor_polygons[tr].boundary.unshift(-1),r.vor_polygons[tr].boundary[1]=or):(Ir=r.vor_polygons[tr].boundary.length,r.vor_polygons[tr].boundary[Ir-2]==rr&&(r.vor_polygons[tr].boundary.push(-1),Ir=r.vor_polygons[tr].boundary.length,r.vor_polygons[tr].boundary[Ir-2]=or))}else Q.push(X),Q.push(Y)}}if(Q.length==k.length)break;k=Q}if(2==k.length){if(k[0][0]!=k[1][0]){for(var pr=[],L=0;L<2;L++){var gr=k[L][0];pr.push(gr),gr=k[L][2],r.vor_polygons[gr].boundary.shift(),r.vor_polygons[gr].boundary.pop()}r.vor_edges.push(pr)}}else if(3==k.length){var dr=k[0][0],hr=k[1][0],cr=k[2][0];if(dr!=hr&&dr!=cr&&hr!=cr){var or=r.vor_positions.length,yr=k[0][3],_r=k[1][3],br=k[2][3];h(Z=g(),i(yr,_r)),h(Z,i(_r,br)),h(Z,i(br,yr)),c(Z=l(Z),-1),r.vor_positions.push(Z);for(L=0;L<3;L++){D=k[L];r.vor_edges.push([D[0],or]);u=D[2];r.vor_polygons[u].boundary.shift();var Ir=r.vor_polygons[u].boundary.length;r.vor_polygons[u].boundary[Ir-1]=or}}}}for(L=0;L<r.vor_polygons.length;L++)(kr=r.vor_polygons[L]).boundary.length>=3&&kr.boundary[0]>=0&&((t=new w(r.vor_positions,kr.boundary.slice(0,3))).IsVertexOrderCorrect()||kr.boundary.reverse())}else if(2==r.hull.length){var yr=r.positions[r.hull[0]],_r=r.positions[r.hull[1]];h(j=g(),yr),h(j,_r),j=l(j),r.vor_positions.push(j);sr=l(i(yr,_r));r.vor_positions.push(sr);var xr=d(j);c(xr,-1),r.vor_positions.push(xr);var wr=d(sr);c(wr,-1),r.vor_positions.push(wr),r.vor_edges.push([0,1,2,3,0]),o=r.edges[0];for(L=0;L<2;L++){u=r.hull[L];r.vor_polygons[u]=new Object,(kr=r.vor_polygons[u]).edges=[o],kr.triangles=[0],0==L?kr.boundary=[0,1,2,3]:1==L&&(kr.boundary=[0,3,2,1])}}}else if(3==r.hull.length){t=r.triangles[0];r.vor_positions.push(t.ccdir);for(L=0;L<3;L++){(gr=L+1)>=3&&(gr=0),(R=L-1)<0&&(R=2);var _r=r.positions[r.hull[L]],mr=y(br=r.positions[r.hull[gr]],_r);r.vor_positions.push(l(i(mr,t.ccdir))),r.vor_edges.push([0,L+1,4]);u=r.hull[L];r.vor_polygons[u]=new Object;for(var kr=r.vor_polygons[u],Vr=r.hull[R],Ar=0;Ar<3&&2!=P([Vr,u],(o=r.edges[Ar]).verts).length;Ar++);kr.edges=[o],kr.triangles=[t],kr.boundary=[0,R+1,4,L+1]}var Pr=d(t.ccdir);c(Pr,-1),r.vor_positions.push(Pr)}}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++){(p=s+1)>=3&&(p-=3);var i=[d=e[s],I=e[p]],u=new m(i),a=new k(r,i);a.edge=u,t[s]=a,n.edges[s]=u,u.polys[0]=n,o.edges.push(u)}for(var l=e.slice(0,3),f=t,v=Object,s=0;s<3;s++){var p=s+2;p>=3&&(p-=3),v[d=e[s]]=[t[s],t[s+1]]}for(var g=3;g<e.length;g++){var d=e[g];if(!M(o,d)){v[d]=[];for(var h=[],c=[],y=[],b=0;b<l.length;b++){for(var I=l[b],x=new k(r,[d,I]),P=!1,E=0;E<f.length;E++){var S=f[E];if(P=x.intersects(r,S))break}if(!P){u=new m(x.verts);x.edge=u,A(h,x),A(v[d],x),V(c,d),A(v[I],x),V(c,I)}}V(l,d);for(b=0;b<f.length;b++){for(var x=f[b],z=[],L=0;L<2;L++){var T=q(v[d],v[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)-J;if(N<0&&(N+=3),1==N)Q=[d,K,H];else if(2==N)var Q=[d,H,K];if((n=new w(r,Q)).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(y,x);for(L=0;L<2;L++){var R=z[L];_(R.edge.polys[0])?(R.edge.polys[0]=n,o.edges.push(R.edge)):(R.edge.polys[1]=n,A(y,R))}}}}}for(b=0;b<h.length;b++)A(f,h[b]);O(f,y);for(var U=[],b=0;b<c.length;b++){var W=c[b];O(v[W],y),0==v[W].length&&U.push(W)}C(l,U)}}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 a(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(f=0;f<2;f++)for(var o=0;o<2;o++)if(this.verts[f]==e.verts[o])return!1;var n=l(i(this.direc,e.direc)),t=s(n,this.midpnt)>0;if(s(n,e.midpnt)>0!=t)return!1;for(var u=[],f=0;f<2;f++){p=a(n,r[this.verts[f]]);u.push(p)}for(var v=[],f=0;f<2;f++){var p=a(n,r[e.verts[f]]);v.push(p)}var g=x(u[0],u[1]),d=x(v[0],v[1]);if(g<=this.pdst&&d<=e.pdst&&t)return!0;c(n,-1),t=!t;for(f=0;f<2;f++)u[f]=-u[f],v[f]=-v[f];return g=x(u[0],u[1]),d=x(v[0],v[1]),!!(g<=this.pdst&&d<=e.pdst&&t)};r.geoVoronoi=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]},u=function(r,e){return e.map(function(e){return i(r[e])})},a=t.voronoi()([]),l=a.DT=null,f=a.sites=[],v=a.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 a._hull=a._polygons=a._links=a._triangles=null,"object"==typeof r&&"FeatureCollection"==r.type&&(r=r.features),f=r.map(function(r,e){return r.index=e,r}),v=r.map(function(r){return[p(r),g(r)]}),l=S(v.map(s)),a};return a.links=d.links=function(r){if(r&&d(r),a._links)return a._links;var t=o.map(),s=l.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(v[r.verts[0]],v[r.verts[1]])};return{type:"Feature",geometry:{type:"LineString",coordinates:[i(l.positions[r.verts[0]]),i(l.positions[r.verts[1]])]},properties:s}});return l.triangles.forEach(function(r){for(var o,n,i=0,u=0,a=0;a<3;a++){n=e.extent([r.verts[a],r.verts[(a+1)%3]]);var l=t.get(n);(u=s[l].properties.length)>i&&(i=u,o=l)}s[o].properties.urquhart=!1}),a._links={type:"FeatureCollection",features:s}},a.triangles=d.triangles=function(r){if(r&&d(r),a._triangles)return a._triangles;var e=l.triangles.map(function(r){return r.spherical=r.verts.map(function(r){return l.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 a._triangles={type:"FeatureCollection",features:e}},a.polygons=d.polygons=function(r){if(r&&d(r),a._polygons)return a._polygons;var e=l.indices.map(function(r,e){var o=l.vor_polygons[l.indices[r]],t={};if(void 0==o)t.type="Sphere";else{var s=u(l.vor_positions,o.boundary.concat([o.boundary[0]])),i={type:"Polygon",coordinates:[[v[r],s[0],s[1],v[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:v[r],neighbours:o.edges.map(function(e){return e.verts.filter(function(e){return e!==r})[0]})}}});return a._polygons={type:"FeatureCollection",features:e}},a.hull=d.hull=function(r){if(r&&d(r),a._hull)return a._hull;if(!l.hull.length)return null;var e=l.hull.reverse();return a._hull={type:"Feature",geometry:{type:"Polygon",coordinates:[e.concat([e[0]]).map(function(r){return v[r]})]},properties:{sites:e.map(function(r){return f[r]})}}},a.find=function(r,e,o){var t,s=a.polygons().features,i=a.find.found||0,u=s[i]||s[i=0],l=n.geoDistance([r,e],u.properties.sitecoordinates);do{u=s[t=i],i=null,u.properties.neighbours.forEach(function(o){var t=n.geoDistance([r,e],s[o].properties.sitecoordinates);if(t<l)return l=t,void(i=o)})}while(null!==i);if(a.find.found=t,!o||l<o*o)return u.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},Object.defineProperty(r,"__esModule",{value:!0})}); | ||
| (function(e,t){"object"==typeof exports&&"undefined"!=typeof module?t(exports,require("d3-delaunay"),require("d3-geo"),require("d3-array")):"function"==typeof define&&define.amd?define(["exports","d3-delaunay","d3-geo","d3-array"],t):t(e.d3=e.d3||{},e.d3,e.d3,e.d3)})(this,function(e,t,n,o){"use strict";var r=Math.PI,a=2*r,u=180/r,i=r/180,l=Math.cos,s=Math.sin,c=Math.sign||function(e){return e>0?1:e<0?-1:0},f=Math.sqrt;function p(e,t){return[e[1]*t[2]-e[2]*t[1],e[2]*t[0]-e[0]*t[2],e[0]*t[1]-e[1]*t[0]]}function d(e,t){return[e[0]+t[0],e[1]+t[1],e[2]+t[2]]}function h(e){var t=f(e[0]*e[0]+e[1]*e[1]+e[2]*e[2]);return[e[0]/t,e[1]/t,e[2]/t]}function g(e){return[Math.atan2(e[1],e[0])*u,Math.asin(Math.max(-1,Math.min(1,e[2])))*u]}function y(e){var t=e[0]*i,n=e[1]*i,o=Math.cos(n);return[o*Math.cos(t),o*Math.sin(t),Math.sin(n)]}function m(e){const u=function(e){if(e.length<2)return{};const o=n.geoRotation(e[0]),a=n.geoStereographic().translate([0,0]).scale(1).rotate(o.invert([180,0])),u=[0];let i=1;for(let t=1,n=(e=e.map(a)).length;t<n;t++){let n=e[t][0]*e[t][0]+e[t][1]*e[t][1];isNaN(n)&&u.push(t),n>i&&(i=n)}const c=1e6*f(i);u.forEach((t,n)=>e[n]=[c/2,0]);for(let t=0;t<4;t++)e.push([c*l(t/2*r),c*s(t/2*r)]);const p=t.Delaunay.from(e);return p.projection=a,p}(e),i=function(e,t){const n=[],r=e.halfedges,a=e.triangles,u={};if(!r)return n;for(let e=0,i=r.length;e<i;++e){const i=r[e];if(i<e)continue;let[l,s]=o.extent([a[e],a[i]]);s>=t&&l<t&&(s=l,l=0),s>0&&s<t&&(l>0||!u[s]++&&(u[s]=!0))&&n.push([l,s])}return n}(u,e.length),c=function(e,t){if(!e.triangles)return[];const n=e.triangles.slice().map(e=>e>=t?0:e),o=[];for(let e=0,t=n.length/3;e<t;e++){const t=n[3*e],r=n[3*e+1],a=n[3*e+2];t!==r&&r!==a&&a!==t&&o.push([t,a,r])}return o}(u,e.length),m=function(e,t){const n=[];e.forEach((e,t)=>{for(let t=0;t<3;t++){const o=e[t],r=e[(t+1)%3];n[o]=n[o]||[],n[o].push(r)}}),0===e.length&&(2===t?(n[0]=[1],n[1]=[0]):1===t&&(n[0]=[]));return n}(c,e.length),v=function(e,t){return function(o,r,a){let u,i,l=0;void 0===a&&(a=0);do{u=a,a=null,i=n.geoDistance([o,r],t[u]),e[u].forEach(e=>{let u=n.geoDistance([o,r],t[e]);if(u<i)return i=u,a=e,void(l=e)})}while(null!==a);return l}}(m,e),M=function(e,t){return e.map(e=>{const n=e.map(e=>t[e]).map(y),o=d(d(p(n[1],n[0]),p(n[2],n[1])),p(n[0],n[2]));return g(h(o))})}(c,e),{polygons:b,centers:j}=function(e,t,n){const o=[],r=e.slice();if(0===t.length){if(n.length<2)return{polygons:o,centers:r};if(2===n.length){const e=y(n[0]),t=y(n[1]),u=h(d(e,t)),i=h(p(e,t)),l=p(u,i),s=[u,p(u,l),p(p(u,l),l),p(p(p(u,l),l),l)].map(g).map(a);return o.push(s),o.push(s.slice().reverse()),{polygons:o,centers:r}}}function a(e){let n=-1;return r.slice(t.length,1/0).forEach((o,r)=>{o[0]===e[0]&&o[1]===e[1]&&(n=r+t.length)}),n<0&&(n=r.length,r.push(e)),n}return t.forEach((e,t)=>{for(let n=0;n<3;n++){const r=e[n],a=e[(n+1)%3],u=e[(n+2)%3];o[r]=o[r]||[],o[r].push([a,u,t,[r,a,u]])}}),{polygons:o.map(e=>{const t=[e[0][2]];let o=e[0][1];for(let n=1;n<e.length;n++)for(let n=0;n<e.length;n++)if(e[n][0]==o){o=e[n][1],t.push(e[n][2]);break}if(t.length>2)return t;if(2==t.length){const o=_(n[e[0][3][0]],n[e[0][3][1]],r[t[0]]),u=_(n[e[0][3][2]],n[e[0][3][0]],r[t[0]]),i=a(o),l=a(u);return[t[0],l,t[1],i]}console&&console.warn({here:"unreachable",poly:e})}),centers:r}}(M,c,e);return{delaunay:u,edges:i,triangles:c,centers:j,neighbors:m,polygons:b,mesh:function(e){const t=[];return e.forEach(e=>{if(!e)return;let n=e[e.length-1];for(let o of e)o>n&&t.push([n,o]),n=o}),t}(b),hull:function(e,t){const o={},r=[];e.map(e=>{const r={type:"Polygon",coordinates:[[t[e[0]],t[e[1]],t[e[2]],t[e[0]]]]};if(!(n.geoArea(r)>a))for(let t=0;t<3;t++){let n=[e[t],e[(t+1)%3]],r=`${n[1]}-${n[0]}`;o[r]?delete o[r]:o[n.join("-")]=!0}});const u={};let i;if(Object.keys(o).forEach(e=>{e=e.split("-").map(Number),u[e[0]]=e[1],i=e[0]}),void 0===i)return r;let l=i;do{r.push(l),l=u[l]}while(l!==i);return r}(c,e),urquhart:function(e,t){return function(n){const r={},a={};return e.forEach((e,t)=>{const o=e.join("-");r[o]=n[t],a[o]=!0}),t.forEach(e=>{let t=0,n=-1;for(var u=0;u<3;u++){let a=o.extent([e[u],e[(u+1)%3]]).join("-");r[a]>t&&(t=r[a],n=a)}a[n]=!1}),e.map(e=>a[e.join("-")])}}(i,c),find:v}}function _(e,t,n){e=y(e),t=y(t),n=y(n);const o=c(function(e,t){return e[0]*t[0]+e[1]*t[1]+e[2]*t[2]}(p(t,e),n));return g(h(d(e,t)).map(e=>o*e))}e.geoDelaunay=m,e.geoVoronoi=function(e){const t=function(e){return t.delaunay=null,t._data=e,"object"==typeof t._data&&"FeatureCollection"===t._data.type&&(t._data=t._data.features),"object"==typeof t._data&&(t.points=t._data.map(e=>[t._vx(e),t._vy(e)]),t.delaunay=m(t.points)),t};return t._vx=function(e){return"object"==typeof e&&"type"in e?n.geoCentroid(e)[0]:0 in e?e[0]:void 0},t._vy=function(e){return"object"==typeof e&&"type"in e?n.geoCentroid(e)[1]:1 in e?e[1]:void 0},t.x=function(e){return e?(t._vx=e,t):t._vx},t.y=function(e){return e?(t._vy=e,t):t._vy},t.polygons=function(e){return void 0!==e&&t(e),!!t.delaunay&&(0===t._data.length?null:1===t._data.length?{type:"Sphere"}:{type:"FeatureCollection",features:t.delaunay.polygons.map((e,n)=>({type:"Feature",geometry:e?{type:"Polygon",coordinates:[[...e,e[0]].map(e=>t.delaunay.centers[e])]}:null,properties:{site:t._data[n],sitecoordinates:t.points[n],neighbours:t.delaunay.neighbors[n]}}))})},t.triangles=function(e){return void 0!==e&&t(e),!!t.delaunay&&{type:"FeatureCollection",features:t.delaunay.triangles.map((e,n)=>({type:"Feature",properties:{circumcenter:t.delaunay.centers[n]},geometry:{type:"Polygon",coordinates:[[t.points[e[0]],t.points[e[1]],t.points[e[2]],t.points[e[0]]]]}})).filter(e=>n.geoArea(e)<=a)}},t.links=function(e){if(void 0!==e&&t(e),!t.delaunay)return!1;const o=t.delaunay.edges.map(e=>n.geoDistance(t.points[e[0]],t.points[e[1]])),r=t.delaunay.urquhart(o);return{type:"FeatureCollection",features:t.delaunay.edges.map((e,n)=>({type:"Feature",properties:{source:t._data[e[0]],target:t._data[e[1]],length:o[n],urquhart:!!r[n]},geometry:{type:"LineString",coordinates:[t.points[e[0]],t.points[e[1]]]}}))}},t._found=void 0,t.find=function(e,o,r){if(t._found=t.delaunay.find(e,o,t._found),!r||n.geoDistance([e,o],t.points[t._found])<r)return t._found},t.hull=function(e){void 0!==e&&t(e);const n=t.delaunay.hull,o=t.points;return 0===n.length?null:{type:"Polygon",coordinates:[[...n.map(e=>o[e]),o[n[0]]]]}},e?t(e):t},Object.defineProperty(e,"__esModule",{value:!0})}); |
@@ -1,1 +0,2 @@ | ||
| export {default as geoVoronoi} from "./src/geoVoronoi"; | ||
| export {geoDelaunay} from "./src/delaunay.js"; | ||
| export {geoVoronoi} from "./src/voronoi.js"; |
| { | ||
| "name": "d3-geo-voronoi", | ||
| "version": "0.0.6", | ||
| "version": "1.0.0", | ||
| "description": "Spherical Voronoi Diagram and Delaunay Triangulation", | ||
@@ -9,3 +9,3 @@ "keywords": [ | ||
| "d3-geo", | ||
| "d3-voronoi" | ||
| "d3-delaunay" | ||
| ], | ||
@@ -27,10 +27,4 @@ "license": "MIT", | ||
| }, | ||
| "contributors": [ | ||
| { | ||
| "name": "Loren Petrich", | ||
| "url": "http://lpetrich.org" | ||
| } | ||
| ], | ||
| "scripts": { | ||
| "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 --extend d3 -o build/d3-geo-voronoi.js -- index.js", | ||
| "pretest": "rm -rf build && mkdir build && rollup --banner \"$(preamble)\" -g d3-array:d3,d3-geo:d3,d3-delaunay:d3 -f umd -n d3 --extend d3 -o build/d3-geo-voronoi.js -- index.js", | ||
| "test": "tape 'test/**/*-test.js'", | ||
@@ -41,6 +35,5 @@ "prepublishOnly": "npm run test && uglifyjs --preamble \"$(preamble)\" build/d3-geo-voronoi.js -c negate_iife=false -m -o build/d3-geo-voronoi.min.js", | ||
| "dependencies": { | ||
| "d3": "^4.0", | ||
| "d3-array": "^1.0", | ||
| "d3-geo": "^1.0", | ||
| "d3-voronoi": "^1.0" | ||
| "d3-delaunay": "^4.1.2" | ||
| }, | ||
@@ -51,4 +44,4 @@ "devDependencies": { | ||
| "tape": "4", | ||
| "uglify-js": "*" | ||
| "uglify-es": "*" | ||
| } | ||
| } |
| # d3-geo-voronoi | ||
| This module wraps d3 around Loren Petrich's [Spherical Delaunay triangulation library](http://lpetrich.org/Science/GeometryDemo/GeometryDemo_GMap.html), following as closely as possible the API of the [d3-voronoi](https://github.com/d3/d3-voronoi/) module. | ||
| This module adapts d3-delaunay for spherical data. Given a set of objects in spherical coordinates, it computes their Delaunay triangulation and its dual, the Voronoi diagram. | ||
| Given a set of objects in spherical coordinates, it computes their Delaunay triangulation and its dual, the Voronoi diagram ([d3 issue #1820](https://github.com/d3/d3/issues/1820)). | ||
| In addition, it offers convenience methods to extract the convex hull, the Urquhart graph, the circumcenters of the Delaunay triangles, and to find the cell that contains any given point on the sphere. | ||
| The module offers two APIs. The legacy API is based on GeoJSON and follows as closely as possible the API of the [d3-voronoi](https://github.com/d3/d3-voronoi/) module. It is available with *d3.geoVoronoi()*. | ||
| A lighter API is available with *d3.geoDelaunay()*. It offers the same contents, but with a different presentation, where every vertex, edge, polygon… is referenced by an id rather than by its coordinates. This allows a more compact representation in memory and eases topology computations, but is a bit less convenient for drawing the results on a map. | ||
| ## Installing | ||
@@ -17,4 +20,29 @@ | ||
| <a href="#geo-delaunay" name="geo-delaunay">#</a> d3.<b>geoDelaunay</b>([data]) | ||
| [<>](https://github.com/Fil/d3-geo-voronoi/blob/master/src/delaunay.js "Source") | ||
| Creates a new *spherical* Voronoi layout. _data_ must be passed as an array of [lon, lat] coordinates. | ||
| - delaunay.find(x,y,node): pass a starting node (_not_ a radius). | ||
| - delaunay.urquhart(*distances*): retrieve a vector of urquhart edges indices. | ||
| - delaunay.hull(): list of indices of points on the hull (empty if the points cover more than a hemisphere). | ||
| - delaunay.edges: list of edges as indices of points [from, to] (might change to a typed in the future) | ||
| - delaunay.triangles: list of edges as indices of points [a, b, c] (might change to a typed in the future) | ||
| - delaunay.centers: list of centers in spherical coordinates; the first *t* centers are the *t* triangles’s circumcenters. More centers might be listed in order to build the voronoi diagram for degenerate cases such as n=1,2,3 points. | ||
| - delaunay.neighbors, an array of neighbors indices for each vertex. | ||
| - delaunay.polygons, an array of centers for each vertex, order in a clockwise manner. | ||
| - delaunay.mesh, a list of all the edges of the voronoi polygons | ||
| <a href="#geo-voronoi" name="geo-voronoi">#</a> d3.<b>geoVoronoi</b>([data]) | ||
| [<>](https://github.com/Fil/d3-geo-voronoi/blob/master/src/geoVoronoi.js "Source") | ||
| [<>](https://github.com/Fil/d3-geo-voronoi/blob/master/src/voronoi.js "Source") | ||
@@ -25,2 +53,6 @@ Creates a new *spherical* Voronoi layout. _data_ can be passed as an array of [lon, lat] coordinates, an array of GeoJSON features, or a GeoJSON FeatureCollection. | ||
| <a href="#geo_voronoi_delaunay" name="geo_voronoi_delaunay">#</a> <i>voronoi</i>.<b>delaunay</b> | ||
| The raw d3.geoDelaunay() object used to compute this diagram. | ||
| <a href="#geo_voronoi_x" name="geo_voronoi_x">#</a> <i>voronoi</i>.<b>x</b>([<i>x</i>]) | ||
@@ -70,7 +102,5 @@ | ||
| The following new methods are introduced: | ||
| <a name="geo_voronoi_find" href="#geo_voronoi_find">#</a> <i>voronoi</i>.<b>find</b>(<i>x,y,[angle]</i>) | ||
| Finds the closest site to point *x,y*, i.e. the Voronoi polygon that contains it. Optionally, return null if the distance between the point and the site is larger than *angle* radians. | ||
| Finds the closest site to point *x,y*, i.e. the Voronoi polygon that contains it. Optionally, return null if the distance between the point and the site is larger than *angle* degrees. | ||
@@ -90,7 +120,5 @@ [](http://bl.ocks.org/Fil/e94fc45f5ed4dbcc989be1e52b797fdd) | ||
| _Note: there might be a better way to compute the geoHull, and this should probably be part of d3-geo. This method is experimental and may be removed from the API._ | ||
| ### Other tools & projections | ||
| ### Other projections | ||
| There is no reason to limit the display of Voronoi cells to the orthographic projection. The example below displays the Urquhart graph of top container ports on a Winkel tripel map. | ||
@@ -100,2 +128,3 @@ | ||
| [Geo_triangulate](https://jessihamel.github.io/geo_triangulate/) converts GeoJSON to triangles for 3d rendering. | ||
@@ -105,9 +134,22 @@ | ||
| - geoVoronoi is for points on the sphere, `d3-voronoi` is for points on a plane (or possibly a [torus](http://bl.ocks.org/Fil/c1b10942f61483d739dd601d09c30deb) or a [cylinder](http://bl.ocks.org/Fil/4639744e8be5428e7a8e7b3efd9a80dc)). | ||
| - the Delaunay/Voronoi topology is quite different on the sphere and on the plane. This module deals with these differences by first projecting the points with a stereographic projection, then stitching the geometries that are near the singularity of the projection (the “infinite horizon” on the plane is one point on the sphere). | ||
| - geoVoronoi uses a different algorithm (in `O(n^2)`, which is [much slower](https://github.com/Fil/d3-geo-voronoi/issues/1) as the number of sites grows past 1000) -- and its internal data structure is different. | ||
| - geoVoronoi returns GeoJSON objects, which are often `FeatureCollections`. By consequence, you will have to change `.data(voronoi.polygons())` to `.data(geovoronoi.polygons().features)`, and so on. | ||
| - 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. | ||
| - geoVoronoi is built on [d3-delaunay](https://github.com/d3/d3-delaunay), which is also exposed as d3.geoDelunay in this library. If you want to have the fastest results, you should try to use d3.geoDelaunay directly (see the examples). | ||
| - geoVoronoi and geoDelaunay offer methods to compute the spherical [convex hull](#geo_voronoi_hull) and the [Urquhart graph](#geo_voronoi_links) of the data set. 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 or d3-delaunay. | ||
| ### Changes | ||
| - the module needs d3-delaunay and doesn't embed it. | ||
| &lk;script src="https://unpkg.com/d3-delaunay@4></script> | ||
| &lk;script src="https://unpkg.com/d3-geo-voronoi@1"></script> | ||
| To access the previous (slow) version, please use &lk;script src="https://unpkg.com/d3-geo-voronoi@0"></script> | ||
Sorry, the diff of this file is not supported yet
New alerts
License Policy Violation
LicenseThis package is not allowed per your license policy. Review the package's license to ensure compliance.
Found 1 instance in 1 package
Fixed alerts
License Policy Violation
LicenseThis package is not allowed per your license policy. Review the package's license to ensure compliance.
Found 1 instance in 1 package
No v1
QualityPackage is not semver >=1. This means it is not stable and does not support ^ ranges.
Found 1 instance in 1 package
Improved metrics
- Dependency count
- decreased by-25%
3
- Number of package files
- increased by2.86%
36
- Number of low quality alerts
- decreased by-50%
1
- Number of lines in readme file
- increased by38.89%
150
Worsened metrics
- Total package byte prevSize
- decreased by-0.79%
9433864
- Lines of code
- decreased by-12.3%
14944
Dependency changes
+ Addedd3-delaunay@^4.1.2
+ Addedd3-delaunay@4.1.5(transitive)
+ Addeddelaunator@2.0.5(transitive)
- Removedd3@^4.0
- Removedd3-voronoi@^1.0
- Removedcommander@2.20.3(transitive)
- Removedd3@4.13.0(transitive)
- Removedd3-array@1.2.1(transitive)
- Removedd3-axis@1.0.8(transitive)
- Removedd3-brush@1.0.4(transitive)
- Removedd3-chord@1.0.4(transitive)
- Removedd3-collection@1.0.4(transitive)
- Removedd3-color@1.0.3(transitive)
- Removedd3-dispatch@1.0.3(transitive)
- Removedd3-drag@1.2.1(transitive)
- Removedd3-dsv@1.0.8(transitive)
- Removedd3-ease@1.0.3(transitive)
- Removedd3-force@1.1.0(transitive)
- Removedd3-format@1.2.2(transitive)
- Removedd3-geo@1.9.1(transitive)
- Removedd3-hierarchy@1.1.5(transitive)
- Removedd3-interpolate@1.1.6(transitive)
- Removedd3-path@1.0.5(transitive)
- Removedd3-polygon@1.0.3(transitive)
- Removedd3-quadtree@1.0.3(transitive)
- Removedd3-queue@3.0.7(transitive)
- Removedd3-random@1.1.0(transitive)
- Removedd3-request@1.0.6(transitive)
- Removedd3-scale@1.0.7(transitive)
- Removedd3-selection@1.3.0(transitive)
- Removedd3-shape@1.2.0(transitive)
- Removedd3-time@1.0.8(transitive)
- Removedd3-time-format@2.1.1(transitive)
- Removedd3-timer@1.0.7(transitive)
- Removedd3-transition@1.1.1(transitive)
- Removedd3-voronoi@1.1.21.1.4(transitive)
- Removedd3-zoom@1.7.1(transitive)
- Removediconv-lite@0.4.24(transitive)
- Removedrw@1.3.3(transitive)
- Removedsafer-buffer@2.1.2(transitive)
- Removedxmlhttprequest@1.8.0(transitive)