123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365366367368369370371372373374375376377378379380381382383384385386387388389390391392393394395396397398399400401402403404405406407408409410411412413414415416417418419420421422423424425426427428429430431432433434435436437438439440441442443444445446447448449450451452453454455456457458459460461462463464465466467468469470471472473474475476477478479480481482483484485486487488489490491492493494495496497498499500501502503504505506507508509510511512513514515516517518519520521522523524525526527528529530531532533534535536537538539540541542543544545546547548549550551552553554555556557558559560561562563564565566567568569570571572573574575576577578579580581582583584585586587588589590591592593594595596597598599600601602603604605606607608609610611612613614615616617618619620621622623624625626627628629630631632633634635636637638639640641642643644645646647648649650651652653654655656657658659660661662663664665666667668669670671672673674675676677678679680681682683684685686687688689690691692693694695696697698699700701702703704705706707708709710711712713714715716717718719720721722723724725726727728729730731732733734735736737738739740741742743744745746747748749750751752753754755756757758759760761762763764765766767768769770771772773774775776777778779780781782783784785786787788789790791792793794795796797798799800801802803804805806807808809810811812813814815816817818819820821822823824825826827828829830831832833834835836837838839840841842843844845846847848849850851852853854855856857858859860861862863864865866867868869870871872873874875876877878879880881882883884885886887888889890891892893894895896897898899900901902903904905906907908909910911912913914915916917918919920921922923924925926927928929930931932933934935936937938939940941942943944945946947948949950951952953954955956957958959960961962963964965966967968969970971972973974975976977978979980981982983984985986987988989990991992993994995996997998999100010011002100310041005100610071008100910101011101210131014101510161017101810191020102110221023102410251026102710281029103010311032103310341035103610371038103910401041104210431044104510461047104810491050105110521053105410551056105710581059106010611062106310641065106610671068106910701071107210731074107510761077107810791080108110821083108410851086108710881089109010911092109310941095109610971098109911001101110211031104110511061107110811091110111111121113111411151116111711181119112011211122112311241125112611271128112911301131113211331134113511361137113811391140114111421143114411451146114711481149115011511152115311541155115611571158115911601161116211631164116511661167116811691170117111721173117411751176117711781179118011811182118311841185118611871188118911901191119211931194119511961197119811991200120112021203120412051206120712081209121012111212121312141215121612171218121912201221122212231224122512261227122812291230123112321233123412351236123712381239124012411242124312441245124612471248124912501251125212531254125512561257125812591260126112621263126412651266126712681269127012711272127312741275127612771278127912801281128212831284128512861287128812891290129112921293129412951296129712981299130013011302130313041305130613071308130913101311131213131314131513161317131813191320132113221323132413251326132713281329133013311332133313341335133613371338133913401341134213431344134513461347134813491350135113521353135413551356135713581359136013611362136313641365136613671368136913701371137213731374137513761377137813791380138113821383138413851386138713881389139013911392139313941395139613971398139914001401140214031404140514061407140814091410141114121413141414151416141714181419142014211422142314241425142614271428142914301431143214331434143514361437143814391440144114421443144414451446144714481449145014511452145314541455145614571458145914601461146214631464146514661467146814691470147114721473147414751476147714781479148014811482148314841485148614871488148914901491149214931494149514961497149814991500150115021503150415051506150715081509151015111512151315141515151615171518151915201521152215231524152515261527152815291530153115321533153415351536153715381539154015411542154315441545154615471548154915501551155215531554155515561557155815591560156115621563156415651566156715681569157015711572157315741575157615771578157915801581158215831584158515861587158815891590159115921593159415951596159715981599160016011602160316041605160616071608160916101611161216131614161516161617161816191620162116221623162416251626162716281629163016311632163316341635163616371638163916401641164216431644164516461647164816491650165116521653165416551656165716581659166016611662166316641665166616671668166916701671167216731674167516761677167816791680168116821683168416851686168716881689169016911692169316941695169616971698169917001701170217031704170517061707170817091710171117121713171417151716171717181719172017211722172317241725172617271728172917301731173217331734173517361737173817391740174117421743174417451746174717481749175017511752175317541755175617571758175917601761176217631764176517661767176817691770177117721773177417751776177717781779178017811782178317841785178617871788178917901791179217931794179517961797179817991800180118021803180418051806180718081809181018111812181318141815181618171818181918201821182218231824182518261827182818291830183118321833183418351836183718381839184018411842184318441845 |
- /**
- @license
- topojson - https://github.com/topojson/topojson
- Copyright (c) 2012-2016, Michael Bostock
- All rights reserved.
- Redistribution and use in source and binary forms, with or without
- modification, are permitted provided that the following conditions are met:
- * Redistributions of source code must retain the above copyright notice, this
- list of conditions and the following disclaimer.
- * Redistributions in binary form must reproduce the above copyright notice,
- this list of conditions and the following disclaimer in the documentation
- and/or other materials provided with the distribution.
- * The name Michael Bostock may not be used to endorse or promote products
- derived from this software without specific prior written permission.
- THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
- AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
- IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
- DISCLAIMED. IN NO EVENT SHALL MICHAEL BOSTOCK BE LIABLE FOR ANY DIRECT,
- INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING,
- BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
- DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY
- OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING
- NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE,
- EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
- **/
- var tmp = {};
- // https://github.com/topojson/topojson Version 3.0.2. Copyright 2017 Mike Bostock.
- (function (global, factory) {
- typeof exports === 'object' && typeof module !== 'undefined' ? factory(exports) :
- (factory((global.topojson = global.topojson || {})));
- }(tmp, (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 });
- })));
- export default tmp.topojson;
|