1911 lines
53 KiB
JavaScript
1911 lines
53 KiB
JavaScript
// https://github.com/topojson/topojson Version 2.2.0. Copyright 2016 Mike Bostock.
|
||
(function (global, factory) {
|
||
typeof exports === 'object' && typeof module !== 'undefined' ? factory(exports) :
|
||
typeof define === 'function' && define.amd ? define(['exports'], factory) :
|
||
(factory((global.topojson = global.topojson || {})));
|
||
}(this, (function (exports) { 'use strict';
|
||
|
||
// Computes the bounding box of the specified hash of GeoJSON objects.
|
||
var bounds = function(objects) {
|
||
var x0 = Infinity,
|
||
y0 = Infinity,
|
||
x1 = -Infinity,
|
||
y1 = -Infinity;
|
||
|
||
function boundGeometry(geometry) {
|
||
if (geometry && boundGeometryType.hasOwnProperty(geometry.type)) boundGeometryType[geometry.type](geometry);
|
||
}
|
||
|
||
var boundGeometryType = {
|
||
GeometryCollection: function(o) { o.geometries.forEach(boundGeometry); },
|
||
Point: function(o) { boundPoint(o.coordinates); },
|
||
MultiPoint: function(o) { o.coordinates.forEach(boundPoint); },
|
||
LineString: function(o) { boundLine(o.coordinates); },
|
||
MultiLineString: function(o) { o.coordinates.forEach(boundLine); },
|
||
Polygon: function(o) { o.coordinates.forEach(boundLine); },
|
||
MultiPolygon: function(o) { o.coordinates.forEach(boundMultiLine); }
|
||
};
|
||
|
||
function boundPoint(coordinates) {
|
||
var x = coordinates[0],
|
||
y = coordinates[1];
|
||
if (x < x0) x0 = x;
|
||
if (x > x1) x1 = x;
|
||
if (y < y0) y0 = y;
|
||
if (y > y1) y1 = y;
|
||
}
|
||
|
||
function boundLine(coordinates) {
|
||
coordinates.forEach(boundPoint);
|
||
}
|
||
|
||
function boundMultiLine(coordinates) {
|
||
coordinates.forEach(boundLine);
|
||
}
|
||
|
||
for (var key in objects) {
|
||
boundGeometry(objects[key]);
|
||
}
|
||
|
||
return x1 >= x0 && y1 >= y0 ? [x0, y0, x1, y1] : undefined;
|
||
};
|
||
|
||
var hashset = function(size, hash, equal, type, empty) {
|
||
if (arguments.length === 3) {
|
||
type = Array;
|
||
empty = null;
|
||
}
|
||
|
||
var store = new type(size = 1 << Math.max(4, Math.ceil(Math.log(size) / Math.LN2))),
|
||
mask = size - 1;
|
||
|
||
for (var i = 0; i < size; ++i) {
|
||
store[i] = empty;
|
||
}
|
||
|
||
function add(value) {
|
||
var index = hash(value) & mask,
|
||
match = store[index],
|
||
collisions = 0;
|
||
while (match != empty) {
|
||
if (equal(match, value)) return true;
|
||
if (++collisions >= size) throw new Error("full hashset");
|
||
match = store[index = (index + 1) & mask];
|
||
}
|
||
store[index] = value;
|
||
return true;
|
||
}
|
||
|
||
function has(value) {
|
||
var index = hash(value) & mask,
|
||
match = store[index],
|
||
collisions = 0;
|
||
while (match != empty) {
|
||
if (equal(match, value)) return true;
|
||
if (++collisions >= size) break;
|
||
match = store[index = (index + 1) & mask];
|
||
}
|
||
return false;
|
||
}
|
||
|
||
function values() {
|
||
var values = [];
|
||
for (var i = 0, n = store.length; i < n; ++i) {
|
||
var match = store[i];
|
||
if (match != empty) values.push(match);
|
||
}
|
||
return values;
|
||
}
|
||
|
||
return {
|
||
add: add,
|
||
has: has,
|
||
values: values
|
||
};
|
||
};
|
||
|
||
var hashmap = function(size, hash, equal, keyType, keyEmpty, valueType) {
|
||
if (arguments.length === 3) {
|
||
keyType = valueType = Array;
|
||
keyEmpty = null;
|
||
}
|
||
|
||
var keystore = new keyType(size = 1 << Math.max(4, Math.ceil(Math.log(size) / Math.LN2))),
|
||
valstore = new valueType(size),
|
||
mask = size - 1;
|
||
|
||
for (var i = 0; i < size; ++i) {
|
||
keystore[i] = keyEmpty;
|
||
}
|
||
|
||
function set(key, value) {
|
||
var index = hash(key) & mask,
|
||
matchKey = keystore[index],
|
||
collisions = 0;
|
||
while (matchKey != keyEmpty) {
|
||
if (equal(matchKey, key)) return valstore[index] = value;
|
||
if (++collisions >= size) throw new Error("full hashmap");
|
||
matchKey = keystore[index = (index + 1) & mask];
|
||
}
|
||
keystore[index] = key;
|
||
valstore[index] = value;
|
||
return value;
|
||
}
|
||
|
||
function maybeSet(key, value) {
|
||
var index = hash(key) & mask,
|
||
matchKey = keystore[index],
|
||
collisions = 0;
|
||
while (matchKey != keyEmpty) {
|
||
if (equal(matchKey, key)) return valstore[index];
|
||
if (++collisions >= size) throw new Error("full hashmap");
|
||
matchKey = keystore[index = (index + 1) & mask];
|
||
}
|
||
keystore[index] = key;
|
||
valstore[index] = value;
|
||
return value;
|
||
}
|
||
|
||
function get(key, missingValue) {
|
||
var index = hash(key) & mask,
|
||
matchKey = keystore[index],
|
||
collisions = 0;
|
||
while (matchKey != keyEmpty) {
|
||
if (equal(matchKey, key)) return valstore[index];
|
||
if (++collisions >= size) break;
|
||
matchKey = keystore[index = (index + 1) & mask];
|
||
}
|
||
return missingValue;
|
||
}
|
||
|
||
function keys() {
|
||
var keys = [];
|
||
for (var i = 0, n = keystore.length; i < n; ++i) {
|
||
var matchKey = keystore[i];
|
||
if (matchKey != keyEmpty) keys.push(matchKey);
|
||
}
|
||
return keys;
|
||
}
|
||
|
||
return {
|
||
set: set,
|
||
maybeSet: maybeSet, // set if unset
|
||
get: get,
|
||
keys: keys
|
||
};
|
||
};
|
||
|
||
var equalPoint = function(pointA, pointB) {
|
||
return pointA[0] === pointB[0] && pointA[1] === pointB[1];
|
||
};
|
||
|
||
// TODO if quantized, use simpler Int32 hashing?
|
||
|
||
var buffer = new ArrayBuffer(16);
|
||
var floats = new Float64Array(buffer);
|
||
var uints = new Uint32Array(buffer);
|
||
|
||
var hashPoint = function(point) {
|
||
floats[0] = point[0];
|
||
floats[1] = point[1];
|
||
var hash = uints[0] ^ uints[1];
|
||
hash = hash << 5 ^ hash >> 7 ^ uints[2] ^ uints[3];
|
||
return hash & 0x7fffffff;
|
||
};
|
||
|
||
// Given an extracted (pre-)topology, identifies all of the junctions. These are
|
||
// the points at which arcs (lines or rings) will need to be cut so that each
|
||
// arc is represented uniquely.
|
||
//
|
||
// A junction is a point where at least one arc deviates from another arc going
|
||
// through the same point. For example, consider the point B. If there is a arc
|
||
// through ABC and another arc through CBA, then B is not a junction because in
|
||
// both cases the adjacent point pairs are {A,C}. However, if there is an
|
||
// additional arc ABD, then {A,D} != {A,C}, and thus B becomes a junction.
|
||
//
|
||
// For a closed ring ABCA, the first point A’s adjacent points are the second
|
||
// and last point {B,C}. For a line, the first and last point are always
|
||
// considered junctions, even if the line is closed; this ensures that a closed
|
||
// line is never rotated.
|
||
var join = function(topology) {
|
||
var coordinates = topology.coordinates,
|
||
lines = topology.lines,
|
||
rings = topology.rings,
|
||
indexes = index(),
|
||
visitedByIndex = new Int32Array(coordinates.length),
|
||
leftByIndex = new Int32Array(coordinates.length),
|
||
rightByIndex = new Int32Array(coordinates.length),
|
||
junctionByIndex = new Int8Array(coordinates.length),
|
||
junctionCount = 0, // upper bound on number of junctions
|
||
i, n,
|
||
previousIndex,
|
||
currentIndex,
|
||
nextIndex;
|
||
|
||
for (i = 0, n = coordinates.length; i < n; ++i) {
|
||
visitedByIndex[i] = leftByIndex[i] = rightByIndex[i] = -1;
|
||
}
|
||
|
||
for (i = 0, n = lines.length; i < n; ++i) {
|
||
var line = lines[i],
|
||
lineStart = line[0],
|
||
lineEnd = line[1];
|
||
currentIndex = indexes[lineStart];
|
||
nextIndex = indexes[++lineStart];
|
||
++junctionCount, junctionByIndex[currentIndex] = 1; // start
|
||
while (++lineStart <= lineEnd) {
|
||
sequence(i, previousIndex = currentIndex, currentIndex = nextIndex, nextIndex = indexes[lineStart]);
|
||
}
|
||
++junctionCount, junctionByIndex[nextIndex] = 1; // end
|
||
}
|
||
|
||
for (i = 0, n = coordinates.length; i < n; ++i) {
|
||
visitedByIndex[i] = -1;
|
||
}
|
||
|
||
for (i = 0, n = rings.length; i < n; ++i) {
|
||
var ring = rings[i],
|
||
ringStart = ring[0] + 1,
|
||
ringEnd = ring[1];
|
||
previousIndex = indexes[ringEnd - 1];
|
||
currentIndex = indexes[ringStart - 1];
|
||
nextIndex = indexes[ringStart];
|
||
sequence(i, previousIndex, currentIndex, nextIndex);
|
||
while (++ringStart <= ringEnd) {
|
||
sequence(i, previousIndex = currentIndex, currentIndex = nextIndex, nextIndex = indexes[ringStart]);
|
||
}
|
||
}
|
||
|
||
function sequence(i, previousIndex, currentIndex, nextIndex) {
|
||
if (visitedByIndex[currentIndex] === i) return; // ignore self-intersection
|
||
visitedByIndex[currentIndex] = i;
|
||
var leftIndex = leftByIndex[currentIndex];
|
||
if (leftIndex >= 0) {
|
||
var rightIndex = rightByIndex[currentIndex];
|
||
if ((leftIndex !== previousIndex || rightIndex !== nextIndex)
|
||
&& (leftIndex !== nextIndex || rightIndex !== previousIndex)) {
|
||
++junctionCount, junctionByIndex[currentIndex] = 1;
|
||
}
|
||
} else {
|
||
leftByIndex[currentIndex] = previousIndex;
|
||
rightByIndex[currentIndex] = nextIndex;
|
||
}
|
||
}
|
||
|
||
function index() {
|
||
var indexByPoint = hashmap(coordinates.length * 1.4, hashIndex, equalIndex, Int32Array, -1, Int32Array),
|
||
indexes = new Int32Array(coordinates.length);
|
||
|
||
for (var i = 0, n = coordinates.length; i < n; ++i) {
|
||
indexes[i] = indexByPoint.maybeSet(i, i);
|
||
}
|
||
|
||
return indexes;
|
||
}
|
||
|
||
function hashIndex(i) {
|
||
return hashPoint(coordinates[i]);
|
||
}
|
||
|
||
function equalIndex(i, j) {
|
||
return equalPoint(coordinates[i], coordinates[j]);
|
||
}
|
||
|
||
visitedByIndex = leftByIndex = rightByIndex = null;
|
||
|
||
var junctionByPoint = hashset(junctionCount * 1.4, hashPoint, equalPoint), j;
|
||
|
||
// Convert back to a standard hashset by point for caller convenience.
|
||
for (i = 0, n = coordinates.length; i < n; ++i) {
|
||
if (junctionByIndex[j = indexes[i]]) {
|
||
junctionByPoint.add(coordinates[j]);
|
||
}
|
||
}
|
||
|
||
return junctionByPoint;
|
||
};
|
||
|
||
// Given an extracted (pre-)topology, cuts (or rotates) arcs so that all shared
|
||
// point sequences are identified. The topology can then be subsequently deduped
|
||
// to remove exact duplicate arcs.
|
||
var cut = function(topology) {
|
||
var junctions = join(topology),
|
||
coordinates = topology.coordinates,
|
||
lines = topology.lines,
|
||
rings = topology.rings,
|
||
next,
|
||
i, n;
|
||
|
||
for (i = 0, n = lines.length; i < n; ++i) {
|
||
var line = lines[i],
|
||
lineMid = line[0],
|
||
lineEnd = line[1];
|
||
while (++lineMid < lineEnd) {
|
||
if (junctions.has(coordinates[lineMid])) {
|
||
next = {0: lineMid, 1: line[1]};
|
||
line[1] = lineMid;
|
||
line = line.next = next;
|
||
}
|
||
}
|
||
}
|
||
|
||
for (i = 0, n = rings.length; i < n; ++i) {
|
||
var ring = rings[i],
|
||
ringStart = ring[0],
|
||
ringMid = ringStart,
|
||
ringEnd = ring[1],
|
||
ringFixed = junctions.has(coordinates[ringStart]);
|
||
while (++ringMid < ringEnd) {
|
||
if (junctions.has(coordinates[ringMid])) {
|
||
if (ringFixed) {
|
||
next = {0: ringMid, 1: ring[1]};
|
||
ring[1] = ringMid;
|
||
ring = ring.next = next;
|
||
} else { // For the first junction, we can rotate rather than cut.
|
||
rotateArray(coordinates, ringStart, ringEnd, ringEnd - ringMid);
|
||
coordinates[ringEnd] = coordinates[ringStart];
|
||
ringFixed = true;
|
||
ringMid = ringStart; // restart; we may have skipped junctions
|
||
}
|
||
}
|
||
}
|
||
}
|
||
|
||
return topology;
|
||
};
|
||
|
||
function rotateArray(array, start, end, offset) {
|
||
reverse(array, start, end);
|
||
reverse(array, start, start + offset);
|
||
reverse(array, start + offset, end);
|
||
}
|
||
|
||
function reverse(array, start, end) {
|
||
for (var mid = start + ((end-- - start) >> 1), t; start < mid; ++start, --end) {
|
||
t = array[start], array[start] = array[end], array[end] = t;
|
||
}
|
||
}
|
||
|
||
// Given a cut topology, combines duplicate arcs.
|
||
var dedup = function(topology) {
|
||
var coordinates = topology.coordinates,
|
||
lines = topology.lines, line,
|
||
rings = topology.rings, ring,
|
||
arcCount = lines.length + rings.length,
|
||
i, n;
|
||
|
||
delete topology.lines;
|
||
delete topology.rings;
|
||
|
||
// Count the number of (non-unique) arcs to initialize the hashmap safely.
|
||
for (i = 0, n = lines.length; i < n; ++i) {
|
||
line = lines[i]; while (line = line.next) ++arcCount;
|
||
}
|
||
for (i = 0, n = rings.length; i < n; ++i) {
|
||
ring = rings[i]; while (ring = ring.next) ++arcCount;
|
||
}
|
||
|
||
var arcsByEnd = hashmap(arcCount * 2 * 1.4, hashPoint, equalPoint),
|
||
arcs = topology.arcs = [];
|
||
|
||
for (i = 0, n = lines.length; i < n; ++i) {
|
||
line = lines[i];
|
||
do {
|
||
dedupLine(line);
|
||
} while (line = line.next);
|
||
}
|
||
|
||
for (i = 0, n = rings.length; i < n; ++i) {
|
||
ring = rings[i];
|
||
if (ring.next) { // arc is no longer closed
|
||
do {
|
||
dedupLine(ring);
|
||
} while (ring = ring.next);
|
||
} else {
|
||
dedupRing(ring);
|
||
}
|
||
}
|
||
|
||
function dedupLine(arc) {
|
||
var startPoint,
|
||
endPoint,
|
||
startArcs, startArc,
|
||
endArcs, endArc,
|
||
i, n;
|
||
|
||
// Does this arc match an existing arc in order?
|
||
if (startArcs = arcsByEnd.get(startPoint = coordinates[arc[0]])) {
|
||
for (i = 0, n = startArcs.length; i < n; ++i) {
|
||
startArc = startArcs[i];
|
||
if (equalLine(startArc, arc)) {
|
||
arc[0] = startArc[0];
|
||
arc[1] = startArc[1];
|
||
return;
|
||
}
|
||
}
|
||
}
|
||
|
||
// Does this arc match an existing arc in reverse order?
|
||
if (endArcs = arcsByEnd.get(endPoint = coordinates[arc[1]])) {
|
||
for (i = 0, n = endArcs.length; i < n; ++i) {
|
||
endArc = endArcs[i];
|
||
if (reverseEqualLine(endArc, arc)) {
|
||
arc[1] = endArc[0];
|
||
arc[0] = endArc[1];
|
||
return;
|
||
}
|
||
}
|
||
}
|
||
|
||
if (startArcs) startArcs.push(arc); else arcsByEnd.set(startPoint, [arc]);
|
||
if (endArcs) endArcs.push(arc); else arcsByEnd.set(endPoint, [arc]);
|
||
arcs.push(arc);
|
||
}
|
||
|
||
function dedupRing(arc) {
|
||
var endPoint,
|
||
endArcs,
|
||
endArc,
|
||
i, n;
|
||
|
||
// Does this arc match an existing line in order, or reverse order?
|
||
// Rings are closed, so their start point and end point is the same.
|
||
if (endArcs = arcsByEnd.get(endPoint = coordinates[arc[0]])) {
|
||
for (i = 0, n = endArcs.length; i < n; ++i) {
|
||
endArc = endArcs[i];
|
||
if (equalRing(endArc, arc)) {
|
||
arc[0] = endArc[0];
|
||
arc[1] = endArc[1];
|
||
return;
|
||
}
|
||
if (reverseEqualRing(endArc, arc)) {
|
||
arc[0] = endArc[1];
|
||
arc[1] = endArc[0];
|
||
return;
|
||
}
|
||
}
|
||
}
|
||
|
||
// Otherwise, does this arc match an existing ring in order, or reverse order?
|
||
if (endArcs = arcsByEnd.get(endPoint = coordinates[arc[0] + findMinimumOffset(arc)])) {
|
||
for (i = 0, n = endArcs.length; i < n; ++i) {
|
||
endArc = endArcs[i];
|
||
if (equalRing(endArc, arc)) {
|
||
arc[0] = endArc[0];
|
||
arc[1] = endArc[1];
|
||
return;
|
||
}
|
||
if (reverseEqualRing(endArc, arc)) {
|
||
arc[0] = endArc[1];
|
||
arc[1] = endArc[0];
|
||
return;
|
||
}
|
||
}
|
||
}
|
||
|
||
if (endArcs) endArcs.push(arc); else arcsByEnd.set(endPoint, [arc]);
|
||
arcs.push(arc);
|
||
}
|
||
|
||
function equalLine(arcA, arcB) {
|
||
var ia = arcA[0], ib = arcB[0],
|
||
ja = arcA[1], jb = arcB[1];
|
||
if (ia - ja !== ib - jb) return false;
|
||
for (; ia <= ja; ++ia, ++ib) if (!equalPoint(coordinates[ia], coordinates[ib])) return false;
|
||
return true;
|
||
}
|
||
|
||
function reverseEqualLine(arcA, arcB) {
|
||
var ia = arcA[0], ib = arcB[0],
|
||
ja = arcA[1], jb = arcB[1];
|
||
if (ia - ja !== ib - jb) return false;
|
||
for (; ia <= ja; ++ia, --jb) if (!equalPoint(coordinates[ia], coordinates[jb])) return false;
|
||
return true;
|
||
}
|
||
|
||
function equalRing(arcA, arcB) {
|
||
var ia = arcA[0], ib = arcB[0],
|
||
ja = arcA[1], jb = arcB[1],
|
||
n = ja - ia;
|
||
if (n !== jb - ib) return false;
|
||
var ka = findMinimumOffset(arcA),
|
||
kb = findMinimumOffset(arcB);
|
||
for (var i = 0; i < n; ++i) {
|
||
if (!equalPoint(coordinates[ia + (i + ka) % n], coordinates[ib + (i + kb) % n])) return false;
|
||
}
|
||
return true;
|
||
}
|
||
|
||
function reverseEqualRing(arcA, arcB) {
|
||
var ia = arcA[0], ib = arcB[0],
|
||
ja = arcA[1], jb = arcB[1],
|
||
n = ja - ia;
|
||
if (n !== jb - ib) return false;
|
||
var ka = findMinimumOffset(arcA),
|
||
kb = n - findMinimumOffset(arcB);
|
||
for (var i = 0; i < n; ++i) {
|
||
if (!equalPoint(coordinates[ia + (i + ka) % n], coordinates[jb - (i + kb) % n])) return false;
|
||
}
|
||
return true;
|
||
}
|
||
|
||
// Rings are rotated to a consistent, but arbitrary, start point.
|
||
// This is necessary to detect when a ring and a rotated copy are dupes.
|
||
function findMinimumOffset(arc) {
|
||
var start = arc[0],
|
||
end = arc[1],
|
||
mid = start,
|
||
minimum = mid,
|
||
minimumPoint = coordinates[mid];
|
||
while (++mid < end) {
|
||
var point = coordinates[mid];
|
||
if (point[0] < minimumPoint[0] || point[0] === minimumPoint[0] && point[1] < minimumPoint[1]) {
|
||
minimum = mid;
|
||
minimumPoint = point;
|
||
}
|
||
}
|
||
return minimum - start;
|
||
}
|
||
|
||
return topology;
|
||
};
|
||
|
||
// Given a TopoJSON topology in absolute (quantized) coordinates,
|
||
// converts to fixed-point delta encoding.
|
||
// This is a destructive operation that modifies the given topology!
|
||
var delta = function(topology) {
|
||
var arcs = topology.arcs,
|
||
i = -1,
|
||
n = arcs.length;
|
||
|
||
while (++i < n) {
|
||
var arc = arcs[i],
|
||
j = 0,
|
||
m = arc.length,
|
||
point = arc[0],
|
||
x0 = point[0],
|
||
y0 = point[1],
|
||
x1,
|
||
y1;
|
||
while (++j < m) {
|
||
point = arc[j];
|
||
x1 = point[0];
|
||
y1 = point[1];
|
||
arc[j] = [x1 - x0, y1 - y0];
|
||
x0 = x1;
|
||
y0 = y1;
|
||
}
|
||
}
|
||
|
||
return topology;
|
||
};
|
||
|
||
// Extracts the lines and rings from the specified hash of geometry objects.
|
||
//
|
||
// Returns an object with three properties:
|
||
//
|
||
// * coordinates - shared buffer of [x, y] coordinates
|
||
// * lines - lines extracted from the hash, of the form [start, end]
|
||
// * rings - rings extracted from the hash, of the form [start, end]
|
||
//
|
||
// For each ring or line, start and end represent inclusive indexes into the
|
||
// coordinates buffer. For rings (and closed lines), coordinates[start] equals
|
||
// coordinates[end].
|
||
//
|
||
// For each line or polygon geometry in the input hash, including nested
|
||
// geometries as in geometry collections, the `coordinates` array is replaced
|
||
// with an equivalent `arcs` array that, for each line (for line string
|
||
// geometries) or ring (for polygon geometries), points to one of the above
|
||
// lines or rings.
|
||
var extract = function(objects) {
|
||
var index = -1,
|
||
lines = [],
|
||
rings = [],
|
||
coordinates = [];
|
||
|
||
function extractGeometry(geometry) {
|
||
if (geometry && extractGeometryType.hasOwnProperty(geometry.type)) extractGeometryType[geometry.type](geometry);
|
||
}
|
||
|
||
var extractGeometryType = {
|
||
GeometryCollection: function(o) { o.geometries.forEach(extractGeometry); },
|
||
LineString: function(o) { o.arcs = extractLine(o.coordinates); delete o.coordinates; },
|
||
MultiLineString: function(o) { o.arcs = o.coordinates.map(extractLine); delete o.coordinates; },
|
||
Polygon: function(o) { o.arcs = o.coordinates.map(extractRing); delete o.coordinates; },
|
||
MultiPolygon: function(o) { o.arcs = o.coordinates.map(extractMultiRing); delete o.coordinates; }
|
||
};
|
||
|
||
function extractLine(line) {
|
||
for (var i = 0, n = line.length; i < n; ++i) coordinates[++index] = line[i];
|
||
var arc = {0: index - n + 1, 1: index};
|
||
lines.push(arc);
|
||
return arc;
|
||
}
|
||
|
||
function extractRing(ring) {
|
||
for (var i = 0, n = ring.length; i < n; ++i) coordinates[++index] = ring[i];
|
||
var arc = {0: index - n + 1, 1: index};
|
||
rings.push(arc);
|
||
return arc;
|
||
}
|
||
|
||
function extractMultiRing(rings) {
|
||
return rings.map(extractRing);
|
||
}
|
||
|
||
for (var key in objects) {
|
||
extractGeometry(objects[key]);
|
||
}
|
||
|
||
return {
|
||
type: "Topology",
|
||
coordinates: coordinates,
|
||
lines: lines,
|
||
rings: rings,
|
||
objects: objects
|
||
};
|
||
};
|
||
|
||
// Given a hash of GeoJSON objects, replaces Features with geometry objects.
|
||
// This is a destructive operation that modifies the input objects!
|
||
var geometry = function(objects) {
|
||
var key;
|
||
for (key in objects) objects[key] = geomifyObject(objects[key]);
|
||
return objects;
|
||
};
|
||
|
||
function geomifyObject(object) {
|
||
return (object && geomifyObjectType.hasOwnProperty(object.type)
|
||
? geomifyObjectType[object.type]
|
||
: geomifyGeometry)(object);
|
||
}
|
||
|
||
function geomifyFeature(feature) {
|
||
var geometry = feature.geometry;
|
||
if (geometry == null) {
|
||
feature.type = null;
|
||
} else {
|
||
geomifyGeometry(geometry);
|
||
feature.type = geometry.type;
|
||
if (geometry.geometries) feature.geometries = geometry.geometries;
|
||
else if (geometry.coordinates) feature.coordinates = geometry.coordinates;
|
||
if (geometry.bbox) feature.bbox = geometry.bbox;
|
||
}
|
||
delete feature.geometry;
|
||
return feature;
|
||
}
|
||
|
||
function geomifyGeometry(geometry) {
|
||
if (!geometry) return {type: null};
|
||
if (geomifyGeometryType.hasOwnProperty(geometry.type)) geomifyGeometryType[geometry.type](geometry);
|
||
return geometry;
|
||
}
|
||
|
||
var geomifyObjectType = {
|
||
Feature: geomifyFeature,
|
||
FeatureCollection: function(collection) {
|
||
collection.type = "GeometryCollection";
|
||
collection.geometries = collection.features;
|
||
collection.features.forEach(geomifyFeature);
|
||
delete collection.features;
|
||
return collection;
|
||
}
|
||
};
|
||
|
||
var geomifyGeometryType = {
|
||
GeometryCollection: function(o) {
|
||
var geometries = o.geometries, i = -1, n = geometries.length;
|
||
while (++i < n) geometries[i] = geomifyGeometry(geometries[i]);
|
||
},
|
||
MultiPoint: function(o) {
|
||
if (!o.coordinates.length) {
|
||
o.type = null;
|
||
delete o.coordinates;
|
||
} else if (o.coordinates.length < 2) {
|
||
o.type = "Point";
|
||
o.coordinates = o.coordinates[0];
|
||
}
|
||
},
|
||
LineString: function(o) {
|
||
if (!o.coordinates.length) {
|
||
o.type = null;
|
||
delete o.coordinates;
|
||
}
|
||
},
|
||
MultiLineString: function(o) {
|
||
for (var lines = o.coordinates, i = 0, N = 0, n = lines.length; i < n; ++i) {
|
||
var line = lines[i];
|
||
if (line.length) lines[N++] = line;
|
||
}
|
||
if (!N) {
|
||
o.type = null;
|
||
delete o.coordinates;
|
||
} else if (N < 2) {
|
||
o.type = "LineString";
|
||
o.coordinates = lines[0];
|
||
} else {
|
||
o.coordinates.length = N;
|
||
}
|
||
},
|
||
Polygon: function(o) {
|
||
for (var rings = o.coordinates, i = 0, N = 0, n = rings.length; i < n; ++i) {
|
||
var ring = rings[i];
|
||
if (ring.length) rings[N++] = ring;
|
||
}
|
||
if (!N) {
|
||
o.type = null;
|
||
delete o.coordinates;
|
||
} else {
|
||
o.coordinates.length = N;
|
||
}
|
||
},
|
||
MultiPolygon: function(o) {
|
||
for (var polygons = o.coordinates, j = 0, M = 0, m = polygons.length; j < m; ++j) {
|
||
for (var rings = polygons[j], i = 0, N = 0, n = rings.length; i < n; ++i) {
|
||
var ring = rings[i];
|
||
if (ring.length) rings[N++] = ring;
|
||
}
|
||
if (N) {
|
||
rings.length = N;
|
||
polygons[M++] = rings;
|
||
}
|
||
}
|
||
if (!M) {
|
||
o.type = null;
|
||
delete o.coordinates;
|
||
} else if (M < 2) {
|
||
o.type = "Polygon";
|
||
o.coordinates = polygons[0];
|
||
} else {
|
||
polygons.length = M;
|
||
}
|
||
}
|
||
};
|
||
|
||
var prequantize = function(objects, bbox, n) {
|
||
var x0 = bbox[0],
|
||
y0 = bbox[1],
|
||
x1 = bbox[2],
|
||
y1 = bbox[3],
|
||
kx = x1 - x0 ? (n - 1) / (x1 - x0) : 1,
|
||
ky = y1 - y0 ? (n - 1) / (y1 - y0) : 1;
|
||
|
||
function quantizePoint(coordinates) {
|
||
coordinates[0] = Math.round((coordinates[0] - x0) * kx);
|
||
coordinates[1] = Math.round((coordinates[1] - y0) * ky);
|
||
return coordinates;
|
||
}
|
||
|
||
function quantizeLine(coordinates) {
|
||
var i = 0,
|
||
j = 1,
|
||
n = coordinates.length,
|
||
pi = quantizePoint(coordinates[0]),
|
||
pj,
|
||
px = pi[0],
|
||
py = pi[1],
|
||
x,
|
||
y;
|
||
|
||
while (++i < n) {
|
||
pi = quantizePoint(coordinates[i]);
|
||
x = pi[0];
|
||
y = pi[1];
|
||
if (x !== px || y !== py) { // skip coincident points
|
||
pj = coordinates[j++];
|
||
pj[0] = px = x;
|
||
pj[1] = py = y;
|
||
}
|
||
}
|
||
|
||
coordinates.length = j;
|
||
}
|
||
|
||
function quantizeGeometry(o) {
|
||
if (o && quantizeGeometryType.hasOwnProperty(o.type)) quantizeGeometryType[o.type](o);
|
||
}
|
||
|
||
var quantizeGeometryType = {
|
||
GeometryCollection: function(o) {
|
||
o.geometries.forEach(quantizeGeometry);
|
||
},
|
||
Point: function(o) {
|
||
quantizePoint(o.coordinates);
|
||
},
|
||
MultiPoint: function(o) {
|
||
o.coordinates.forEach(quantizePoint);
|
||
},
|
||
LineString: function(o) {
|
||
var line = o.coordinates;
|
||
quantizeLine(line);
|
||
if (line.length < 2) line[1] = line[0]; // must have 2+
|
||
},
|
||
MultiLineString: function(o) {
|
||
for (var lines = o.coordinates, i = 0, n = lines.length; i < n; ++i) {
|
||
var line = lines[i];
|
||
quantizeLine(line);
|
||
if (line.length < 2) line[1] = line[0]; // must have 2+
|
||
}
|
||
},
|
||
Polygon: function(o) {
|
||
for (var rings = o.coordinates, i = 0, n = rings.length; i < n; ++i) {
|
||
var ring = rings[i];
|
||
quantizeLine(ring);
|
||
while (ring.length < 4) ring.push(ring[0]); // must have 4+
|
||
}
|
||
},
|
||
MultiPolygon: function(o) {
|
||
for (var polygons = o.coordinates, i = 0, n = polygons.length; i < n; ++i) {
|
||
for (var rings = polygons[i], j = 0, m = rings.length; j < m; ++j) {
|
||
var ring = rings[j];
|
||
quantizeLine(ring);
|
||
while (ring.length < 4) ring.push(ring[0]); // must have 4+
|
||
}
|
||
}
|
||
}
|
||
};
|
||
|
||
for (var key in objects) {
|
||
quantizeGeometry(objects[key]);
|
||
}
|
||
|
||
return {
|
||
scale: [1 / kx, 1 / ky],
|
||
translate: [x0, y0]
|
||
};
|
||
};
|
||
|
||
// Constructs the TopoJSON Topology for the specified hash of features.
|
||
// Each object in the specified hash must be a GeoJSON object,
|
||
// meaning FeatureCollection, a Feature or a geometry object.
|
||
var topology = function(objects, quantization) {
|
||
var bbox = bounds(geometry(objects)),
|
||
transform = quantization > 0 && bbox && prequantize(objects, bbox, quantization),
|
||
topology = dedup(cut(extract(objects))),
|
||
coordinates = topology.coordinates,
|
||
indexByArc = hashmap(topology.arcs.length * 1.4, hashArc, equalArc);
|
||
|
||
objects = topology.objects; // for garbage collection
|
||
topology.bbox = bbox;
|
||
topology.arcs = topology.arcs.map(function(arc, i) {
|
||
indexByArc.set(arc, i);
|
||
return coordinates.slice(arc[0], arc[1] + 1);
|
||
});
|
||
|
||
delete topology.coordinates;
|
||
coordinates = null;
|
||
|
||
function indexGeometry(geometry$$1) {
|
||
if (geometry$$1 && indexGeometryType.hasOwnProperty(geometry$$1.type)) indexGeometryType[geometry$$1.type](geometry$$1);
|
||
}
|
||
|
||
var indexGeometryType = {
|
||
GeometryCollection: function(o) { o.geometries.forEach(indexGeometry); },
|
||
LineString: function(o) { o.arcs = indexArcs(o.arcs); },
|
||
MultiLineString: function(o) { o.arcs = o.arcs.map(indexArcs); },
|
||
Polygon: function(o) { o.arcs = o.arcs.map(indexArcs); },
|
||
MultiPolygon: function(o) { o.arcs = o.arcs.map(indexMultiArcs); }
|
||
};
|
||
|
||
function indexArcs(arc) {
|
||
var indexes = [];
|
||
do {
|
||
var index = indexByArc.get(arc);
|
||
indexes.push(arc[0] < arc[1] ? index : ~index);
|
||
} while (arc = arc.next);
|
||
return indexes;
|
||
}
|
||
|
||
function indexMultiArcs(arcs) {
|
||
return arcs.map(indexArcs);
|
||
}
|
||
|
||
for (var key in objects) {
|
||
indexGeometry(objects[key]);
|
||
}
|
||
|
||
if (transform) {
|
||
topology.transform = transform;
|
||
delta(topology);
|
||
}
|
||
|
||
return topology;
|
||
};
|
||
|
||
function hashArc(arc) {
|
||
var i = arc[0], j = arc[1], t;
|
||
if (j < i) t = i, i = j, j = t;
|
||
return i + 31 * j;
|
||
}
|
||
|
||
function equalArc(arcA, arcB) {
|
||
var ia = arcA[0], ja = arcA[1],
|
||
ib = arcB[0], jb = arcB[1], t;
|
||
if (ja < ia) t = ia, ia = ja, ja = t;
|
||
if (jb < ib) t = ib, ib = jb, jb = t;
|
||
return ia === ib && ja === jb;
|
||
}
|
||
|
||
var prune = function(topology) {
|
||
var oldArcs = topology.arcs,
|
||
newArcs = topology.arcs = [],
|
||
newArcIndex = -1,
|
||
newIndexByOldIndex = new Array(oldArcs.length),
|
||
name;
|
||
|
||
function pruneGeometry(o) {
|
||
switch (o.type) {
|
||
case "GeometryCollection": o.geometries.forEach(pruneGeometry); break;
|
||
case "LineString": pruneArcs(o.arcs); break;
|
||
case "MultiLineString": o.arcs.forEach(pruneArcs); break;
|
||
case "Polygon": o.arcs.forEach(pruneArcs); break;
|
||
case "MultiPolygon": o.arcs.forEach(pruneMultiArcs); break;
|
||
}
|
||
}
|
||
|
||
function pruneArcs(arcs) {
|
||
for (var i = 0, n = arcs.length; i < n; ++i) {
|
||
var oldIndex = arcs[i],
|
||
oldReverse = oldIndex < 0 && (oldIndex = ~oldIndex, true),
|
||
newIndex;
|
||
|
||
// If this is the first instance of this arc,
|
||
// record it under its new index.
|
||
if ((newIndex = newIndexByOldIndex[oldIndex]) == null) {
|
||
newIndexByOldIndex[oldIndex] = newIndex = ++newArcIndex;
|
||
newArcs[newIndex] = oldArcs[oldIndex];
|
||
}
|
||
|
||
arcs[i] = oldReverse ? ~newIndex : newIndex;
|
||
}
|
||
}
|
||
|
||
function pruneMultiArcs(arcs) {
|
||
arcs.forEach(pruneArcs);
|
||
}
|
||
|
||
for (name in topology.objects) {
|
||
pruneGeometry(topology.objects[name]);
|
||
}
|
||
|
||
return topology;
|
||
};
|
||
|
||
var filter = function(topology, filter) {
|
||
var name;
|
||
|
||
if (filter == null) filter = filterTrue;
|
||
|
||
function filterGeometry(o) {
|
||
switch (o.type) {
|
||
case "Polygon": {
|
||
o.arcs = filterRings(o.arcs);
|
||
if (!o.arcs) o.type = null, delete o.arcs;
|
||
break;
|
||
}
|
||
case "MultiPolygon": {
|
||
o.arcs = o.arcs.map(filterRings).filter(filterIdentity);
|
||
if (!o.arcs.length) o.type = null, delete o.arcs;
|
||
break;
|
||
}
|
||
case "GeometryCollection": {
|
||
o.geometries.forEach(filterGeometry);
|
||
o.geometries = o.geometries.filter(filterNotNull);
|
||
if (!o.geometries.length) o.type = null, delete o.geometries;
|
||
break;
|
||
}
|
||
}
|
||
}
|
||
|
||
function filterRings(arcs) {
|
||
return arcs.length && filterExteriorRing(arcs[0]) // if the exterior is small, ignore any holes
|
||
? [arcs.shift()].concat(arcs.filter(filterInteriorRing))
|
||
: null;
|
||
}
|
||
|
||
function filterExteriorRing(ring) {
|
||
return filter(ring, false);
|
||
}
|
||
|
||
function filterInteriorRing(ring) {
|
||
return filter(ring, true);
|
||
}
|
||
|
||
for (name in topology.objects) {
|
||
filterGeometry(topology.objects[name]);
|
||
}
|
||
|
||
return prune(topology);
|
||
};
|
||
|
||
function filterTrue() {
|
||
return true;
|
||
}
|
||
|
||
function filterIdentity(x) {
|
||
return x;
|
||
}
|
||
|
||
function filterNotNull(geometry) {
|
||
return geometry.type != null;
|
||
}
|
||
|
||
var filterAttached = function(topology) {
|
||
var uniqueRingByArc = {}, // arc index -> index of unique associated ring, or -1 if used by multiple rings
|
||
ringIndex = 0,
|
||
name;
|
||
|
||
function testGeometry(o) {
|
||
switch (o.type) {
|
||
case "GeometryCollection": o.geometries.forEach(testGeometry); break;
|
||
case "Polygon": testArcs(o.arcs); break;
|
||
case "MultiPolygon": o.arcs.forEach(testArcs); break;
|
||
}
|
||
}
|
||
|
||
function testArcs(arcs) {
|
||
for (var i = 0, n = arcs.length; i < n; ++i, ++ringIndex) {
|
||
for (var ring = arcs[i], j = 0, m = ring.length; j < m; ++j) {
|
||
var arc = ring[j];
|
||
if (arc < 0) arc = ~arc;
|
||
var uniqueRing = uniqueRingByArc[arc];
|
||
if (uniqueRing >= 0 && uniqueRing !== ringIndex) uniqueRingByArc[arc] = -1;
|
||
else uniqueRingByArc[arc] = ringIndex;
|
||
}
|
||
}
|
||
}
|
||
|
||
for (name in topology.objects) {
|
||
testGeometry(topology.objects[name]);
|
||
}
|
||
|
||
return function(ring) {
|
||
for (var j = 0, m = ring.length, arc; j < m; ++j) {
|
||
if (arc = ring[j], uniqueRingByArc[arc < 0 ? ~arc : arc] < 0) {
|
||
return true;
|
||
}
|
||
}
|
||
return false;
|
||
};
|
||
};
|
||
|
||
var identity = function(x) {
|
||
return x;
|
||
};
|
||
|
||
var transform = function(topology) {
|
||
if ((transform = topology.transform) == null) return identity;
|
||
var transform,
|
||
x0,
|
||
y0,
|
||
kx = transform.scale[0],
|
||
ky = transform.scale[1],
|
||
dx = transform.translate[0],
|
||
dy = transform.translate[1];
|
||
return function(point, i) {
|
||
if (!i) x0 = y0 = 0;
|
||
point[0] = (x0 += point[0]) * kx + dx;
|
||
point[1] = (y0 += point[1]) * ky + dy;
|
||
return point;
|
||
};
|
||
};
|
||
|
||
var bbox = function(topology) {
|
||
var bbox = topology.bbox;
|
||
|
||
function bboxPoint(p0) {
|
||
p1[0] = p0[0], p1[1] = p0[1], t(p1);
|
||
if (p1[0] < x0) x0 = p1[0];
|
||
if (p1[0] > x1) x1 = p1[0];
|
||
if (p1[1] < y0) y0 = p1[1];
|
||
if (p1[1] > y1) y1 = p1[1];
|
||
}
|
||
|
||
function bboxGeometry(o) {
|
||
switch (o.type) {
|
||
case "GeometryCollection": o.geometries.forEach(bboxGeometry); break;
|
||
case "Point": bboxPoint(o.coordinates); break;
|
||
case "MultiPoint": o.coordinates.forEach(bboxPoint); break;
|
||
}
|
||
}
|
||
|
||
if (!bbox) {
|
||
var t = transform(topology), p0, p1 = new Array(2), name,
|
||
x0 = Infinity, y0 = x0, x1 = -x0, y1 = -x0;
|
||
|
||
topology.arcs.forEach(function(arc) {
|
||
var i = -1, n = arc.length;
|
||
while (++i < n) {
|
||
p0 = arc[i], p1[0] = p0[0], p1[1] = p0[1], t(p1, i);
|
||
if (p1[0] < x0) x0 = p1[0];
|
||
if (p1[0] > x1) x1 = p1[0];
|
||
if (p1[1] < y0) y0 = p1[1];
|
||
if (p1[1] > y1) y1 = p1[1];
|
||
}
|
||
});
|
||
|
||
for (name in topology.objects) {
|
||
bboxGeometry(topology.objects[name]);
|
||
}
|
||
|
||
bbox = topology.bbox = [x0, y0, x1, y1];
|
||
}
|
||
|
||
return bbox;
|
||
};
|
||
|
||
var reverse$1 = function(array, n) {
|
||
var t, j = array.length, i = j - n;
|
||
while (i < --j) t = array[i], array[i++] = array[j], array[j] = t;
|
||
};
|
||
|
||
var feature = function(topology, o) {
|
||
return o.type === "GeometryCollection"
|
||
? {type: "FeatureCollection", features: o.geometries.map(function(o) { return feature$1(topology, o); })}
|
||
: feature$1(topology, o);
|
||
};
|
||
|
||
function feature$1(topology, o) {
|
||
var id = o.id,
|
||
bbox = o.bbox,
|
||
properties = o.properties == null ? {} : o.properties,
|
||
geometry = object(topology, o);
|
||
return id == null && bbox == null ? {type: "Feature", properties: properties, geometry: geometry}
|
||
: bbox == null ? {type: "Feature", id: id, properties: properties, geometry: geometry}
|
||
: {type: "Feature", id: id, bbox: bbox, properties: properties, geometry: geometry};
|
||
}
|
||
|
||
function object(topology, o) {
|
||
var transformPoint = transform(topology),
|
||
arcs = topology.arcs;
|
||
|
||
function arc(i, points) {
|
||
if (points.length) points.pop();
|
||
for (var a = arcs[i < 0 ? ~i : i], k = 0, n = a.length; k < n; ++k) {
|
||
points.push(transformPoint(a[k].slice(), k));
|
||
}
|
||
if (i < 0) reverse$1(points, n);
|
||
}
|
||
|
||
function point(p) {
|
||
return transformPoint(p.slice());
|
||
}
|
||
|
||
function line(arcs) {
|
||
var points = [];
|
||
for (var i = 0, n = arcs.length; i < n; ++i) arc(arcs[i], points);
|
||
if (points.length < 2) points.push(points[0].slice());
|
||
return points;
|
||
}
|
||
|
||
function ring(arcs) {
|
||
var points = line(arcs);
|
||
while (points.length < 4) points.push(points[0].slice());
|
||
return points;
|
||
}
|
||
|
||
function polygon(arcs) {
|
||
return arcs.map(ring);
|
||
}
|
||
|
||
function geometry(o) {
|
||
var type = o.type, coordinates;
|
||
switch (type) {
|
||
case "GeometryCollection": return {type: type, geometries: o.geometries.map(geometry)};
|
||
case "Point": coordinates = point(o.coordinates); break;
|
||
case "MultiPoint": coordinates = o.coordinates.map(point); break;
|
||
case "LineString": coordinates = line(o.arcs); break;
|
||
case "MultiLineString": coordinates = o.arcs.map(line); break;
|
||
case "Polygon": coordinates = polygon(o.arcs); break;
|
||
case "MultiPolygon": coordinates = o.arcs.map(polygon); break;
|
||
default: return null;
|
||
}
|
||
return {type: type, coordinates: coordinates};
|
||
}
|
||
|
||
return geometry(o);
|
||
}
|
||
|
||
var stitch = function(topology, arcs) {
|
||
var stitchedArcs = {},
|
||
fragmentByStart = {},
|
||
fragmentByEnd = {},
|
||
fragments = [],
|
||
emptyIndex = -1;
|
||
|
||
// Stitch empty arcs first, since they may be subsumed by other arcs.
|
||
arcs.forEach(function(i, j) {
|
||
var arc = topology.arcs[i < 0 ? ~i : i], t;
|
||
if (arc.length < 3 && !arc[1][0] && !arc[1][1]) {
|
||
t = arcs[++emptyIndex], arcs[emptyIndex] = i, arcs[j] = t;
|
||
}
|
||
});
|
||
|
||
arcs.forEach(function(i) {
|
||
var e = ends(i),
|
||
start = e[0],
|
||
end = e[1],
|
||
f, g;
|
||
|
||
if (f = fragmentByEnd[start]) {
|
||
delete fragmentByEnd[f.end];
|
||
f.push(i);
|
||
f.end = end;
|
||
if (g = fragmentByStart[end]) {
|
||
delete fragmentByStart[g.start];
|
||
var fg = g === f ? f : f.concat(g);
|
||
fragmentByStart[fg.start = f.start] = fragmentByEnd[fg.end = g.end] = fg;
|
||
} else {
|
||
fragmentByStart[f.start] = fragmentByEnd[f.end] = f;
|
||
}
|
||
} else if (f = fragmentByStart[end]) {
|
||
delete fragmentByStart[f.start];
|
||
f.unshift(i);
|
||
f.start = start;
|
||
if (g = fragmentByEnd[start]) {
|
||
delete fragmentByEnd[g.end];
|
||
var gf = g === f ? f : g.concat(f);
|
||
fragmentByStart[gf.start = g.start] = fragmentByEnd[gf.end = f.end] = gf;
|
||
} else {
|
||
fragmentByStart[f.start] = fragmentByEnd[f.end] = f;
|
||
}
|
||
} else {
|
||
f = [i];
|
||
fragmentByStart[f.start = start] = fragmentByEnd[f.end = end] = f;
|
||
}
|
||
});
|
||
|
||
function ends(i) {
|
||
var arc = topology.arcs[i < 0 ? ~i : i], p0 = arc[0], p1;
|
||
if (topology.transform) p1 = [0, 0], arc.forEach(function(dp) { p1[0] += dp[0], p1[1] += dp[1]; });
|
||
else p1 = arc[arc.length - 1];
|
||
return i < 0 ? [p1, p0] : [p0, p1];
|
||
}
|
||
|
||
function flush(fragmentByEnd, fragmentByStart) {
|
||
for (var k in fragmentByEnd) {
|
||
var f = fragmentByEnd[k];
|
||
delete fragmentByStart[f.start];
|
||
delete f.start;
|
||
delete f.end;
|
||
f.forEach(function(i) { stitchedArcs[i < 0 ? ~i : i] = 1; });
|
||
fragments.push(f);
|
||
}
|
||
}
|
||
|
||
flush(fragmentByEnd, fragmentByStart);
|
||
flush(fragmentByStart, fragmentByEnd);
|
||
arcs.forEach(function(i) { if (!stitchedArcs[i < 0 ? ~i : i]) fragments.push([i]); });
|
||
|
||
return fragments;
|
||
};
|
||
|
||
var mesh = function(topology) {
|
||
return object(topology, meshArcs.apply(this, arguments));
|
||
};
|
||
|
||
function meshArcs(topology, object$$1, filter) {
|
||
var arcs, i, n;
|
||
if (arguments.length > 1) arcs = extractArcs(topology, object$$1, filter);
|
||
else for (i = 0, arcs = new Array(n = topology.arcs.length); i < n; ++i) arcs[i] = i;
|
||
return {type: "MultiLineString", arcs: stitch(topology, arcs)};
|
||
}
|
||
|
||
function extractArcs(topology, object$$1, filter) {
|
||
var arcs = [],
|
||
geomsByArc = [],
|
||
geom;
|
||
|
||
function extract0(i) {
|
||
var j = i < 0 ? ~i : i;
|
||
(geomsByArc[j] || (geomsByArc[j] = [])).push({i: i, g: geom});
|
||
}
|
||
|
||
function extract1(arcs) {
|
||
arcs.forEach(extract0);
|
||
}
|
||
|
||
function extract2(arcs) {
|
||
arcs.forEach(extract1);
|
||
}
|
||
|
||
function extract3(arcs) {
|
||
arcs.forEach(extract2);
|
||
}
|
||
|
||
function geometry(o) {
|
||
switch (geom = o, o.type) {
|
||
case "GeometryCollection": o.geometries.forEach(geometry); break;
|
||
case "LineString": extract1(o.arcs); break;
|
||
case "MultiLineString": case "Polygon": extract2(o.arcs); break;
|
||
case "MultiPolygon": extract3(o.arcs); break;
|
||
}
|
||
}
|
||
|
||
geometry(object$$1);
|
||
|
||
geomsByArc.forEach(filter == null
|
||
? function(geoms) { arcs.push(geoms[0].i); }
|
||
: function(geoms) { if (filter(geoms[0].g, geoms[geoms.length - 1].g)) arcs.push(geoms[0].i); });
|
||
|
||
return arcs;
|
||
}
|
||
|
||
function planarRingArea(ring) {
|
||
var i = -1, n = ring.length, a, b = ring[n - 1], area = 0;
|
||
while (++i < n) a = b, b = ring[i], area += a[0] * b[1] - a[1] * b[0];
|
||
return Math.abs(area); // Note: doubled area!
|
||
}
|
||
|
||
var merge = function(topology) {
|
||
return object(topology, mergeArcs.apply(this, arguments));
|
||
};
|
||
|
||
function mergeArcs(topology, objects) {
|
||
var polygonsByArc = {},
|
||
polygons = [],
|
||
groups = [];
|
||
|
||
objects.forEach(geometry);
|
||
|
||
function geometry(o) {
|
||
switch (o.type) {
|
||
case "GeometryCollection": o.geometries.forEach(geometry); break;
|
||
case "Polygon": extract(o.arcs); break;
|
||
case "MultiPolygon": o.arcs.forEach(extract); break;
|
||
}
|
||
}
|
||
|
||
function extract(polygon) {
|
||
polygon.forEach(function(ring) {
|
||
ring.forEach(function(arc) {
|
||
(polygonsByArc[arc = arc < 0 ? ~arc : arc] || (polygonsByArc[arc] = [])).push(polygon);
|
||
});
|
||
});
|
||
polygons.push(polygon);
|
||
}
|
||
|
||
function area(ring) {
|
||
return planarRingArea(object(topology, {type: "Polygon", arcs: [ring]}).coordinates[0]);
|
||
}
|
||
|
||
polygons.forEach(function(polygon) {
|
||
if (!polygon._) {
|
||
var group = [],
|
||
neighbors = [polygon];
|
||
polygon._ = 1;
|
||
groups.push(group);
|
||
while (polygon = neighbors.pop()) {
|
||
group.push(polygon);
|
||
polygon.forEach(function(ring) {
|
||
ring.forEach(function(arc) {
|
||
polygonsByArc[arc < 0 ? ~arc : arc].forEach(function(polygon) {
|
||
if (!polygon._) {
|
||
polygon._ = 1;
|
||
neighbors.push(polygon);
|
||
}
|
||
});
|
||
});
|
||
});
|
||
}
|
||
}
|
||
});
|
||
|
||
polygons.forEach(function(polygon) {
|
||
delete polygon._;
|
||
});
|
||
|
||
return {
|
||
type: "MultiPolygon",
|
||
arcs: groups.map(function(polygons) {
|
||
var arcs = [], n;
|
||
|
||
// Extract the exterior (unique) arcs.
|
||
polygons.forEach(function(polygon) {
|
||
polygon.forEach(function(ring) {
|
||
ring.forEach(function(arc) {
|
||
if (polygonsByArc[arc < 0 ? ~arc : arc].length < 2) {
|
||
arcs.push(arc);
|
||
}
|
||
});
|
||
});
|
||
});
|
||
|
||
// Stitch the arcs into one or more rings.
|
||
arcs = stitch(topology, arcs);
|
||
|
||
// If more than one ring is returned,
|
||
// at most one of these rings can be the exterior;
|
||
// choose the one with the greatest absolute area.
|
||
if ((n = arcs.length) > 1) {
|
||
for (var i = 1, k = area(arcs[0]), ki, t; i < n; ++i) {
|
||
if ((ki = area(arcs[i])) > k) {
|
||
t = arcs[0], arcs[0] = arcs[i], arcs[i] = t, k = ki;
|
||
}
|
||
}
|
||
}
|
||
|
||
return arcs;
|
||
})
|
||
};
|
||
}
|
||
|
||
var bisect = function(a, x) {
|
||
var lo = 0, hi = a.length;
|
||
while (lo < hi) {
|
||
var mid = lo + hi >>> 1;
|
||
if (a[mid] < x) lo = mid + 1;
|
||
else hi = mid;
|
||
}
|
||
return lo;
|
||
};
|
||
|
||
var neighbors = function(objects) {
|
||
var indexesByArc = {}, // arc index -> array of object indexes
|
||
neighbors = objects.map(function() { return []; });
|
||
|
||
function line(arcs, i) {
|
||
arcs.forEach(function(a) {
|
||
if (a < 0) a = ~a;
|
||
var o = indexesByArc[a];
|
||
if (o) o.push(i);
|
||
else indexesByArc[a] = [i];
|
||
});
|
||
}
|
||
|
||
function polygon(arcs, i) {
|
||
arcs.forEach(function(arc) { line(arc, i); });
|
||
}
|
||
|
||
function geometry(o, i) {
|
||
if (o.type === "GeometryCollection") o.geometries.forEach(function(o) { geometry(o, i); });
|
||
else if (o.type in geometryType) geometryType[o.type](o.arcs, i);
|
||
}
|
||
|
||
var geometryType = {
|
||
LineString: line,
|
||
MultiLineString: polygon,
|
||
Polygon: polygon,
|
||
MultiPolygon: function(arcs, i) { arcs.forEach(function(arc) { polygon(arc, i); }); }
|
||
};
|
||
|
||
objects.forEach(geometry);
|
||
|
||
for (var i in indexesByArc) {
|
||
for (var indexes = indexesByArc[i], m = indexes.length, j = 0; j < m; ++j) {
|
||
for (var k = j + 1; k < m; ++k) {
|
||
var ij = indexes[j], ik = indexes[k], n;
|
||
if ((n = neighbors[ij])[i = bisect(n, ik)] !== ik) n.splice(i, 0, ik);
|
||
if ((n = neighbors[ik])[i = bisect(n, ij)] !== ij) n.splice(i, 0, ij);
|
||
}
|
||
}
|
||
}
|
||
|
||
return neighbors;
|
||
};
|
||
|
||
var quantize = function(topology, n) {
|
||
if (!((n = Math.floor(n)) >= 2)) throw new Error("n must be \u22652");
|
||
if (topology.transform) throw new Error("already quantized");
|
||
var bb = bbox(topology), name,
|
||
dx = bb[0], kx = (bb[2] - dx) / (n - 1) || 1,
|
||
dy = bb[1], ky = (bb[3] - dy) / (n - 1) || 1;
|
||
|
||
function quantizePoint(p) {
|
||
p[0] = Math.round((p[0] - dx) / kx);
|
||
p[1] = Math.round((p[1] - dy) / ky);
|
||
}
|
||
|
||
function quantizeGeometry(o) {
|
||
switch (o.type) {
|
||
case "GeometryCollection": o.geometries.forEach(quantizeGeometry); break;
|
||
case "Point": quantizePoint(o.coordinates); break;
|
||
case "MultiPoint": o.coordinates.forEach(quantizePoint); break;
|
||
}
|
||
}
|
||
|
||
topology.arcs.forEach(function(arc) {
|
||
var i = 1,
|
||
j = 1,
|
||
n = arc.length,
|
||
pi = arc[0],
|
||
x0 = pi[0] = Math.round((pi[0] - dx) / kx),
|
||
y0 = pi[1] = Math.round((pi[1] - dy) / ky),
|
||
pj,
|
||
x1,
|
||
y1;
|
||
|
||
for (; i < n; ++i) {
|
||
pi = arc[i];
|
||
x1 = Math.round((pi[0] - dx) / kx);
|
||
y1 = Math.round((pi[1] - dy) / ky);
|
||
if (x1 !== x0 || y1 !== y0) {
|
||
pj = arc[j++];
|
||
pj[0] = x1 - x0, x0 = x1;
|
||
pj[1] = y1 - y0, y0 = y1;
|
||
}
|
||
}
|
||
|
||
if (j < 2) {
|
||
pj = arc[j++];
|
||
pj[0] = 0;
|
||
pj[1] = 0;
|
||
}
|
||
|
||
arc.length = j;
|
||
});
|
||
|
||
for (name in topology.objects) {
|
||
quantizeGeometry(topology.objects[name]);
|
||
}
|
||
|
||
topology.transform = {
|
||
scale: [kx, ky],
|
||
translate: [dx, dy]
|
||
};
|
||
|
||
return topology;
|
||
};
|
||
|
||
var untransform = function(topology) {
|
||
if ((transform = topology.transform) == null) return identity;
|
||
var transform,
|
||
x0,
|
||
y0,
|
||
kx = transform.scale[0],
|
||
ky = transform.scale[1],
|
||
dx = transform.translate[0],
|
||
dy = transform.translate[1];
|
||
return function(point, i) {
|
||
if (!i) x0 = y0 = 0;
|
||
var x1 = Math.round((point[0] - dx) / kx),
|
||
y1 = Math.round((point[1] - dy) / ky);
|
||
point[0] = x1 - x0, x0 = x1;
|
||
point[1] = y1 - y0, y0 = y1;
|
||
return point;
|
||
};
|
||
};
|
||
|
||
function planarTriangleArea(triangle) {
|
||
var a = triangle[0], b = triangle[1], c = triangle[2];
|
||
return Math.abs((a[0] - c[0]) * (b[1] - a[1]) - (a[0] - b[0]) * (c[1] - a[1]));
|
||
}
|
||
|
||
function planarRingArea$1(ring) {
|
||
var i = -1, n = ring.length, a, b = ring[n - 1], area = 0;
|
||
while (++i < n) a = b, b = ring[i], area += a[0] * b[1] - a[1] * b[0];
|
||
return Math.abs(area) / 2;
|
||
}
|
||
|
||
var filterWeight = function(topology, minWeight, weight) {
|
||
minWeight = minWeight == null ? Number.MIN_VALUE : +minWeight;
|
||
|
||
if (weight == null) weight = planarRingArea$1;
|
||
|
||
return function(ring, interior) {
|
||
return weight(feature(topology, {type: "Polygon", arcs: [ring]}).geometry.coordinates[0], interior) >= minWeight;
|
||
};
|
||
};
|
||
|
||
function compare(a, b) {
|
||
return a[1][2] - b[1][2];
|
||
}
|
||
|
||
var newHeap = function() {
|
||
var heap = {},
|
||
array = [],
|
||
size = 0;
|
||
|
||
heap.push = function(object) {
|
||
up(array[object._ = size] = object, size++);
|
||
return size;
|
||
};
|
||
|
||
heap.pop = function() {
|
||
if (size <= 0) return;
|
||
var removed = array[0], object;
|
||
if (--size > 0) object = array[size], down(array[object._ = 0] = object, 0);
|
||
return removed;
|
||
};
|
||
|
||
heap.remove = function(removed) {
|
||
var i = removed._, object;
|
||
if (array[i] !== removed) return; // invalid request
|
||
if (i !== --size) object = array[size], (compare(object, removed) < 0 ? up : down)(array[object._ = i] = object, i);
|
||
return i;
|
||
};
|
||
|
||
function up(object, i) {
|
||
while (i > 0) {
|
||
var j = ((i + 1) >> 1) - 1,
|
||
parent = array[j];
|
||
if (compare(object, parent) >= 0) break;
|
||
array[parent._ = i] = parent;
|
||
array[object._ = i = j] = object;
|
||
}
|
||
}
|
||
|
||
function down(object, i) {
|
||
while (true) {
|
||
var r = (i + 1) << 1,
|
||
l = r - 1,
|
||
j = i,
|
||
child = array[j];
|
||
if (l < size && compare(array[l], child) < 0) child = array[j = l];
|
||
if (r < size && compare(array[r], child) < 0) child = array[j = r];
|
||
if (j === i) break;
|
||
array[child._ = i] = child;
|
||
array[object._ = i = j] = object;
|
||
}
|
||
}
|
||
|
||
return heap;
|
||
};
|
||
|
||
var presimplify = function(topology, weight) {
|
||
var absolute = transform(topology),
|
||
relative = untransform(topology),
|
||
heap = newHeap();
|
||
|
||
if (weight == null) weight = planarTriangleArea;
|
||
|
||
topology.arcs.forEach(function(arc) {
|
||
var triangles = [],
|
||
maxWeight = 0,
|
||
triangle,
|
||
i,
|
||
n;
|
||
|
||
arc.forEach(absolute);
|
||
|
||
for (i = 1, n = arc.length - 1; i < n; ++i) {
|
||
triangle = arc.slice(i - 1, i + 2);
|
||
triangle[1][2] = weight(triangle);
|
||
triangles.push(triangle);
|
||
heap.push(triangle);
|
||
}
|
||
|
||
// Always keep the arc endpoints!
|
||
arc[0][2] = arc[n][2] = Infinity;
|
||
|
||
for (i = 0, n = triangles.length; i < n; ++i) {
|
||
triangle = triangles[i];
|
||
triangle.previous = triangles[i - 1];
|
||
triangle.next = triangles[i + 1];
|
||
}
|
||
|
||
while (triangle = heap.pop()) {
|
||
var previous = triangle.previous,
|
||
next = triangle.next;
|
||
|
||
// If the weight of the current point is less than that of the previous
|
||
// point to be eliminated, use the latter’s weight instead. This ensures
|
||
// that the current point cannot be eliminated without eliminating
|
||
// previously- eliminated points.
|
||
if (triangle[1][2] < maxWeight) triangle[1][2] = maxWeight;
|
||
else maxWeight = triangle[1][2];
|
||
|
||
if (previous) {
|
||
previous.next = next;
|
||
previous[2] = triangle[2];
|
||
update(previous);
|
||
}
|
||
|
||
if (next) {
|
||
next.previous = previous;
|
||
next[0] = triangle[0];
|
||
update(next);
|
||
}
|
||
}
|
||
|
||
arc.forEach(relative);
|
||
});
|
||
|
||
function update(triangle) {
|
||
heap.remove(triangle);
|
||
triangle[1][2] = weight(triangle);
|
||
heap.push(triangle);
|
||
}
|
||
|
||
return topology;
|
||
};
|
||
|
||
var quantile = function(topology, p) {
|
||
var array = [];
|
||
|
||
topology.arcs.forEach(function(arc) {
|
||
arc.forEach(function(point) {
|
||
if (isFinite(point[2])) { // Ignore endpoints, whose weight is Infinity.
|
||
array.push(point[2]);
|
||
}
|
||
});
|
||
});
|
||
|
||
return array.length && quantile$1(array.sort(descending), p);
|
||
};
|
||
|
||
function quantile$1(array, p) {
|
||
if (!(n = array.length)) return;
|
||
if ((p = +p) <= 0 || n < 2) return array[0];
|
||
if (p >= 1) return array[n - 1];
|
||
var n,
|
||
h = (n - 1) * p,
|
||
i = Math.floor(h),
|
||
a = array[i],
|
||
b = array[i + 1];
|
||
return a + (b - a) * (h - i);
|
||
}
|
||
|
||
function descending(a, b) {
|
||
return b - a;
|
||
}
|
||
|
||
var simplify = function(topology, minWeight) {
|
||
minWeight = minWeight == null ? Number.MIN_VALUE : +minWeight;
|
||
|
||
// Remove points whose weight is less than the minimum weight.
|
||
topology.arcs.forEach(topology.transform ? function(arc) {
|
||
var dx = 0,
|
||
dy = 0, // accumulate removed points
|
||
i = -1,
|
||
j = -1,
|
||
n = arc.length,
|
||
source,
|
||
target;
|
||
|
||
while (++i < n) {
|
||
source = arc[i];
|
||
if (source[2] >= minWeight) {
|
||
target = arc[++j];
|
||
target[0] = source[0] + dx;
|
||
target[1] = source[1] + dy;
|
||
dx = dy = 0;
|
||
} else {
|
||
dx += source[0];
|
||
dy += source[1];
|
||
}
|
||
}
|
||
|
||
arc.length = ++j;
|
||
} : function(arc) {
|
||
var i = -1,
|
||
j = -1,
|
||
n = arc.length,
|
||
point;
|
||
|
||
while (++i < n) {
|
||
point = arc[i];
|
||
if (point[2] >= minWeight) {
|
||
arc[++j] = point;
|
||
}
|
||
}
|
||
|
||
arc.length = ++j;
|
||
});
|
||
|
||
// Remove the computed weight for each point, and remove coincident points.
|
||
// This is done as a separate pass because some coordinates may be shared
|
||
// between arcs (such as the last point and first point of a cut line).
|
||
// If the entire arc is empty, retain at least two points (per spec).
|
||
topology.arcs.forEach(topology.transform ? function(arc) {
|
||
var i = 0,
|
||
j = 0,
|
||
n = arc.length,
|
||
p = arc[0];
|
||
p.length = 2;
|
||
while (++i < n) {
|
||
p = arc[i];
|
||
p.length = 2;
|
||
if (p[0] || p[1]) arc[++j] = p;
|
||
}
|
||
arc.length = (j || 1) + 1;
|
||
} : function(arc) {
|
||
var i = 0,
|
||
j = 0,
|
||
n = arc.length,
|
||
p = arc[0],
|
||
x0 = p[0],
|
||
y0 = p[1],
|
||
x1,
|
||
y1;
|
||
p.length = 2;
|
||
while (++i < n) {
|
||
p = arc[i], x1 = p[0], y1 = p[1];
|
||
p.length = 2;
|
||
if (x0 !== x1 || y0 !== y1) arc[++j] = p, x0 = x1, y0 = y1;
|
||
}
|
||
arc.length = (j || 1) + 1;
|
||
});
|
||
|
||
return topology;
|
||
};
|
||
|
||
var pi = Math.PI;
|
||
var tau = 2 * pi;
|
||
var fourPi = 4 * pi;
|
||
var radians = pi / 180;
|
||
var abs = Math.abs;
|
||
var atan = Math.atan;
|
||
var atan2 = Math.atan2;
|
||
var cos = Math.cos;
|
||
var max = Math.max;
|
||
var sin = Math.sin;
|
||
var sqrt = Math.sqrt;
|
||
var tan = Math.tan;
|
||
|
||
function sphericalRingArea(ring, interior) {
|
||
if (!ring.length) return 0;
|
||
var sum = 0,
|
||
point = ring[0],
|
||
lambda0, lambda1 = point[0] * radians, delta,
|
||
phi1 = (point[1] * radians + tau) / 2,
|
||
cosPhi0, cosPhi1 = cos(phi1),
|
||
sinPhi0, sinPhi1 = sin(phi1),
|
||
i, n, k;
|
||
|
||
for (i = 1, n = ring.length; i < n; ++i) {
|
||
point = ring[i];
|
||
lambda0 = lambda1, lambda1 = point[0] * radians, delta = lambda1 - lambda0;
|
||
phi1 = (point[1] * radians + tau) / 2;
|
||
cosPhi0 = cosPhi1, cosPhi1 = cos(phi1);
|
||
sinPhi0 = sinPhi1, sinPhi1 = sin(phi1);
|
||
|
||
// Spherical excess E for a spherical triangle with vertices: south pole,
|
||
// previous point, current point. Uses a formula derived from Cagnoli’s
|
||
// theorem. See Todhunter, Spherical Trig. (1871), Sec. 103, Eq. (2).
|
||
k = sinPhi0 * sinPhi1;
|
||
sum += atan2(k * sin(delta), cosPhi0 * cosPhi1 + k * cos(delta));
|
||
}
|
||
|
||
sum = 2 * (sum > pi ? sum - tau : sum < -pi ? sum + tau : sum);
|
||
if (interior) sum *= -1;
|
||
return sum < 0 ? sum + fourPi : sum;
|
||
}
|
||
|
||
function sphericalTriangleArea(t) {
|
||
var lambda0 = t[0][0] * radians, phi0 = t[0][1] * radians, cosPhi0 = cos(phi0), sinPhi0 = sin(phi0),
|
||
lambda1 = t[1][0] * radians, phi1 = t[1][1] * radians, cosPhi1 = cos(phi1), sinPhi1 = sin(phi1),
|
||
lambda2 = t[2][0] * radians, phi2 = t[2][1] * radians, cosPhi2 = cos(phi2), sinPhi2 = sin(phi2),
|
||
a = distance(lambda0, cosPhi0, sinPhi0, lambda1, cosPhi1, sinPhi1),
|
||
b = distance(lambda1, cosPhi1, sinPhi1, lambda2, cosPhi2, sinPhi2),
|
||
c = distance(lambda2, cosPhi2, sinPhi2, lambda0, cosPhi0, sinPhi0),
|
||
s = (a + b + c) / 2;
|
||
return 4 * atan(sqrt(max(0, tan(s / 2) * tan((s - a) / 2) * tan((s - b) / 2) * tan((s - c) / 2))));
|
||
}
|
||
|
||
function distance(lambda0, sinPhi0, cosPhi0, lambda1, sinPhi1, cosPhi1) {
|
||
var delta = abs(lambda1 - lambda0),
|
||
cosDelta = cos(delta),
|
||
sinDelta = sin(delta),
|
||
x = cosPhi1 * sinDelta,
|
||
y = cosPhi0 * sinPhi1 - sinPhi0 * cosPhi1 * cosDelta,
|
||
z = sinPhi0 * sinPhi1 + cosPhi0 * cosPhi1 * cosDelta;
|
||
return atan2(sqrt(x * x + y * y), z);
|
||
}
|
||
|
||
exports.topology = topology;
|
||
exports.filter = filter;
|
||
exports.filterAttached = filterAttached;
|
||
exports.filterWeight = filterWeight;
|
||
exports.planarRingArea = planarRingArea$1;
|
||
exports.planarTriangleArea = planarTriangleArea;
|
||
exports.presimplify = presimplify;
|
||
exports.quantile = quantile;
|
||
exports.simplify = simplify;
|
||
exports.sphericalRingArea = sphericalRingArea;
|
||
exports.sphericalTriangleArea = sphericalTriangleArea;
|
||
exports.bbox = bbox;
|
||
exports.feature = feature;
|
||
exports.merge = merge;
|
||
exports.mergeArcs = mergeArcs;
|
||
exports.mesh = mesh;
|
||
exports.meshArcs = meshArcs;
|
||
exports.neighbors = neighbors;
|
||
exports.quantize = quantize;
|
||
exports.transform = transform;
|
||
exports.untransform = untransform;
|
||
|
||
Object.defineProperty(exports, '__esModule', { value: true });
|
||
|
||
})));
|