File name
Commit message
Commit date
File name
Commit message
Commit date
File name
Commit message
Commit date
File name
Commit message
Commit date
// https://github.com/topojson/topojson Version 3.0.2. Copyright 2017 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';
var identity = function(x) {
return x;
};
var transform = function(transform) {
if (transform == null) return identity;
var x0,
y0,
kx = transform.scale[0],
ky = transform.scale[1],
dx = transform.translate[0],
dy = transform.translate[1];
return function(input, i) {
if (!i) x0 = y0 = 0;
var j = 2, n = input.length, output = new Array(n);
output[0] = (x0 += input[0]) * kx + dx;
output[1] = (y0 += input[1]) * ky + dy;
while (j < n) output[j] = input[j], ++j;
return output;
};
};
var bbox = function(topology) {
var t = transform(topology.transform), key,
x0 = Infinity, y0 = x0, x1 = -x0, y1 = -x0;
function bboxPoint(p) {
p = t(p);
if (p[0] < x0) x0 = p[0];
if (p[0] > x1) x1 = p[0];
if (p[1] < y0) y0 = p[1];
if (p[1] > y1) y1 = p[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;
}
}
topology.arcs.forEach(function(arc) {
var i = -1, n = arc.length, p;
while (++i < n) {
p = t(arc[i], i);
if (p[0] < x0) x0 = p[0];
if (p[0] > x1) x1 = p[0];
if (p[1] < y0) y0 = p[1];
if (p[1] > y1) y1 = p[1];
}
});
for (key in topology.objects) {
bboxGeometry(topology.objects[key]);
}
return [x0, y0, x1, y1];
};
var reverse = 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.transform),
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], k));
}
if (i < 0) reverse(points, n);
}
function point(p) {
return transformPoint(p);
}
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]); // This should never happen per the specification.
return points;
}
function ring(arcs) {
var points = line(arcs);
while (points.length < 4) points.push(points[0]); // This may happen if an arc has only two points.
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 untransform = function(transform) {
if (transform == null) return identity;
var x0,
y0,
kx = transform.scale[0],
ky = transform.scale[1],
dx = transform.translate[0],
dy = transform.translate[1];
return function(input, i) {
if (!i) x0 = y0 = 0;
var j = 2,
n = input.length,
output = new Array(n),
x1 = Math.round((input[0] - dx) / kx),
y1 = Math.round((input[1] - dy) / ky);
output[0] = x1 - x0, x0 = x1;
output[1] = y1 - y0, y0 = y1;
while (j < n) output[j] = input[j], ++j;
return output;
};
};
var quantize = function(topology, transform) {
if (topology.transform) throw new Error("already quantized");
if (!transform || !transform.scale) {
if (!((n = Math.floor(transform)) >= 2)) throw new Error("n must be \u22652");
box = topology.bbox || bbox(topology);
var x0 = box[0], y0 = box[1], x1 = box[2], y1 = box[3], n;
transform = {scale: [x1 - x0 ? (x1 - x0) / (n - 1) : 1, y1 - y0 ? (y1 - y0) / (n - 1) : 1], translate: [x0, y0]};
} else {
box = topology.bbox;
}
var t = untransform(transform), box, key, inputs = topology.objects, outputs = {};
function quantizePoint(point) {
return t(point);
}
function quantizeGeometry(input) {
var output;
switch (input.type) {
case "GeometryCollection": output = {type: "GeometryCollection", geometries: input.geometries.map(quantizeGeometry)}; break;
case "Point": output = {type: "Point", coordinates: quantizePoint(input.coordinates)}; break;
case "MultiPoint": output = {type: "MultiPoint", coordinates: input.coordinates.map(quantizePoint)}; break;
default: return input;
}
if (input.id != null) output.id = input.id;
if (input.bbox != null) output.bbox = input.bbox;
if (input.properties != null) output.properties = input.properties;
return output;
}
function quantizeArc(input) {
var i = 0, j = 1, n = input.length, p, output = new Array(n); // pessimistic
output[0] = t(input[0], 0);
while (++i < n) if ((p = t(input[i], i))[0] || p[1]) output[j++] = p; // non-coincident points
if (j === 1) output[j++] = [0, 0]; // an arc must have at least two points
output.length = j;
return output;
}
for (key in inputs) outputs[key] = quantizeGeometry(inputs[key]);
return {
type: "Topology",
bbox: box,
transform: transform,
objects: outputs,
arcs: topology.arcs.map(quantizeArc)
};
};
// 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 != null && 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.arcs); },
MultiLineString: function(o) { o.arcs.forEach(boundLine); },
Polygon: function(o) { o.arcs.forEach(boundLine); },
MultiPolygon: function(o) { o.arcs.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 uints = new Uint32Array(buffer);
var hashPoint = function(point) {
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$1(array, start, end);
reverse$1(array, start, start + offset);
reverse$1(array, start + offset, end);
}
function reverse$1(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 an array of arcs in absolute (but already quantized!) coordinates,
// converts to fixed-point delta encoding.
// This is a destructive operation that modifies the given arcs!
var delta = function(arcs) {
var i = -1,
n = arcs.length;
while (++i < n) {
var arc = arcs[i],
j = 0,
k = 1,
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];
if (x1 !== x0 || y1 !== y0) arc[k++] = [x1 - x0, y1 - y0], x0 = x1, y0 = y1;
}
if (k === 1) arc[k++] = [0, 0]; // Each arc must be an array of two or more positions.
arc.length = k;
}
return arcs;
};
// 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.arcs); },
MultiLineString: function(o) { o.arcs = o.arcs.map(extractLine); },
Polygon: function(o) { o.arcs = o.arcs.map(extractRing); },
MultiPolygon: function(o) { o.arcs = o.arcs.map(extractMultiRing); }
};
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, returns a hash of GeoJSON geometry objects.
// Any null input geometry objects are represented as {type: null} in the output.
// Any feature.{id,properties,bbox} are transferred to the output geometry object.
// Each output geometry object is a shallow copy of the input (e.g., properties, coordinates)!
var geometry = function(inputs) {
var outputs = {}, key;
for (key in inputs) outputs[key] = geomifyObject(inputs[key]);
return outputs;
};
function geomifyObject(input) {
return input == null ? {type: null}
: (input.type === "FeatureCollection" ? geomifyFeatureCollection
: input.type === "Feature" ? geomifyFeature
: geomifyGeometry)(input);
}
function geomifyFeatureCollection(input) {
var output = {type: "GeometryCollection", geometries: input.features.map(geomifyFeature)};
if (input.bbox != null) output.bbox = input.bbox;
return output;
}
function geomifyFeature(input) {
var output = geomifyGeometry(input.geometry), key; // eslint-disable-line no-unused-vars
if (input.id != null) output.id = input.id;
if (input.bbox != null) output.bbox = input.bbox;
for (key in input.properties) { output.properties = input.properties; break; }
return output;
}
function geomifyGeometry(input) {
if (input == null) return {type: null};
var output = input.type === "GeometryCollection" ? {type: "GeometryCollection", geometries: input.geometries.map(geomifyGeometry)}
: input.type === "Point" || input.type === "MultiPoint" ? {type: input.type, coordinates: input.coordinates}
: {type: input.type, arcs: input.coordinates}; // TODO Check for unknown types?
if (input.bbox != null) output.bbox = input.bbox;
return output;
}
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(input) {
return [Math.round((input[0] - x0) * kx), Math.round((input[1] - y0) * ky)];
}
function quantizePoints(input, m) {
var i = -1,
j = 0,
n = input.length,
output = new Array(n), // pessimistic
pi,
px,
py,
x,
y;
while (++i < n) {
pi = input[i];
x = Math.round((pi[0] - x0) * kx);
y = Math.round((pi[1] - y0) * ky);
if (x !== px || y !== py) output[j++] = [px = x, py = y]; // non-coincident points
}
output.length = j;
while (j < m) j = output.push([output[0][0], output[0][1]]);
return output;
}
function quantizeLine(input) {
return quantizePoints(input, 2);
}
function quantizeRing(input) {
return quantizePoints(input, 4);
}
function quantizePolygon(input) {
return input.map(quantizeRing);
}
function quantizeGeometry(o) {
if (o != null && quantizeGeometryType.hasOwnProperty(o.type)) quantizeGeometryType[o.type](o);
}
var quantizeGeometryType = {
GeometryCollection: function(o) { o.geometries.forEach(quantizeGeometry); },
Point: function(o) { o.coordinates = quantizePoint(o.coordinates); },
MultiPoint: function(o) { o.coordinates = o.coordinates.map(quantizePoint); },
LineString: function(o) { o.arcs = quantizeLine(o.arcs); },
MultiLineString: function(o) { o.arcs = o.arcs.map(quantizeLine); },
Polygon: function(o) { o.arcs = quantizePolygon(o.arcs); },
MultiPolygon: function(o) { o.arcs = o.arcs.map(quantizePolygon); }
};
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(objects = 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;
topology.arcs = delta(topology.arcs);
}
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 oldObjects = topology.objects,
newObjects = {},
oldArcs = topology.arcs,
oldArcsLength = oldArcs.length,
oldIndex = -1,
newIndexByOldIndex = new Array(oldArcsLength),
newArcsLength = 0,
newArcs,
newIndex = -1,
key;
function scanGeometry(input) {
switch (input.type) {
case "GeometryCollection": input.geometries.forEach(scanGeometry); break;
case "LineString": scanArcs(input.arcs); break;
case "MultiLineString": input.arcs.forEach(scanArcs); break;
case "Polygon": input.arcs.forEach(scanArcs); break;
case "MultiPolygon": input.arcs.forEach(scanMultiArcs); break;
}
}
function scanArc(index) {
if (index < 0) index = ~index;
if (!newIndexByOldIndex[index]) newIndexByOldIndex[index] = 1, ++newArcsLength;
}
function scanArcs(arcs) {
arcs.forEach(scanArc);
}
function scanMultiArcs(arcs) {
arcs.forEach(scanArcs);
}
function reindexGeometry(input) {
var output;
switch (input.type) {
case "GeometryCollection": output = {type: "GeometryCollection", geometries: input.geometries.map(reindexGeometry)}; break;
case "LineString": output = {type: "LineString", arcs: reindexArcs(input.arcs)}; break;
case "MultiLineString": output = {type: "MultiLineString", arcs: input.arcs.map(reindexArcs)}; break;
case "Polygon": output = {type: "Polygon", arcs: input.arcs.map(reindexArcs)}; break;
case "MultiPolygon": output = {type: "MultiPolygon", arcs: input.arcs.map(reindexMultiArcs)}; break;
default: return input;
}
if (input.id != null) output.id = input.id;
if (input.bbox != null) output.bbox = input.bbox;
if (input.properties != null) output.properties = input.properties;
return output;
}
function reindexArc(oldIndex) {
return oldIndex < 0 ? ~newIndexByOldIndex[~oldIndex] : newIndexByOldIndex[oldIndex];
}
function reindexArcs(arcs) {
return arcs.map(reindexArc);
}
function reindexMultiArcs(arcs) {
return arcs.map(reindexArcs);
}
for (key in oldObjects) {
scanGeometry(oldObjects[key]);
}
newArcs = new Array(newArcsLength);
while (++oldIndex < oldArcsLength) {
if (newIndexByOldIndex[oldIndex]) {
newIndexByOldIndex[oldIndex] = ++newIndex;
newArcs[newIndex] = oldArcs[oldIndex];
}
}
for (key in oldObjects) {
newObjects[key] = reindexGeometry(oldObjects[key]);
}
return {
type: "Topology",
bbox: topology.bbox,
transform: topology.transform,
objects: newObjects,
arcs: newArcs
};
};
var filter = function(topology, filter) {
var oldObjects = topology.objects,
newObjects = {},
key;
if (filter == null) filter = filterTrue;
function filterGeometry(input) {
var output, arcs;
switch (input.type) {
case "Polygon": {
arcs = filterRings(input.arcs);
output = arcs ? {type: "Polygon", arcs: arcs} : {type: null};
break;
}
case "MultiPolygon": {
arcs = input.arcs.map(filterRings).filter(filterIdentity);
output = arcs.length ? {type: "MultiPolygon", arcs: arcs} : {type: null};
break;
}
case "GeometryCollection": {
arcs = input.geometries.map(filterGeometry).filter(filterNotNull);
output = arcs.length ? {type: "GeometryCollection", geometries: arcs} : {type: null};
break;
}
default: return input;
}
if (input.id != null) output.id = input.id;
if (input.bbox != null) output.bbox = input.bbox;
if (input.properties != null) output.properties = input.properties;
return output;
}
function filterRings(arcs) {
return arcs.length && filterExteriorRing(arcs[0]) // if the exterior is small, ignore any holes
? [arcs[0]].concat(arcs.slice(1).filter(filterInteriorRing))
: null;
}
function filterExteriorRing(ring) {
return filter(ring, false);
}
function filterInteriorRing(ring) {
return filter(ring, true);
}
for (key in oldObjects) {
newObjects[key] = filterGeometry(oldObjects[key]);
}
return prune({
type: "Topology",
bbox: topology.bbox,
transform: topology.transform,
objects: newObjects,
arcs: topology.arcs
});
};
function filterTrue() {
return true;
}
function filterIdentity(x) {
return x;
}
function filterNotNull(geometry) {
return geometry.type != null;
}
var filterAttached = function(topology) {
var ownerByArc = new Array(topology.arcs.length), // arc index -> index of unique associated ring, or -1 if used by multiple rings
ownerIndex = 0,
key;
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, ++ownerIndex) {
for (var ring = arcs[i], j = 0, m = ring.length; j < m; ++j) {
var arc = ring[j];
if (arc < 0) arc = ~arc;
var owner = ownerByArc[arc];
if (owner == null) ownerByArc[arc] = ownerIndex;
else if (owner !== ownerIndex) ownerByArc[arc] = -1;
}
}
}
for (key in topology.objects) {
testGeometry(topology.objects[key]);
}
return function(ring) {
for (var j = 0, m = ring.length, arc; j < m; ++j) {
if (ownerByArc[(arc = ring[j]) < 0 ? ~arc : arc] === -1) {
return true;
}
}
return false;
};
};
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])) / 2;
}
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;
};
};
var filterAttachedWeight = function(topology, minWeight, weight) {
var a = filterAttached(topology),
w = filterWeight(topology, minWeight, weight);
return function(ring, interior) {
return a(ring, interior) || w(ring, interior);
};
};
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;
};
function copy(point) {
return [point[0], point[1], 0];
}
var presimplify = function(topology, weight) {
var point = topology.transform ? transform(topology.transform) : copy,
heap = newHeap();
if (weight == null) weight = planarTriangleArea;
var arcs = topology.arcs.map(function(arc) {
var triangles = [],
maxWeight = 0,
triangle,
i,
n;
arc = arc.map(point);
for (i = 1, n = arc.length - 1; i < n; ++i) {
triangle = [arc[i - 1], arc[i], arc[i + 1]];
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);
}
}
return arc;
});
function update(triangle) {
heap.remove(triangle);
triangle[1][2] = weight(triangle);
heap.push(triangle);
}
return {
type: "Topology",
bbox: topology.bbox,
objects: topology.objects,
arcs: arcs
};
};
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.
var arcs = topology.arcs.map(function(input) {
var i = -1,
j = 0,
n = input.length,
output = new Array(n), // pessimistic
point;
while (++i < n) {
if ((point = input[i])[2] >= minWeight) {
output[j++] = [point[0], point[1]];
}
}
output.length = j;
return output;
});
return {
type: "Topology",
transform: topology.transform,
bbox: topology.bbox,
objects: topology.objects,
arcs: arcs
};
};
var pi = Math.PI;
var tau = 2 * pi;
var quarterPi = pi / 4;
var radians = pi / 180;
var abs = Math.abs;
var atan2 = Math.atan2;
var cos = Math.cos;
var sin = Math.sin;
function halfArea(ring, closed) {
var i = 0,
n = ring.length,
sum = 0,
point = ring[closed ? i++ : n - 1],
lambda0, lambda1 = point[0] * radians,
phi1 = (point[1] * radians) / 2 + quarterPi,
cosPhi0, cosPhi1 = cos(phi1),
sinPhi0, sinPhi1 = sin(phi1);
for (; i < n; ++i) {
point = ring[i];
lambda0 = lambda1, lambda1 = point[0] * radians;
phi1 = (point[1] * radians) / 2 + quarterPi;
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).
// See https://github.com/d3/d3-geo/blob/master/README.md#geoArea
var dLambda = lambda1 - lambda0,
sdLambda = dLambda >= 0 ? 1 : -1,
adLambda = sdLambda * dLambda,
k = sinPhi0 * sinPhi1,
u = cosPhi0 * cosPhi1 + k * cos(adLambda),
v = k * sdLambda * sin(adLambda);
sum += atan2(v, u);
}
return sum;
}
function sphericalRingArea(ring, interior) {
var sum = halfArea(ring, true);
if (interior) sum *= -1;
return (sum < 0 ? tau + sum : sum) * 2;
}
function sphericalTriangleArea(t) {
return abs(halfArea(t, false)) * 2;
}
exports.bbox = bbox;
exports.feature = feature;
exports.mesh = mesh;
exports.meshArcs = meshArcs;
exports.merge = merge;
exports.mergeArcs = mergeArcs;
exports.neighbors = neighbors;
exports.quantize = quantize;
exports.transform = transform;
exports.untransform = untransform;
exports.topology = topology;
exports.filter = filter;
exports.filterAttached = filterAttached;
exports.filterAttachedWeight = filterAttachedWeight;
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;
Object.defineProperty(exports, '__esModule', { value: true });
})));