diff options
Diffstat (limited to 'web/nms.gathering.org/speedometer/d3-master/src/geom')
16 files changed, 1382 insertions, 0 deletions
diff --git a/web/nms.gathering.org/speedometer/d3-master/src/geom/clip-line.js b/web/nms.gathering.org/speedometer/d3-master/src/geom/clip-line.js new file mode 100644 index 0000000..c83c412 --- /dev/null +++ b/web/nms.gathering.org/speedometer/d3-master/src/geom/clip-line.js @@ -0,0 +1,66 @@ +import "../math/trigonometry"; + +// Liang–Barsky line clipping. +function d3_geom_clipLine(x0, y0, x1, y1) { + return function(line) { + var a = line.a, + b = line.b, + ax = a.x, + ay = a.y, + bx = b.x, + by = b.y, + t0 = 0, + t1 = 1, + dx = bx - ax, + dy = by - ay, + r; + + r = x0 - ax; + if (!dx && r > 0) return; + r /= dx; + if (dx < 0) { + if (r < t0) return; + if (r < t1) t1 = r; + } else if (dx > 0) { + if (r > t1) return; + if (r > t0) t0 = r; + } + + r = x1 - ax; + if (!dx && r < 0) return; + r /= dx; + if (dx < 0) { + if (r > t1) return; + if (r > t0) t0 = r; + } else if (dx > 0) { + if (r < t0) return; + if (r < t1) t1 = r; + } + + r = y0 - ay; + if (!dy && r > 0) return; + r /= dy; + if (dy < 0) { + if (r < t0) return; + if (r < t1) t1 = r; + } else if (dy > 0) { + if (r > t1) return; + if (r > t0) t0 = r; + } + + r = y1 - ay; + if (!dy && r < 0) return; + r /= dy; + if (dy < 0) { + if (r > t1) return; + if (r > t0) t0 = r; + } else if (dy > 0) { + if (r < t0) return; + if (r < t1) t1 = r; + } + + if (t0 > 0) line.a = {x: ax + t0 * dx, y: ay + t0 * dy}; + if (t1 < 1) line.b = {x: ax + t1 * dx, y: ay + t1 * dy}; + return line; + }; +} diff --git a/web/nms.gathering.org/speedometer/d3-master/src/geom/delaunay.js b/web/nms.gathering.org/speedometer/d3-master/src/geom/delaunay.js new file mode 100644 index 0000000..0a60cd1 --- /dev/null +++ b/web/nms.gathering.org/speedometer/d3-master/src/geom/delaunay.js @@ -0,0 +1,6 @@ +import "geom"; + +// @deprecated; use d3.geom.voronoi triangles instead. +d3.geom.delaunay = function(vertices) { + return d3.geom.voronoi().triangles(vertices); +}; diff --git a/web/nms.gathering.org/speedometer/d3-master/src/geom/geom.js b/web/nms.gathering.org/speedometer/d3-master/src/geom/geom.js new file mode 100644 index 0000000..b17c4fc --- /dev/null +++ b/web/nms.gathering.org/speedometer/d3-master/src/geom/geom.js @@ -0,0 +1 @@ +d3.geom = {}; diff --git a/web/nms.gathering.org/speedometer/d3-master/src/geom/hull.js b/web/nms.gathering.org/speedometer/d3-master/src/geom/hull.js new file mode 100644 index 0000000..7abce15 --- /dev/null +++ b/web/nms.gathering.org/speedometer/d3-master/src/geom/hull.js @@ -0,0 +1,91 @@ +import "../core/functor"; +import "../math/trigonometry"; +import "geom"; +import "point"; + +/** + * Computes the 2D convex hull of a set of points using the monotone chain + * algorithm: + * http://en.wikibooks.org/wiki/Algorithm_Implementation/Geometry/Convex_hull/Monotone_chain) + * + * The runtime of this algorithm is O(n log n), where n is the number of input + * points. However in practice it outperforms other O(n log n) hulls. + * + * @param vertices [[x1, y1], [x2, y2], ...] + * @returns polygon [[x1, y1], [x2, y2], ...] + */ +d3.geom.hull = function(vertices) { + var x = d3_geom_pointX, + y = d3_geom_pointY; + + if (arguments.length) return hull(vertices); + + function hull(data) { + // Hull of < 3 points is not well-defined + if (data.length < 3) return []; + + var fx = d3_functor(x), + fy = d3_functor(y), + i, + n = data.length, + points = [], // of the form [[x0, y0, 0], ..., [xn, yn, n]] + flippedPoints = []; + + for (i = 0 ; i < n; i++) { + points.push([+fx.call(this, data[i], i), +fy.call(this, data[i], i), i]); + } + + // sort ascending by x-coord first, y-coord second + points.sort(d3_geom_hullOrder); + + // we flip bottommost points across y axis so we can use the upper hull routine on both + for (i = 0; i < n; i++) flippedPoints.push([points[i][0], -points[i][1]]); + + var upper = d3_geom_hullUpper(points), + lower = d3_geom_hullUpper(flippedPoints); + + // construct the polygon, removing possible duplicate endpoints + var skipLeft = lower[0] === upper[0], + skipRight = lower[lower.length - 1] === upper[upper.length - 1], + polygon = []; + + // add upper hull in r->l order + // then add lower hull in l->r order + for (i = upper.length - 1; i >= 0; --i) polygon.push(data[points[upper[i]][2]]); + for (i = +skipLeft; i < lower.length - skipRight; ++i) polygon.push(data[points[lower[i]][2]]); + + return polygon; + } + + hull.x = function(_) { + return arguments.length ? (x = _, hull) : x; + }; + + hull.y = function(_) { + return arguments.length ? (y = _, hull) : y; + }; + + return hull; +}; + +// finds the 'upper convex hull' (see wiki link above) +// assumes points arg has >=3 elements, is sorted by x, unique in y +// returns array of indices into points in left to right order +function d3_geom_hullUpper(points) { + var n = points.length, + hull = [0, 1], + hs = 2; // hull size + + for (var i = 2; i < n; i++) { + while (hs > 1 && d3_cross2d(points[hull[hs-2]], points[hull[hs-1]], points[i]) <= 0) --hs; + hull[hs++] = i; + } + + // we slice to make sure that the points we 'popped' from hull don't stay behind + return hull.slice(0, hs); +} + +// comparator for ascending sort by x-coord first, y-coord second +function d3_geom_hullOrder(a, b) { + return a[0] - b[0] || a[1] - b[1]; +} diff --git a/web/nms.gathering.org/speedometer/d3-master/src/geom/index.js b/web/nms.gathering.org/speedometer/d3-master/src/geom/index.js new file mode 100644 index 0000000..9e2fb28 --- /dev/null +++ b/web/nms.gathering.org/speedometer/d3-master/src/geom/index.js @@ -0,0 +1,6 @@ +import "geom"; +import "hull"; +import "polygon"; +import "voronoi"; +import "delaunay"; +import "quadtree"; diff --git a/web/nms.gathering.org/speedometer/d3-master/src/geom/point.js b/web/nms.gathering.org/speedometer/d3-master/src/geom/point.js new file mode 100644 index 0000000..10cfe3e --- /dev/null +++ b/web/nms.gathering.org/speedometer/d3-master/src/geom/point.js @@ -0,0 +1,7 @@ +function d3_geom_pointX(d) { + return d[0]; +} + +function d3_geom_pointY(d) { + return d[1]; +} diff --git a/web/nms.gathering.org/speedometer/d3-master/src/geom/polygon.js b/web/nms.gathering.org/speedometer/d3-master/src/geom/polygon.js new file mode 100644 index 0000000..02383dd --- /dev/null +++ b/web/nms.gathering.org/speedometer/d3-master/src/geom/polygon.js @@ -0,0 +1,105 @@ +import "../core/subclass"; +import "geom"; + +d3.geom.polygon = function(coordinates) { + d3_subclass(coordinates, d3_geom_polygonPrototype); + return coordinates; +}; + +var d3_geom_polygonPrototype = d3.geom.polygon.prototype = []; + +d3_geom_polygonPrototype.area = function() { + var i = -1, + n = this.length, + a, + b = this[n - 1], + area = 0; + + while (++i < n) { + a = b; + b = this[i]; + area += a[1] * b[0] - a[0] * b[1]; + } + + return area * .5; +}; + +d3_geom_polygonPrototype.centroid = function(k) { + var i = -1, + n = this.length, + x = 0, + y = 0, + a, + b = this[n - 1], + c; + + if (!arguments.length) k = -1 / (6 * this.area()); + + while (++i < n) { + a = b; + b = this[i]; + c = a[0] * b[1] - b[0] * a[1]; + x += (a[0] + b[0]) * c; + y += (a[1] + b[1]) * c; + } + + return [x * k, y * k]; +}; + +// The Sutherland-Hodgman clipping algorithm. +// Note: requires the clip polygon to be counterclockwise and convex. +d3_geom_polygonPrototype.clip = function(subject) { + var input, + closed = d3_geom_polygonClosed(subject), + i = -1, + n = this.length - d3_geom_polygonClosed(this), + j, + m, + a = this[n - 1], + b, + c, + d; + + while (++i < n) { + input = subject.slice(); + subject.length = 0; + b = this[i]; + c = input[(m = input.length - closed) - 1]; + j = -1; + while (++j < m) { + d = input[j]; + if (d3_geom_polygonInside(d, a, b)) { + if (!d3_geom_polygonInside(c, a, b)) { + subject.push(d3_geom_polygonIntersect(c, d, a, b)); + } + subject.push(d); + } else if (d3_geom_polygonInside(c, a, b)) { + subject.push(d3_geom_polygonIntersect(c, d, a, b)); + } + c = d; + } + if (closed) subject.push(subject[0]); + a = b; + } + + return subject; +}; + +function d3_geom_polygonInside(p, a, b) { + return (b[0] - a[0]) * (p[1] - a[1]) < (b[1] - a[1]) * (p[0] - a[0]); +} + +// Intersect two infinite lines cd and ab. +function d3_geom_polygonIntersect(c, d, a, b) { + var x1 = c[0], x3 = a[0], x21 = d[0] - x1, x43 = b[0] - x3, + y1 = c[1], y3 = a[1], y21 = d[1] - y1, y43 = b[1] - y3, + ua = (x43 * (y1 - y3) - y43 * (x1 - x3)) / (y43 * x21 - x43 * y21); + return [x1 + ua * x21, y1 + ua * y21]; +} + +// Returns true if the polygon is closed. +function d3_geom_polygonClosed(coordinates) { + var a = coordinates[0], + b = coordinates[coordinates.length - 1]; + return !(a[0] - b[0] || a[1] - b[1]); +} diff --git a/web/nms.gathering.org/speedometer/d3-master/src/geom/quadtree.js b/web/nms.gathering.org/speedometer/d3-master/src/geom/quadtree.js new file mode 100644 index 0000000..8d9f6a5 --- /dev/null +++ b/web/nms.gathering.org/speedometer/d3-master/src/geom/quadtree.js @@ -0,0 +1,243 @@ +import "../core/functor"; +import "../math/abs"; +import "geom"; +import "point"; + +d3.geom.quadtree = function(points, x1, y1, x2, y2) { + var x = d3_geom_pointX, + y = d3_geom_pointY, + compat; + + // For backwards-compatibility. + if (compat = arguments.length) { + x = d3_geom_quadtreeCompatX; + y = d3_geom_quadtreeCompatY; + if (compat === 3) { + y2 = y1; + x2 = x1; + y1 = x1 = 0; + } + return quadtree(points); + } + + function quadtree(data) { + var d, + fx = d3_functor(x), + fy = d3_functor(y), + xs, + ys, + i, + n, + x1_, + y1_, + x2_, + y2_; + + if (x1 != null) { + x1_ = x1, y1_ = y1, x2_ = x2, y2_ = y2; + } else { + // Compute bounds, and cache points temporarily. + x2_ = y2_ = -(x1_ = y1_ = Infinity); + xs = [], ys = []; + n = data.length; + if (compat) for (i = 0; i < n; ++i) { + d = data[i]; + if (d.x < x1_) x1_ = d.x; + if (d.y < y1_) y1_ = d.y; + if (d.x > x2_) x2_ = d.x; + if (d.y > y2_) y2_ = d.y; + xs.push(d.x); + ys.push(d.y); + } else for (i = 0; i < n; ++i) { + var x_ = +fx(d = data[i], i), + y_ = +fy(d, i); + if (x_ < x1_) x1_ = x_; + if (y_ < y1_) y1_ = y_; + if (x_ > x2_) x2_ = x_; + if (y_ > y2_) y2_ = y_; + xs.push(x_); + ys.push(y_); + } + } + + // Squarify the bounds. + var dx = x2_ - x1_, + dy = y2_ - y1_; + if (dx > dy) y2_ = y1_ + dx; + else x2_ = x1_ + dy; + + // Recursively inserts the specified point p at the node n or one of its + // descendants. The bounds are defined by [x1, x2] and [y1, y2]. + function insert(n, d, x, y, x1, y1, x2, y2) { + if (isNaN(x) || isNaN(y)) return; // ignore invalid points + if (n.leaf) { + var nx = n.x, + ny = n.y; + if (nx != null) { + // If the point at this leaf node is at the same position as the new + // point we are adding, we leave the point associated with the + // internal node while adding the new point to a child node. This + // avoids infinite recursion. + if ((abs(nx - x) + abs(ny - y)) < .01) { + insertChild(n, d, x, y, x1, y1, x2, y2); + } else { + var nPoint = n.point; + n.x = n.y = n.point = null; + insertChild(n, nPoint, nx, ny, x1, y1, x2, y2); + insertChild(n, d, x, y, x1, y1, x2, y2); + } + } else { + n.x = x, n.y = y, n.point = d; + } + } else { + insertChild(n, d, x, y, x1, y1, x2, y2); + } + } + + // Recursively inserts the specified point [x, y] into a descendant of node + // n. The bounds are defined by [x1, x2] and [y1, y2]. + function insertChild(n, d, x, y, x1, y1, x2, y2) { + // Compute the split point, and the quadrant in which to insert p. + var xm = (x1 + x2) * .5, + ym = (y1 + y2) * .5, + right = x >= xm, + below = y >= ym, + i = below << 1 | right; + + // Recursively insert into the child node. + n.leaf = false; + n = n.nodes[i] || (n.nodes[i] = d3_geom_quadtreeNode()); + + // Update the bounds as we recurse. + if (right) x1 = xm; else x2 = xm; + if (below) y1 = ym; else y2 = ym; + insert(n, d, x, y, x1, y1, x2, y2); + } + + // Create the root node. + var root = d3_geom_quadtreeNode(); + + root.add = function(d) { + insert(root, d, +fx(d, ++i), +fy(d, i), x1_, y1_, x2_, y2_); + }; + + root.visit = function(f) { + d3_geom_quadtreeVisit(f, root, x1_, y1_, x2_, y2_); + }; + + // Find the closest point to the specified point. + // TODO allow the initial search extent to be specified? + // TODO allow the initial minimum distance to be specified? + // TODO allow searching below any node? + root.find = function(point) { + return d3_geom_quadtreeFind(root, point[0], point[1], x1_, y1_, x2_, y2_); + }; + + // Insert all points. + i = -1; + if (x1 == null) { + while (++i < n) { + insert(root, data[i], xs[i], ys[i], x1_, y1_, x2_, y2_); + } + --i; // index of last insertion + } else data.forEach(root.add); + + // Discard captured fields. + xs = ys = data = d = null; + + return root; + } + + quadtree.x = function(_) { + return arguments.length ? (x = _, quadtree) : x; + }; + + quadtree.y = function(_) { + return arguments.length ? (y = _, quadtree) : y; + }; + + quadtree.extent = function(_) { + if (!arguments.length) return x1 == null ? null : [[x1, y1], [x2, y2]]; + if (_ == null) x1 = y1 = x2 = y2 = null; + else x1 = +_[0][0], y1 = +_[0][1], x2 = +_[1][0], y2 = +_[1][1]; + return quadtree; + }; + + quadtree.size = function(_) { + if (!arguments.length) return x1 == null ? null : [x2 - x1, y2 - y1]; + if (_ == null) x1 = y1 = x2 = y2 = null; + else x1 = y1 = 0, x2 = +_[0], y2 = +_[1]; + return quadtree; + }; + + return quadtree; +}; + +function d3_geom_quadtreeCompatX(d) { return d.x; } +function d3_geom_quadtreeCompatY(d) { return d.y; } + +function d3_geom_quadtreeNode() { + return { + leaf: true, + nodes: [], + point: null, + x: null, + y: null + }; +} + +function d3_geom_quadtreeVisit(f, node, x1, y1, x2, y2) { + if (!f(node, x1, y1, x2, y2)) { + var sx = (x1 + x2) * .5, + sy = (y1 + y2) * .5, + children = node.nodes; + if (children[0]) d3_geom_quadtreeVisit(f, children[0], x1, y1, sx, sy); + if (children[1]) d3_geom_quadtreeVisit(f, children[1], sx, y1, x2, sy); + if (children[2]) d3_geom_quadtreeVisit(f, children[2], x1, sy, sx, y2); + if (children[3]) d3_geom_quadtreeVisit(f, children[3], sx, sy, x2, y2); + } +} + +function d3_geom_quadtreeFind(root, x, y, x0, y0, x3, y3) { + var minDistance2 = Infinity, + closestPoint; + + (function find(node, x1, y1, x2, y2) { + + // stop searching if this cell can’t contain a closer node + if (x1 > x3 || y1 > y3 || x2 < x0 || y2 < y0) return; + + // visit this point + if (point = node.point) { + var point, + dx = x - node.x, + dy = y - node.y, + distance2 = dx * dx + dy * dy; + if (distance2 < minDistance2) { + var distance = Math.sqrt(minDistance2 = distance2); + x0 = x - distance, y0 = y - distance; + x3 = x + distance, y3 = y + distance; + closestPoint = point; + } + } + + // bisect the current node + var children = node.nodes, + xm = (x1 + x2) * .5, + ym = (y1 + y2) * .5, + right = x >= xm, + below = y >= ym; + + // visit closest cell first + for (var i = below << 1 | right, j = i + 4; i < j; ++i) { + if (node = children[i & 3]) switch (i & 3) { + case 0: find(node, x1, y1, xm, ym); break; + case 1: find(node, xm, y1, x2, ym); break; + case 2: find(node, x1, ym, xm, y2); break; + case 3: find(node, xm, ym, x2, y2); break; + } + } + })(root, x0, y0, x3, y3); + + return closestPoint; +} diff --git a/web/nms.gathering.org/speedometer/d3-master/src/geom/voronoi.js b/web/nms.gathering.org/speedometer/d3-master/src/geom/voronoi.js new file mode 100644 index 0000000..53f7d79 --- /dev/null +++ b/web/nms.gathering.org/speedometer/d3-master/src/geom/voronoi.js @@ -0,0 +1,110 @@ +import "../core/functor"; +import "voronoi/"; +import "geom"; +import "point"; + +d3.geom.voronoi = function(points) { + var x = d3_geom_pointX, + y = d3_geom_pointY, + fx = x, + fy = y, + clipExtent = d3_geom_voronoiClipExtent; + + // @deprecated; use voronoi(data) instead. + if (points) return voronoi(points); + + function voronoi(data) { + var polygons = new Array(data.length), + x0 = clipExtent[0][0], + y0 = clipExtent[0][1], + x1 = clipExtent[1][0], + y1 = clipExtent[1][1]; + + d3_geom_voronoi(sites(data), clipExtent).cells.forEach(function(cell, i) { + var edges = cell.edges, + site = cell.site, + polygon = polygons[i] = edges.length ? edges.map(function(e) { var s = e.start(); return [s.x, s.y]; }) + : site.x >= x0 && site.x <= x1 && site.y >= y0 && site.y <= y1 ? [[x0, y1], [x1, y1], [x1, y0], [x0, y0]] + : []; + polygon.point = data[i]; + }); + + return polygons; + } + + function sites(data) { + return data.map(function(d, i) { + return { + x: Math.round(fx(d, i) / ε) * ε, + y: Math.round(fy(d, i) / ε) * ε, + i: i + }; + }); + } + + voronoi.links = function(data) { + return d3_geom_voronoi(sites(data)).edges.filter(function(edge) { + return edge.l && edge.r; + }).map(function(edge) { + return { + source: data[edge.l.i], + target: data[edge.r.i] + }; + }); + }; + + voronoi.triangles = function(data) { + var triangles = []; + + d3_geom_voronoi(sites(data)).cells.forEach(function(cell, i) { + var site = cell.site, + edges = cell.edges.sort(d3_geom_voronoiHalfEdgeOrder), + j = -1, + m = edges.length, + e0, + s0, + e1 = edges[m - 1].edge, + s1 = e1.l === site ? e1.r : e1.l; + + while (++j < m) { + e0 = e1; + s0 = s1; + e1 = edges[j].edge; + s1 = e1.l === site ? e1.r : e1.l; + if (i < s0.i && i < s1.i && d3_geom_voronoiTriangleArea(site, s0, s1) < 0) { + triangles.push([data[i], data[s0.i], data[s1.i]]); + } + } + }); + + return triangles; + }; + + voronoi.x = function(_) { + return arguments.length ? (fx = d3_functor(x = _), voronoi) : x; + }; + + voronoi.y = function(_) { + return arguments.length ? (fy = d3_functor(y = _), voronoi) : y; + }; + + voronoi.clipExtent = function(_) { + if (!arguments.length) return clipExtent === d3_geom_voronoiClipExtent ? null : clipExtent; + clipExtent = _ == null ? d3_geom_voronoiClipExtent : _; + return voronoi; + }; + + // @deprecated; use clipExtent instead. + voronoi.size = function(_) { + if (!arguments.length) return clipExtent === d3_geom_voronoiClipExtent ? null : clipExtent && clipExtent[1]; + return voronoi.clipExtent(_ && [[0, 0], _]); + }; + + return voronoi; +}; + +var d3_geom_voronoiClipExtent = [[-1e6, -1e6], [1e6, 1e6]]; + +function d3_geom_voronoiTriangleArea(a, b, c) { + return (a.x - c.x) * (b.y - a.y) - (a.x - b.x) * (c.y - a.y); +} diff --git a/web/nms.gathering.org/speedometer/d3-master/src/geom/voronoi/beach.js b/web/nms.gathering.org/speedometer/d3-master/src/geom/voronoi/beach.js new file mode 100644 index 0000000..e017467 --- /dev/null +++ b/web/nms.gathering.org/speedometer/d3-master/src/geom/voronoi/beach.js @@ -0,0 +1,186 @@ +import "../../math/abs"; + +function d3_geom_voronoiBeach() { + d3_geom_voronoiRedBlackNode(this); + this.edge = + this.site = + this.circle = null; +} + +function d3_geom_voronoiCreateBeach(site) { + var beach = d3_geom_voronoiBeachPool.pop() || new d3_geom_voronoiBeach; + beach.site = site; + return beach; +} + +function d3_geom_voronoiDetachBeach(beach) { + d3_geom_voronoiDetachCircle(beach); + d3_geom_voronoiBeaches.remove(beach); + d3_geom_voronoiBeachPool.push(beach); + d3_geom_voronoiRedBlackNode(beach); +} + +function d3_geom_voronoiRemoveBeach(beach) { + var circle = beach.circle, + x = circle.x, + y = circle.cy, + vertex = {x: x, y: y}, + previous = beach.P, + next = beach.N, + disappearing = [beach]; + + d3_geom_voronoiDetachBeach(beach); + + var lArc = previous; + while (lArc.circle + && abs(x - lArc.circle.x) < ε + && abs(y - lArc.circle.cy) < ε) { + previous = lArc.P; + disappearing.unshift(lArc); + d3_geom_voronoiDetachBeach(lArc); + lArc = previous; + } + + disappearing.unshift(lArc); + d3_geom_voronoiDetachCircle(lArc); + + var rArc = next; + while (rArc.circle + && abs(x - rArc.circle.x) < ε + && abs(y - rArc.circle.cy) < ε) { + next = rArc.N; + disappearing.push(rArc); + d3_geom_voronoiDetachBeach(rArc); + rArc = next; + } + + disappearing.push(rArc); + d3_geom_voronoiDetachCircle(rArc); + + var nArcs = disappearing.length, + iArc; + for (iArc = 1; iArc < nArcs; ++iArc) { + rArc = disappearing[iArc]; + lArc = disappearing[iArc - 1]; + d3_geom_voronoiSetEdgeEnd(rArc.edge, lArc.site, rArc.site, vertex); + } + + lArc = disappearing[0]; + rArc = disappearing[nArcs - 1]; + rArc.edge = d3_geom_voronoiCreateEdge(lArc.site, rArc.site, null, vertex); + + d3_geom_voronoiAttachCircle(lArc); + d3_geom_voronoiAttachCircle(rArc); +} + +function d3_geom_voronoiAddBeach(site) { + var x = site.x, + directrix = site.y, + lArc, + rArc, + dxl, + dxr, + node = d3_geom_voronoiBeaches._; + + while (node) { + dxl = d3_geom_voronoiLeftBreakPoint(node, directrix) - x; + if (dxl > ε) node = node.L; else { + dxr = x - d3_geom_voronoiRightBreakPoint(node, directrix); + if (dxr > ε) { + if (!node.R) { + lArc = node; + break; + } + node = node.R; + } else { + if (dxl > -ε) { + lArc = node.P; + rArc = node; + } else if (dxr > -ε) { + lArc = node; + rArc = node.N; + } else { + lArc = rArc = node; + } + break; + } + } + } + + var newArc = d3_geom_voronoiCreateBeach(site); + d3_geom_voronoiBeaches.insert(lArc, newArc); + + if (!lArc && !rArc) return; + + if (lArc === rArc) { + d3_geom_voronoiDetachCircle(lArc); + rArc = d3_geom_voronoiCreateBeach(lArc.site); + d3_geom_voronoiBeaches.insert(newArc, rArc); + newArc.edge = rArc.edge = d3_geom_voronoiCreateEdge(lArc.site, newArc.site); + d3_geom_voronoiAttachCircle(lArc); + d3_geom_voronoiAttachCircle(rArc); + return; + } + + if (!rArc) { // && lArc + newArc.edge = d3_geom_voronoiCreateEdge(lArc.site, newArc.site); + return; + } + + // else lArc !== rArc + d3_geom_voronoiDetachCircle(lArc); + d3_geom_voronoiDetachCircle(rArc); + + var lSite = lArc.site, + ax = lSite.x, + ay = lSite.y, + bx = site.x - ax, + by = site.y - ay, + rSite = rArc.site, + cx = rSite.x - ax, + cy = rSite.y - ay, + d = 2 * (bx * cy - by * cx), + hb = bx * bx + by * by, + hc = cx * cx + cy * cy, + vertex = {x: (cy * hb - by * hc) / d + ax, y: (bx * hc - cx * hb) / d + ay}; + + d3_geom_voronoiSetEdgeEnd(rArc.edge, lSite, rSite, vertex); + newArc.edge = d3_geom_voronoiCreateEdge(lSite, site, null, vertex); + rArc.edge = d3_geom_voronoiCreateEdge(site, rSite, null, vertex); + d3_geom_voronoiAttachCircle(lArc); + d3_geom_voronoiAttachCircle(rArc); +} + +function d3_geom_voronoiLeftBreakPoint(arc, directrix) { + var site = arc.site, + rfocx = site.x, + rfocy = site.y, + pby2 = rfocy - directrix; + + if (!pby2) return rfocx; + + var lArc = arc.P; + if (!lArc) return -Infinity; + + site = lArc.site; + var lfocx = site.x, + lfocy = site.y, + plby2 = lfocy - directrix; + + if (!plby2) return lfocx; + + var hl = lfocx - rfocx, + aby2 = 1 / pby2 - 1 / plby2, + b = hl / plby2; + + if (aby2) return (-b + Math.sqrt(b * b - 2 * aby2 * (hl * hl / (-2 * plby2) - lfocy + plby2 / 2 + rfocy - pby2 / 2))) / aby2 + rfocx; + + return (rfocx + lfocx) / 2; +} + +function d3_geom_voronoiRightBreakPoint(arc, directrix) { + var rArc = arc.N; + if (rArc) return d3_geom_voronoiLeftBreakPoint(rArc, directrix); + var site = arc.site; + return site.y === directrix ? site.x : Infinity; +} diff --git a/web/nms.gathering.org/speedometer/d3-master/src/geom/voronoi/cell.js b/web/nms.gathering.org/speedometer/d3-master/src/geom/voronoi/cell.js new file mode 100644 index 0000000..8c6628d --- /dev/null +++ b/web/nms.gathering.org/speedometer/d3-master/src/geom/voronoi/cell.js @@ -0,0 +1,64 @@ +import "../../math/abs"; + +function d3_geom_voronoiCell(site) { + this.site = site; + this.edges = []; +} + +d3_geom_voronoiCell.prototype.prepare = function() { + var halfEdges = this.edges, + iHalfEdge = halfEdges.length, + edge; + + while (iHalfEdge--) { + edge = halfEdges[iHalfEdge].edge; + if (!edge.b || !edge.a) halfEdges.splice(iHalfEdge, 1); + } + + halfEdges.sort(d3_geom_voronoiHalfEdgeOrder); + return halfEdges.length; +}; + +function d3_geom_voronoiCloseCells(extent) { + var x0 = extent[0][0], + x1 = extent[1][0], + y0 = extent[0][1], + y1 = extent[1][1], + x2, + y2, + x3, + y3, + cells = d3_geom_voronoiCells, + iCell = cells.length, + cell, + iHalfEdge, + halfEdges, + nHalfEdges, + start, + end; + + while (iCell--) { + cell = cells[iCell]; + if (!cell || !cell.prepare()) continue; + halfEdges = cell.edges; + nHalfEdges = halfEdges.length; + iHalfEdge = 0; + while (iHalfEdge < nHalfEdges) { + end = halfEdges[iHalfEdge].end(), x3 = end.x, y3 = end.y; + start = halfEdges[++iHalfEdge % nHalfEdges].start(), x2 = start.x, y2 = start.y; + if (abs(x3 - x2) > ε || abs(y3 - y2) > ε) { + halfEdges.splice(iHalfEdge, 0, new d3_geom_voronoiHalfEdge(d3_geom_voronoiCreateBorderEdge(cell.site, end, + abs(x3 - x0) < ε && y1 - y3 > ε ? {x: x0, y: abs(x2 - x0) < ε ? y2 : y1} + : abs(y3 - y1) < ε && x1 - x3 > ε ? {x: abs(y2 - y1) < ε ? x2 : x1, y: y1} + : abs(x3 - x1) < ε && y3 - y0 > ε ? {x: x1, y: abs(x2 - x1) < ε ? y2 : y0} + : abs(y3 - y0) < ε && x3 - x0 > ε ? {x: abs(y2 - y0) < ε ? x2 : x0, y: y0} + : null), cell.site, null)); + ++nHalfEdges; + } + } + } +} + +function d3_geom_voronoiHalfEdgeOrder(a, b) { + return b.angle - a.angle; +} diff --git a/web/nms.gathering.org/speedometer/d3-master/src/geom/voronoi/circle.js b/web/nms.gathering.org/speedometer/d3-master/src/geom/voronoi/circle.js new file mode 100644 index 0000000..d7fb679 --- /dev/null +++ b/web/nms.gathering.org/speedometer/d3-master/src/geom/voronoi/circle.js @@ -0,0 +1,73 @@ +function d3_geom_voronoiCircle() { + d3_geom_voronoiRedBlackNode(this); + this.x = + this.y = + this.arc = + this.site = + this.cy = null; +} + +function d3_geom_voronoiAttachCircle(arc) { + var lArc = arc.P, + rArc = arc.N; + + if (!lArc || !rArc) return; + + var lSite = lArc.site, + cSite = arc.site, + rSite = rArc.site; + + if (lSite === rSite) return; + + var bx = cSite.x, + by = cSite.y, + ax = lSite.x - bx, + ay = lSite.y - by, + cx = rSite.x - bx, + cy = rSite.y - by; + + var d = 2 * (ax * cy - ay * cx); + if (d >= -ε2) return; + + var ha = ax * ax + ay * ay, + hc = cx * cx + cy * cy, + x = (cy * ha - ay * hc) / d, + y = (ax * hc - cx * ha) / d, + cy = y + by; + + var circle = d3_geom_voronoiCirclePool.pop() || new d3_geom_voronoiCircle; + circle.arc = arc; + circle.site = cSite; + circle.x = x + bx; + circle.y = cy + Math.sqrt(x * x + y * y); // y bottom + circle.cy = cy; + + arc.circle = circle; + + var before = null, + node = d3_geom_voronoiCircles._; + + while (node) { + if (circle.y < node.y || (circle.y === node.y && circle.x <= node.x)) { + if (node.L) node = node.L; + else { before = node.P; break; } + } else { + if (node.R) node = node.R; + else { before = node; break; } + } + } + + d3_geom_voronoiCircles.insert(before, circle); + if (!before) d3_geom_voronoiFirstCircle = circle; +} + +function d3_geom_voronoiDetachCircle(arc) { + var circle = arc.circle; + if (circle) { + if (!circle.P) d3_geom_voronoiFirstCircle = circle.N; + d3_geom_voronoiCircles.remove(circle); + d3_geom_voronoiCirclePool.push(circle); + d3_geom_voronoiRedBlackNode(circle); + arc.circle = null; + } +} diff --git a/web/nms.gathering.org/speedometer/d3-master/src/geom/voronoi/clip.js b/web/nms.gathering.org/speedometer/d3-master/src/geom/voronoi/clip.js new file mode 100644 index 0000000..e145965 --- /dev/null +++ b/web/nms.gathering.org/speedometer/d3-master/src/geom/voronoi/clip.js @@ -0,0 +1,80 @@ +import "../../math/abs"; +import "../clip-line"; + +function d3_geom_voronoiClipEdges(extent) { + var edges = d3_geom_voronoiEdges, + clip = d3_geom_clipLine(extent[0][0], extent[0][1], extent[1][0], extent[1][1]), + i = edges.length, + e; + while (i--) { + e = edges[i]; + if (!d3_geom_voronoiConnectEdge(e, extent) + || !clip(e) + || (abs(e.a.x - e.b.x) < ε && abs(e.a.y - e.b.y) < ε)) { + e.a = e.b = null; + edges.splice(i, 1); + } + } +} + +function d3_geom_voronoiConnectEdge(edge, extent) { + var vb = edge.b; + if (vb) return true; + + var va = edge.a, + x0 = extent[0][0], + x1 = extent[1][0], + y0 = extent[0][1], + y1 = extent[1][1], + lSite = edge.l, + rSite = edge.r, + lx = lSite.x, + ly = lSite.y, + rx = rSite.x, + ry = rSite.y, + fx = (lx + rx) / 2, + fy = (ly + ry) / 2, + fm, + fb; + + if (ry === ly) { + if (fx < x0 || fx >= x1) return; + if (lx > rx) { + if (!va) va = {x: fx, y: y0}; + else if (va.y >= y1) return; + vb = {x: fx, y: y1}; + } else { + if (!va) va = {x: fx, y: y1}; + else if (va.y < y0) return; + vb = {x: fx, y: y0}; + } + } else { + fm = (lx - rx) / (ry - ly); + fb = fy - fm * fx; + if (fm < -1 || fm > 1) { + if (lx > rx) { + if (!va) va = {x: (y0 - fb) / fm, y: y0}; + else if (va.y >= y1) return; + vb = {x: (y1 - fb) / fm, y: y1}; + } else { + if (!va) va = {x: (y1 - fb) / fm, y: y1}; + else if (va.y < y0) return; + vb = {x: (y0 - fb) / fm, y: y0}; + } + } else { + if (ly < ry) { + if (!va) va = {x: x0, y: fm * x0 + fb}; + else if (va.x >= x1) return; + vb = {x: x1, y: fm * x1 + fb}; + } else { + if (!va) va = {x: x1, y: fm * x1 + fb}; + else if (va.x < x0) return; + vb = {x: x0, y: fm * x0 + fb}; + } + } + } + + edge.a = va; + edge.b = vb; + return true; +} diff --git a/web/nms.gathering.org/speedometer/d3-master/src/geom/voronoi/edge.js b/web/nms.gathering.org/speedometer/d3-master/src/geom/voronoi/edge.js new file mode 100644 index 0000000..8e5a734 --- /dev/null +++ b/web/nms.gathering.org/speedometer/d3-master/src/geom/voronoi/edge.js @@ -0,0 +1,50 @@ +function d3_geom_voronoiEdge(lSite, rSite) { + this.l = lSite; + this.r = rSite; + this.a = this.b = null; // for border edges +} + +function d3_geom_voronoiCreateEdge(lSite, rSite, va, vb) { + var edge = new d3_geom_voronoiEdge(lSite, rSite); + d3_geom_voronoiEdges.push(edge); + if (va) d3_geom_voronoiSetEdgeEnd(edge, lSite, rSite, va); + if (vb) d3_geom_voronoiSetEdgeEnd(edge, rSite, lSite, vb); + d3_geom_voronoiCells[lSite.i].edges.push(new d3_geom_voronoiHalfEdge(edge, lSite, rSite)); + d3_geom_voronoiCells[rSite.i].edges.push(new d3_geom_voronoiHalfEdge(edge, rSite, lSite)); + return edge; +} + +function d3_geom_voronoiCreateBorderEdge(lSite, va, vb) { + var edge = new d3_geom_voronoiEdge(lSite, null); + edge.a = va; + edge.b = vb; + d3_geom_voronoiEdges.push(edge); + return edge; +} + +function d3_geom_voronoiSetEdgeEnd(edge, lSite, rSite, vertex) { + if (!edge.a && !edge.b) { + edge.a = vertex; + edge.l = lSite; + edge.r = rSite; + } else if (edge.l === rSite) { + edge.b = vertex; + } else { + edge.a = vertex; + } +} + +function d3_geom_voronoiHalfEdge(edge, lSite, rSite) { + var va = edge.a, + vb = edge.b; + this.edge = edge; + this.site = lSite; + this.angle = rSite ? Math.atan2(rSite.y - lSite.y, rSite.x - lSite.x) + : edge.l === lSite ? Math.atan2(vb.x - va.x, va.y - vb.y) + : Math.atan2(va.x - vb.x, vb.y - va.y); +}; + +d3_geom_voronoiHalfEdge.prototype = { + start: function() { return this.edge.l === this.site ? this.edge.a : this.edge.b; }, + end: function() { return this.edge.l === this.site ? this.edge.b : this.edge.a; } +}; diff --git a/web/nms.gathering.org/speedometer/d3-master/src/geom/voronoi/index.js b/web/nms.gathering.org/speedometer/d3-master/src/geom/voronoi/index.js new file mode 100644 index 0000000..a6c01a8 --- /dev/null +++ b/web/nms.gathering.org/speedometer/d3-master/src/geom/voronoi/index.js @@ -0,0 +1,59 @@ +import "../../math/trigonometry"; + +var d3_geom_voronoiEdges, + d3_geom_voronoiCells, + d3_geom_voronoiBeaches, + d3_geom_voronoiBeachPool = [], + d3_geom_voronoiFirstCircle, + d3_geom_voronoiCircles, + d3_geom_voronoiCirclePool = []; + +import "beach"; +import "cell"; +import "circle"; +import "clip"; +import "edge"; +import "red-black"; + +function d3_geom_voronoi(sites, bbox) { + var site = sites.sort(d3_geom_voronoiVertexOrder).pop(), + x0, + y0, + circle; + + d3_geom_voronoiEdges = []; + d3_geom_voronoiCells = new Array(sites.length); + d3_geom_voronoiBeaches = new d3_geom_voronoiRedBlackTree; + d3_geom_voronoiCircles = new d3_geom_voronoiRedBlackTree; + + while (true) { + circle = d3_geom_voronoiFirstCircle; + if (site && (!circle || site.y < circle.y || (site.y === circle.y && site.x < circle.x))) { + if (site.x !== x0 || site.y !== y0) { + d3_geom_voronoiCells[site.i] = new d3_geom_voronoiCell(site); + d3_geom_voronoiAddBeach(site); + x0 = site.x, y0 = site.y; + } + site = sites.pop(); + } else if (circle) { + d3_geom_voronoiRemoveBeach(circle.arc); + } else { + break; + } + } + + if (bbox) d3_geom_voronoiClipEdges(bbox), d3_geom_voronoiCloseCells(bbox); + + var diagram = {cells: d3_geom_voronoiCells, edges: d3_geom_voronoiEdges}; + + d3_geom_voronoiBeaches = + d3_geom_voronoiCircles = + d3_geom_voronoiEdges = + d3_geom_voronoiCells = null; + + return diagram; +}; + +function d3_geom_voronoiVertexOrder(a, b) { + return b.y - a.y || b.x - a.x; +} diff --git a/web/nms.gathering.org/speedometer/d3-master/src/geom/voronoi/red-black.js b/web/nms.gathering.org/speedometer/d3-master/src/geom/voronoi/red-black.js new file mode 100644 index 0000000..7cf6880 --- /dev/null +++ b/web/nms.gathering.org/speedometer/d3-master/src/geom/voronoi/red-black.js @@ -0,0 +1,235 @@ +function d3_geom_voronoiRedBlackTree() { + this._ = null; // root node +} + +function d3_geom_voronoiRedBlackNode(node) { + node.U = // parent node + node.C = // color - true for red, false for black + node.L = // left node + node.R = // right node + node.P = // previous node + node.N = null; // next node +} + +d3_geom_voronoiRedBlackTree.prototype = { + + insert: function(after, node) { + var parent, grandpa, uncle; + + if (after) { + node.P = after; + node.N = after.N; + if (after.N) after.N.P = node; + after.N = node; + if (after.R) { + after = after.R; + while (after.L) after = after.L; + after.L = node; + } else { + after.R = node; + } + parent = after; + } else if (this._) { + after = d3_geom_voronoiRedBlackFirst(this._); + node.P = null; + node.N = after; + after.P = after.L = node; + parent = after; + } else { + node.P = node.N = null; + this._ = node; + parent = null; + } + node.L = node.R = null; + node.U = parent; + node.C = true; + + after = node; + while (parent && parent.C) { + grandpa = parent.U; + if (parent === grandpa.L) { + uncle = grandpa.R; + if (uncle && uncle.C) { + parent.C = uncle.C = false; + grandpa.C = true; + after = grandpa; + } else { + if (after === parent.R) { + d3_geom_voronoiRedBlackRotateLeft(this, parent); + after = parent; + parent = after.U; + } + parent.C = false; + grandpa.C = true; + d3_geom_voronoiRedBlackRotateRight(this, grandpa); + } + } else { + uncle = grandpa.L; + if (uncle && uncle.C) { + parent.C = uncle.C = false; + grandpa.C = true; + after = grandpa; + } else { + if (after === parent.L) { + d3_geom_voronoiRedBlackRotateRight(this, parent); + after = parent; + parent = after.U; + } + parent.C = false; + grandpa.C = true; + d3_geom_voronoiRedBlackRotateLeft(this, grandpa); + } + } + parent = after.U; + } + this._.C = false; + }, + + remove: function(node) { + if (node.N) node.N.P = node.P; + if (node.P) node.P.N = node.N; + node.N = node.P = null; + + var parent = node.U, + sibling, + left = node.L, + right = node.R, + next, + red; + + if (!left) next = right; + else if (!right) next = left; + else next = d3_geom_voronoiRedBlackFirst(right); + + if (parent) { + if (parent.L === node) parent.L = next; + else parent.R = next; + } else { + this._ = next; + } + + if (left && right) { + red = next.C; + next.C = node.C; + next.L = left; + left.U = next; + if (next !== right) { + parent = next.U; + next.U = node.U; + node = next.R; + parent.L = node; + next.R = right; + right.U = next; + } else { + next.U = parent; + parent = next; + node = next.R; + } + } else { + red = node.C; + node = next; + } + + if (node) node.U = parent; + if (red) return; + if (node && node.C) { node.C = false; return; } + + do { + if (node === this._) break; + if (node === parent.L) { + sibling = parent.R; + if (sibling.C) { + sibling.C = false; + parent.C = true; + d3_geom_voronoiRedBlackRotateLeft(this, parent); + sibling = parent.R; + } + if ((sibling.L && sibling.L.C) + || (sibling.R && sibling.R.C)) { + if (!sibling.R || !sibling.R.C) { + sibling.L.C = false; + sibling.C = true; + d3_geom_voronoiRedBlackRotateRight(this, sibling); + sibling = parent.R; + } + sibling.C = parent.C; + parent.C = sibling.R.C = false; + d3_geom_voronoiRedBlackRotateLeft(this, parent); + node = this._; + break; + } + } else { + sibling = parent.L; + if (sibling.C) { + sibling.C = false; + parent.C = true; + d3_geom_voronoiRedBlackRotateRight(this, parent); + sibling = parent.L; + } + if ((sibling.L && sibling.L.C) + || (sibling.R && sibling.R.C)) { + if (!sibling.L || !sibling.L.C) { + sibling.R.C = false; + sibling.C = true; + d3_geom_voronoiRedBlackRotateLeft(this, sibling); + sibling = parent.L; + } + sibling.C = parent.C; + parent.C = sibling.L.C = false; + d3_geom_voronoiRedBlackRotateRight(this, parent); + node = this._; + break; + } + } + sibling.C = true; + node = parent; + parent = parent.U; + } while (!node.C); + + if (node) node.C = false; + } + +}; + +function d3_geom_voronoiRedBlackRotateLeft(tree, node) { + var p = node, + q = node.R, + parent = p.U; + + if (parent) { + if (parent.L === p) parent.L = q; + else parent.R = q; + } else { + tree._ = q; + } + + q.U = parent; + p.U = q; + p.R = q.L; + if (p.R) p.R.U = p; + q.L = p; +} + +function d3_geom_voronoiRedBlackRotateRight(tree, node) { + var p = node, + q = node.L, + parent = p.U; + + if (parent) { + if (parent.L === p) parent.L = q; + else parent.R = q; + } else { + tree._ = q; + } + + q.U = parent; + p.U = q; + p.L = q.R; + if (p.L) p.L.U = p; + q.R = p; +} + +function d3_geom_voronoiRedBlackFirst(node) { + while (node.L) node = node.L; + return node; +} |