topojson.js 53 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365366367368369370371372373374375376377378379380381382383384385386387388389390391392393394395396397398399400401402403404405406407408409410411412413414415416417418419420421422423424425426427428429430431432433434435436437438439440441442443444445446447448449450451452453454455456457458459460461462463464465466467468469470471472473474475476477478479480481482483484485486487488489490491492493494495496497498499500501502503504505506507508509510511512513514515516517518519520521522523524525526527528529530531532533534535536537538539540541542543544545546547548549550551552553554555556557558559560561562563564565566567568569570571572573574575576577578579580581582583584585586587588589590591592593594595596597598599600601602603604605606607608609610611612613614615616617618619620621622623624625626627628629630631632633634635636637638639640641642643644645646647648649650651652653654655656657658659660661662663664665666667668669670671672673674675676677678679680681682683684685686687688689690691692693694695696697698699700701702703704705706707708709710711712713714715716717718719720721722723724725726727728729730731732733734735736737738739740741742743744745746747748749750751752753754755756757758759760761762763764765766767768769770771772773774775776777778779780781782783784785786787788789790791792793794795796797798799800801802803804805806807808809810811812813814815816817818819820821822823824825826827828829830831832833834835836837838839840841842843844845846847848849850851852853854855856857858859860861862863864865866867868869870871872873874875876877878879880881882883884885886887888889890891892893894895896897898899900901902903904905906907908909910911912913914915916917918919920921922923924925926927928929930931932933934935936937938939940941942943944945946947948949950951952953954955956957958959960961962963964965966967968969970971972973974975976977978979980981982983984985986987988989990991992993994995996997998999100010011002100310041005100610071008100910101011101210131014101510161017101810191020102110221023102410251026102710281029103010311032103310341035103610371038103910401041104210431044104510461047104810491050105110521053105410551056105710581059106010611062106310641065106610671068106910701071107210731074107510761077107810791080108110821083108410851086108710881089109010911092109310941095109610971098109911001101110211031104110511061107110811091110111111121113111411151116111711181119112011211122112311241125112611271128112911301131113211331134113511361137113811391140114111421143114411451146114711481149115011511152115311541155115611571158115911601161116211631164116511661167116811691170117111721173117411751176117711781179118011811182118311841185118611871188118911901191119211931194119511961197119811991200120112021203120412051206120712081209121012111212121312141215121612171218121912201221122212231224122512261227122812291230123112321233123412351236123712381239124012411242124312441245124612471248124912501251125212531254125512561257125812591260126112621263126412651266126712681269127012711272127312741275127612771278127912801281128212831284128512861287128812891290129112921293129412951296129712981299130013011302130313041305130613071308130913101311131213131314131513161317131813191320132113221323132413251326132713281329133013311332133313341335133613371338133913401341134213431344134513461347134813491350135113521353135413551356135713581359136013611362136313641365136613671368136913701371137213731374137513761377137813791380138113821383138413851386138713881389139013911392139313941395139613971398139914001401140214031404140514061407140814091410141114121413141414151416141714181419142014211422142314241425142614271428142914301431143214331434143514361437143814391440144114421443144414451446144714481449145014511452145314541455145614571458145914601461146214631464146514661467146814691470147114721473147414751476147714781479148014811482148314841485148614871488148914901491149214931494149514961497149814991500150115021503150415051506150715081509151015111512151315141515151615171518151915201521152215231524152515261527152815291530153115321533153415351536153715381539154015411542154315441545154615471548154915501551155215531554155515561557155815591560156115621563156415651566156715681569157015711572157315741575157615771578157915801581158215831584158515861587158815891590159115921593159415951596159715981599160016011602160316041605160616071608160916101611161216131614161516161617161816191620162116221623162416251626162716281629163016311632163316341635163616371638163916401641164216431644164516461647164816491650165116521653165416551656165716581659166016611662166316641665166616671668166916701671167216731674167516761677167816791680168116821683168416851686168716881689169016911692169316941695169616971698169917001701170217031704170517061707170817091710171117121713171417151716171717181719172017211722172317241725172617271728172917301731173217331734173517361737173817391740174117421743174417451746174717481749175017511752175317541755175617571758175917601761176217631764176517661767176817691770177117721773177417751776177717781779178017811782178317841785178617871788178917901791179217931794179517961797179817991800180118021803180418051806180718081809181018111812181318141815181618171818181918201821182218231824182518261827182818291830183118321833183418351836183718381839184018411842184318441845
  1. /**
  2. @license
  3. topojson - https://github.com/topojson/topojson
  4. Copyright (c) 2012-2016, Michael Bostock
  5. All rights reserved.
  6. Redistribution and use in source and binary forms, with or without
  7. modification, are permitted provided that the following conditions are met:
  8. * Redistributions of source code must retain the above copyright notice, this
  9. list of conditions and the following disclaimer.
  10. * Redistributions in binary form must reproduce the above copyright notice,
  11. this list of conditions and the following disclaimer in the documentation
  12. and/or other materials provided with the distribution.
  13. * The name Michael Bostock may not be used to endorse or promote products
  14. derived from this software without specific prior written permission.
  15. THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
  16. AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
  17. IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
  18. DISCLAIMED. IN NO EVENT SHALL MICHAEL BOSTOCK BE LIABLE FOR ANY DIRECT,
  19. INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING,
  20. BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
  21. DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY
  22. OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING
  23. NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE,
  24. EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
  25. **/
  26. var tmp = {};
  27. // https://github.com/topojson/topojson Version 3.0.2. Copyright 2017 Mike Bostock.
  28. (function (global, factory) {
  29. typeof exports === 'object' && typeof module !== 'undefined' ? factory(exports) :
  30. (factory((global.topojson = global.topojson || {})));
  31. }(tmp, (function (exports) { 'use strict';
  32. var identity = function(x) {
  33. return x;
  34. };
  35. var transform = function(transform) {
  36. if (transform == null) return identity;
  37. var x0,
  38. y0,
  39. kx = transform.scale[0],
  40. ky = transform.scale[1],
  41. dx = transform.translate[0],
  42. dy = transform.translate[1];
  43. return function(input, i) {
  44. if (!i) x0 = y0 = 0;
  45. var j = 2, n = input.length, output = new Array(n);
  46. output[0] = (x0 += input[0]) * kx + dx;
  47. output[1] = (y0 += input[1]) * ky + dy;
  48. while (j < n) output[j] = input[j], ++j;
  49. return output;
  50. };
  51. };
  52. var bbox = function(topology) {
  53. var t = transform(topology.transform), key,
  54. x0 = Infinity, y0 = x0, x1 = -x0, y1 = -x0;
  55. function bboxPoint(p) {
  56. p = t(p);
  57. if (p[0] < x0) x0 = p[0];
  58. if (p[0] > x1) x1 = p[0];
  59. if (p[1] < y0) y0 = p[1];
  60. if (p[1] > y1) y1 = p[1];
  61. }
  62. function bboxGeometry(o) {
  63. switch (o.type) {
  64. case "GeometryCollection": o.geometries.forEach(bboxGeometry); break;
  65. case "Point": bboxPoint(o.coordinates); break;
  66. case "MultiPoint": o.coordinates.forEach(bboxPoint); break;
  67. }
  68. }
  69. topology.arcs.forEach(function(arc) {
  70. var i = -1, n = arc.length, p;
  71. while (++i < n) {
  72. p = t(arc[i], i);
  73. if (p[0] < x0) x0 = p[0];
  74. if (p[0] > x1) x1 = p[0];
  75. if (p[1] < y0) y0 = p[1];
  76. if (p[1] > y1) y1 = p[1];
  77. }
  78. });
  79. for (key in topology.objects) {
  80. bboxGeometry(topology.objects[key]);
  81. }
  82. return [x0, y0, x1, y1];
  83. };
  84. var reverse = function(array, n) {
  85. var t, j = array.length, i = j - n;
  86. while (i < --j) t = array[i], array[i++] = array[j], array[j] = t;
  87. };
  88. var feature = function(topology, o) {
  89. return o.type === "GeometryCollection"
  90. ? {type: "FeatureCollection", features: o.geometries.map(function(o) { return feature$1(topology, o); })}
  91. : feature$1(topology, o);
  92. };
  93. function feature$1(topology, o) {
  94. var id = o.id,
  95. bbox = o.bbox,
  96. properties = o.properties == null ? {} : o.properties,
  97. geometry = object(topology, o);
  98. return id == null && bbox == null ? {type: "Feature", properties: properties, geometry: geometry}
  99. : bbox == null ? {type: "Feature", id: id, properties: properties, geometry: geometry}
  100. : {type: "Feature", id: id, bbox: bbox, properties: properties, geometry: geometry};
  101. }
  102. function object(topology, o) {
  103. var transformPoint = transform(topology.transform),
  104. arcs = topology.arcs;
  105. function arc(i, points) {
  106. if (points.length) points.pop();
  107. for (var a = arcs[i < 0 ? ~i : i], k = 0, n = a.length; k < n; ++k) {
  108. points.push(transformPoint(a[k], k));
  109. }
  110. if (i < 0) reverse(points, n);
  111. }
  112. function point(p) {
  113. return transformPoint(p);
  114. }
  115. function line(arcs) {
  116. var points = [];
  117. for (var i = 0, n = arcs.length; i < n; ++i) arc(arcs[i], points);
  118. if (points.length < 2) points.push(points[0]); // This should never happen per the specification.
  119. return points;
  120. }
  121. function ring(arcs) {
  122. var points = line(arcs);
  123. while (points.length < 4) points.push(points[0]); // This may happen if an arc has only two points.
  124. return points;
  125. }
  126. function polygon(arcs) {
  127. return arcs.map(ring);
  128. }
  129. function geometry(o) {
  130. var type = o.type, coordinates;
  131. switch (type) {
  132. case "GeometryCollection": return {type: type, geometries: o.geometries.map(geometry)};
  133. case "Point": coordinates = point(o.coordinates); break;
  134. case "MultiPoint": coordinates = o.coordinates.map(point); break;
  135. case "LineString": coordinates = line(o.arcs); break;
  136. case "MultiLineString": coordinates = o.arcs.map(line); break;
  137. case "Polygon": coordinates = polygon(o.arcs); break;
  138. case "MultiPolygon": coordinates = o.arcs.map(polygon); break;
  139. default: return null;
  140. }
  141. return {type: type, coordinates: coordinates};
  142. }
  143. return geometry(o);
  144. }
  145. var stitch = function(topology, arcs) {
  146. var stitchedArcs = {},
  147. fragmentByStart = {},
  148. fragmentByEnd = {},
  149. fragments = [],
  150. emptyIndex = -1;
  151. // Stitch empty arcs first, since they may be subsumed by other arcs.
  152. arcs.forEach(function(i, j) {
  153. var arc = topology.arcs[i < 0 ? ~i : i], t;
  154. if (arc.length < 3 && !arc[1][0] && !arc[1][1]) {
  155. t = arcs[++emptyIndex], arcs[emptyIndex] = i, arcs[j] = t;
  156. }
  157. });
  158. arcs.forEach(function(i) {
  159. var e = ends(i),
  160. start = e[0],
  161. end = e[1],
  162. f, g;
  163. if (f = fragmentByEnd[start]) {
  164. delete fragmentByEnd[f.end];
  165. f.push(i);
  166. f.end = end;
  167. if (g = fragmentByStart[end]) {
  168. delete fragmentByStart[g.start];
  169. var fg = g === f ? f : f.concat(g);
  170. fragmentByStart[fg.start = f.start] = fragmentByEnd[fg.end = g.end] = fg;
  171. } else {
  172. fragmentByStart[f.start] = fragmentByEnd[f.end] = f;
  173. }
  174. } else if (f = fragmentByStart[end]) {
  175. delete fragmentByStart[f.start];
  176. f.unshift(i);
  177. f.start = start;
  178. if (g = fragmentByEnd[start]) {
  179. delete fragmentByEnd[g.end];
  180. var gf = g === f ? f : g.concat(f);
  181. fragmentByStart[gf.start = g.start] = fragmentByEnd[gf.end = f.end] = gf;
  182. } else {
  183. fragmentByStart[f.start] = fragmentByEnd[f.end] = f;
  184. }
  185. } else {
  186. f = [i];
  187. fragmentByStart[f.start = start] = fragmentByEnd[f.end = end] = f;
  188. }
  189. });
  190. function ends(i) {
  191. var arc = topology.arcs[i < 0 ? ~i : i], p0 = arc[0], p1;
  192. if (topology.transform) p1 = [0, 0], arc.forEach(function(dp) { p1[0] += dp[0], p1[1] += dp[1]; });
  193. else p1 = arc[arc.length - 1];
  194. return i < 0 ? [p1, p0] : [p0, p1];
  195. }
  196. function flush(fragmentByEnd, fragmentByStart) {
  197. for (var k in fragmentByEnd) {
  198. var f = fragmentByEnd[k];
  199. delete fragmentByStart[f.start];
  200. delete f.start;
  201. delete f.end;
  202. f.forEach(function(i) { stitchedArcs[i < 0 ? ~i : i] = 1; });
  203. fragments.push(f);
  204. }
  205. }
  206. flush(fragmentByEnd, fragmentByStart);
  207. flush(fragmentByStart, fragmentByEnd);
  208. arcs.forEach(function(i) { if (!stitchedArcs[i < 0 ? ~i : i]) fragments.push([i]); });
  209. return fragments;
  210. };
  211. var mesh = function(topology) {
  212. return object(topology, meshArcs.apply(this, arguments));
  213. };
  214. function meshArcs(topology, object$$1, filter) {
  215. var arcs, i, n;
  216. if (arguments.length > 1) arcs = extractArcs(topology, object$$1, filter);
  217. else for (i = 0, arcs = new Array(n = topology.arcs.length); i < n; ++i) arcs[i] = i;
  218. return {type: "MultiLineString", arcs: stitch(topology, arcs)};
  219. }
  220. function extractArcs(topology, object$$1, filter) {
  221. var arcs = [],
  222. geomsByArc = [],
  223. geom;
  224. function extract0(i) {
  225. var j = i < 0 ? ~i : i;
  226. (geomsByArc[j] || (geomsByArc[j] = [])).push({i: i, g: geom});
  227. }
  228. function extract1(arcs) {
  229. arcs.forEach(extract0);
  230. }
  231. function extract2(arcs) {
  232. arcs.forEach(extract1);
  233. }
  234. function extract3(arcs) {
  235. arcs.forEach(extract2);
  236. }
  237. function geometry(o) {
  238. switch (geom = o, o.type) {
  239. case "GeometryCollection": o.geometries.forEach(geometry); break;
  240. case "LineString": extract1(o.arcs); break;
  241. case "MultiLineString": case "Polygon": extract2(o.arcs); break;
  242. case "MultiPolygon": extract3(o.arcs); break;
  243. }
  244. }
  245. geometry(object$$1);
  246. geomsByArc.forEach(filter == null
  247. ? function(geoms) { arcs.push(geoms[0].i); }
  248. : function(geoms) { if (filter(geoms[0].g, geoms[geoms.length - 1].g)) arcs.push(geoms[0].i); });
  249. return arcs;
  250. }
  251. function planarRingArea(ring) {
  252. var i = -1, n = ring.length, a, b = ring[n - 1], area = 0;
  253. while (++i < n) a = b, b = ring[i], area += a[0] * b[1] - a[1] * b[0];
  254. return Math.abs(area); // Note: doubled area!
  255. }
  256. var merge = function(topology) {
  257. return object(topology, mergeArcs.apply(this, arguments));
  258. };
  259. function mergeArcs(topology, objects) {
  260. var polygonsByArc = {},
  261. polygons = [],
  262. groups = [];
  263. objects.forEach(geometry);
  264. function geometry(o) {
  265. switch (o.type) {
  266. case "GeometryCollection": o.geometries.forEach(geometry); break;
  267. case "Polygon": extract(o.arcs); break;
  268. case "MultiPolygon": o.arcs.forEach(extract); break;
  269. }
  270. }
  271. function extract(polygon) {
  272. polygon.forEach(function(ring) {
  273. ring.forEach(function(arc) {
  274. (polygonsByArc[arc = arc < 0 ? ~arc : arc] || (polygonsByArc[arc] = [])).push(polygon);
  275. });
  276. });
  277. polygons.push(polygon);
  278. }
  279. function area(ring) {
  280. return planarRingArea(object(topology, {type: "Polygon", arcs: [ring]}).coordinates[0]);
  281. }
  282. polygons.forEach(function(polygon) {
  283. if (!polygon._) {
  284. var group = [],
  285. neighbors = [polygon];
  286. polygon._ = 1;
  287. groups.push(group);
  288. while (polygon = neighbors.pop()) {
  289. group.push(polygon);
  290. polygon.forEach(function(ring) {
  291. ring.forEach(function(arc) {
  292. polygonsByArc[arc < 0 ? ~arc : arc].forEach(function(polygon) {
  293. if (!polygon._) {
  294. polygon._ = 1;
  295. neighbors.push(polygon);
  296. }
  297. });
  298. });
  299. });
  300. }
  301. }
  302. });
  303. polygons.forEach(function(polygon) {
  304. delete polygon._;
  305. });
  306. return {
  307. type: "MultiPolygon",
  308. arcs: groups.map(function(polygons) {
  309. var arcs = [], n;
  310. // Extract the exterior (unique) arcs.
  311. polygons.forEach(function(polygon) {
  312. polygon.forEach(function(ring) {
  313. ring.forEach(function(arc) {
  314. if (polygonsByArc[arc < 0 ? ~arc : arc].length < 2) {
  315. arcs.push(arc);
  316. }
  317. });
  318. });
  319. });
  320. // Stitch the arcs into one or more rings.
  321. arcs = stitch(topology, arcs);
  322. // If more than one ring is returned,
  323. // at most one of these rings can be the exterior;
  324. // choose the one with the greatest absolute area.
  325. if ((n = arcs.length) > 1) {
  326. for (var i = 1, k = area(arcs[0]), ki, t; i < n; ++i) {
  327. if ((ki = area(arcs[i])) > k) {
  328. t = arcs[0], arcs[0] = arcs[i], arcs[i] = t, k = ki;
  329. }
  330. }
  331. }
  332. return arcs;
  333. })
  334. };
  335. }
  336. var bisect = function(a, x) {
  337. var lo = 0, hi = a.length;
  338. while (lo < hi) {
  339. var mid = lo + hi >>> 1;
  340. if (a[mid] < x) lo = mid + 1;
  341. else hi = mid;
  342. }
  343. return lo;
  344. };
  345. var neighbors = function(objects) {
  346. var indexesByArc = {}, // arc index -> array of object indexes
  347. neighbors = objects.map(function() { return []; });
  348. function line(arcs, i) {
  349. arcs.forEach(function(a) {
  350. if (a < 0) a = ~a;
  351. var o = indexesByArc[a];
  352. if (o) o.push(i);
  353. else indexesByArc[a] = [i];
  354. });
  355. }
  356. function polygon(arcs, i) {
  357. arcs.forEach(function(arc) { line(arc, i); });
  358. }
  359. function geometry(o, i) {
  360. if (o.type === "GeometryCollection") o.geometries.forEach(function(o) { geometry(o, i); });
  361. else if (o.type in geometryType) geometryType[o.type](o.arcs, i);
  362. }
  363. var geometryType = {
  364. LineString: line,
  365. MultiLineString: polygon,
  366. Polygon: polygon,
  367. MultiPolygon: function(arcs, i) { arcs.forEach(function(arc) { polygon(arc, i); }); }
  368. };
  369. objects.forEach(geometry);
  370. for (var i in indexesByArc) {
  371. for (var indexes = indexesByArc[i], m = indexes.length, j = 0; j < m; ++j) {
  372. for (var k = j + 1; k < m; ++k) {
  373. var ij = indexes[j], ik = indexes[k], n;
  374. if ((n = neighbors[ij])[i = bisect(n, ik)] !== ik) n.splice(i, 0, ik);
  375. if ((n = neighbors[ik])[i = bisect(n, ij)] !== ij) n.splice(i, 0, ij);
  376. }
  377. }
  378. }
  379. return neighbors;
  380. };
  381. var untransform = function(transform) {
  382. if (transform == null) return identity;
  383. var x0,
  384. y0,
  385. kx = transform.scale[0],
  386. ky = transform.scale[1],
  387. dx = transform.translate[0],
  388. dy = transform.translate[1];
  389. return function(input, i) {
  390. if (!i) x0 = y0 = 0;
  391. var j = 2,
  392. n = input.length,
  393. output = new Array(n),
  394. x1 = Math.round((input[0] - dx) / kx),
  395. y1 = Math.round((input[1] - dy) / ky);
  396. output[0] = x1 - x0, x0 = x1;
  397. output[1] = y1 - y0, y0 = y1;
  398. while (j < n) output[j] = input[j], ++j;
  399. return output;
  400. };
  401. };
  402. var quantize = function(topology, transform) {
  403. if (topology.transform) throw new Error("already quantized");
  404. if (!transform || !transform.scale) {
  405. if (!((n = Math.floor(transform)) >= 2)) throw new Error("n must be \u22652");
  406. box = topology.bbox || bbox(topology);
  407. var x0 = box[0], y0 = box[1], x1 = box[2], y1 = box[3], n;
  408. transform = {scale: [x1 - x0 ? (x1 - x0) / (n - 1) : 1, y1 - y0 ? (y1 - y0) / (n - 1) : 1], translate: [x0, y0]};
  409. } else {
  410. box = topology.bbox;
  411. }
  412. var t = untransform(transform), box, key, inputs = topology.objects, outputs = {};
  413. function quantizePoint(point) {
  414. return t(point);
  415. }
  416. function quantizeGeometry(input) {
  417. var output;
  418. switch (input.type) {
  419. case "GeometryCollection": output = {type: "GeometryCollection", geometries: input.geometries.map(quantizeGeometry)}; break;
  420. case "Point": output = {type: "Point", coordinates: quantizePoint(input.coordinates)}; break;
  421. case "MultiPoint": output = {type: "MultiPoint", coordinates: input.coordinates.map(quantizePoint)}; break;
  422. default: return input;
  423. }
  424. if (input.id != null) output.id = input.id;
  425. if (input.bbox != null) output.bbox = input.bbox;
  426. if (input.properties != null) output.properties = input.properties;
  427. return output;
  428. }
  429. function quantizeArc(input) {
  430. var i = 0, j = 1, n = input.length, p, output = new Array(n); // pessimistic
  431. output[0] = t(input[0], 0);
  432. while (++i < n) if ((p = t(input[i], i))[0] || p[1]) output[j++] = p; // non-coincident points
  433. if (j === 1) output[j++] = [0, 0]; // an arc must have at least two points
  434. output.length = j;
  435. return output;
  436. }
  437. for (key in inputs) outputs[key] = quantizeGeometry(inputs[key]);
  438. return {
  439. type: "Topology",
  440. bbox: box,
  441. transform: transform,
  442. objects: outputs,
  443. arcs: topology.arcs.map(quantizeArc)
  444. };
  445. };
  446. // Computes the bounding box of the specified hash of GeoJSON objects.
  447. var bounds = function(objects) {
  448. var x0 = Infinity,
  449. y0 = Infinity,
  450. x1 = -Infinity,
  451. y1 = -Infinity;
  452. function boundGeometry(geometry) {
  453. if (geometry != null && boundGeometryType.hasOwnProperty(geometry.type)) boundGeometryType[geometry.type](geometry);
  454. }
  455. var boundGeometryType = {
  456. GeometryCollection: function(o) { o.geometries.forEach(boundGeometry); },
  457. Point: function(o) { boundPoint(o.coordinates); },
  458. MultiPoint: function(o) { o.coordinates.forEach(boundPoint); },
  459. LineString: function(o) { boundLine(o.arcs); },
  460. MultiLineString: function(o) { o.arcs.forEach(boundLine); },
  461. Polygon: function(o) { o.arcs.forEach(boundLine); },
  462. MultiPolygon: function(o) { o.arcs.forEach(boundMultiLine); }
  463. };
  464. function boundPoint(coordinates) {
  465. var x = coordinates[0],
  466. y = coordinates[1];
  467. if (x < x0) x0 = x;
  468. if (x > x1) x1 = x;
  469. if (y < y0) y0 = y;
  470. if (y > y1) y1 = y;
  471. }
  472. function boundLine(coordinates) {
  473. coordinates.forEach(boundPoint);
  474. }
  475. function boundMultiLine(coordinates) {
  476. coordinates.forEach(boundLine);
  477. }
  478. for (var key in objects) {
  479. boundGeometry(objects[key]);
  480. }
  481. return x1 >= x0 && y1 >= y0 ? [x0, y0, x1, y1] : undefined;
  482. };
  483. var hashset = function(size, hash, equal, type, empty) {
  484. if (arguments.length === 3) {
  485. type = Array;
  486. empty = null;
  487. }
  488. var store = new type(size = 1 << Math.max(4, Math.ceil(Math.log(size) / Math.LN2))),
  489. mask = size - 1;
  490. for (var i = 0; i < size; ++i) {
  491. store[i] = empty;
  492. }
  493. function add(value) {
  494. var index = hash(value) & mask,
  495. match = store[index],
  496. collisions = 0;
  497. while (match != empty) {
  498. if (equal(match, value)) return true;
  499. if (++collisions >= size) throw new Error("full hashset");
  500. match = store[index = (index + 1) & mask];
  501. }
  502. store[index] = value;
  503. return true;
  504. }
  505. function has(value) {
  506. var index = hash(value) & mask,
  507. match = store[index],
  508. collisions = 0;
  509. while (match != empty) {
  510. if (equal(match, value)) return true;
  511. if (++collisions >= size) break;
  512. match = store[index = (index + 1) & mask];
  513. }
  514. return false;
  515. }
  516. function values() {
  517. var values = [];
  518. for (var i = 0, n = store.length; i < n; ++i) {
  519. var match = store[i];
  520. if (match != empty) values.push(match);
  521. }
  522. return values;
  523. }
  524. return {
  525. add: add,
  526. has: has,
  527. values: values
  528. };
  529. };
  530. var hashmap = function(size, hash, equal, keyType, keyEmpty, valueType) {
  531. if (arguments.length === 3) {
  532. keyType = valueType = Array;
  533. keyEmpty = null;
  534. }
  535. var keystore = new keyType(size = 1 << Math.max(4, Math.ceil(Math.log(size) / Math.LN2))),
  536. valstore = new valueType(size),
  537. mask = size - 1;
  538. for (var i = 0; i < size; ++i) {
  539. keystore[i] = keyEmpty;
  540. }
  541. function set(key, value) {
  542. var index = hash(key) & mask,
  543. matchKey = keystore[index],
  544. collisions = 0;
  545. while (matchKey != keyEmpty) {
  546. if (equal(matchKey, key)) return valstore[index] = value;
  547. if (++collisions >= size) throw new Error("full hashmap");
  548. matchKey = keystore[index = (index + 1) & mask];
  549. }
  550. keystore[index] = key;
  551. valstore[index] = value;
  552. return value;
  553. }
  554. function maybeSet(key, value) {
  555. var index = hash(key) & mask,
  556. matchKey = keystore[index],
  557. collisions = 0;
  558. while (matchKey != keyEmpty) {
  559. if (equal(matchKey, key)) return valstore[index];
  560. if (++collisions >= size) throw new Error("full hashmap");
  561. matchKey = keystore[index = (index + 1) & mask];
  562. }
  563. keystore[index] = key;
  564. valstore[index] = value;
  565. return value;
  566. }
  567. function get(key, missingValue) {
  568. var index = hash(key) & mask,
  569. matchKey = keystore[index],
  570. collisions = 0;
  571. while (matchKey != keyEmpty) {
  572. if (equal(matchKey, key)) return valstore[index];
  573. if (++collisions >= size) break;
  574. matchKey = keystore[index = (index + 1) & mask];
  575. }
  576. return missingValue;
  577. }
  578. function keys() {
  579. var keys = [];
  580. for (var i = 0, n = keystore.length; i < n; ++i) {
  581. var matchKey = keystore[i];
  582. if (matchKey != keyEmpty) keys.push(matchKey);
  583. }
  584. return keys;
  585. }
  586. return {
  587. set: set,
  588. maybeSet: maybeSet, // set if unset
  589. get: get,
  590. keys: keys
  591. };
  592. };
  593. var equalPoint = function(pointA, pointB) {
  594. return pointA[0] === pointB[0] && pointA[1] === pointB[1];
  595. };
  596. // TODO if quantized, use simpler Int32 hashing?
  597. var buffer = new ArrayBuffer(16);
  598. var uints = new Uint32Array(buffer);
  599. var hashPoint = function(point) {
  600. var hash = uints[0] ^ uints[1];
  601. hash = hash << 5 ^ hash >> 7 ^ uints[2] ^ uints[3];
  602. return hash & 0x7fffffff;
  603. };
  604. // Given an extracted (pre-)topology, identifies all of the junctions. These are
  605. // the points at which arcs (lines or rings) will need to be cut so that each
  606. // arc is represented uniquely.
  607. //
  608. // A junction is a point where at least one arc deviates from another arc going
  609. // through the same point. For example, consider the point B. If there is a arc
  610. // through ABC and another arc through CBA, then B is not a junction because in
  611. // both cases the adjacent point pairs are {A,C}. However, if there is an
  612. // additional arc ABD, then {A,D} != {A,C}, and thus B becomes a junction.
  613. //
  614. // For a closed ring ABCA, the first point A’s adjacent points are the second
  615. // and last point {B,C}. For a line, the first and last point are always
  616. // considered junctions, even if the line is closed; this ensures that a closed
  617. // line is never rotated.
  618. var join = function(topology) {
  619. var coordinates = topology.coordinates,
  620. lines = topology.lines,
  621. rings = topology.rings,
  622. indexes = index(),
  623. visitedByIndex = new Int32Array(coordinates.length),
  624. leftByIndex = new Int32Array(coordinates.length),
  625. rightByIndex = new Int32Array(coordinates.length),
  626. junctionByIndex = new Int8Array(coordinates.length),
  627. junctionCount = 0, // upper bound on number of junctions
  628. i, n,
  629. previousIndex,
  630. currentIndex,
  631. nextIndex;
  632. for (i = 0, n = coordinates.length; i < n; ++i) {
  633. visitedByIndex[i] = leftByIndex[i] = rightByIndex[i] = -1;
  634. }
  635. for (i = 0, n = lines.length; i < n; ++i) {
  636. var line = lines[i],
  637. lineStart = line[0],
  638. lineEnd = line[1];
  639. currentIndex = indexes[lineStart];
  640. nextIndex = indexes[++lineStart];
  641. ++junctionCount, junctionByIndex[currentIndex] = 1; // start
  642. while (++lineStart <= lineEnd) {
  643. sequence(i, previousIndex = currentIndex, currentIndex = nextIndex, nextIndex = indexes[lineStart]);
  644. }
  645. ++junctionCount, junctionByIndex[nextIndex] = 1; // end
  646. }
  647. for (i = 0, n = coordinates.length; i < n; ++i) {
  648. visitedByIndex[i] = -1;
  649. }
  650. for (i = 0, n = rings.length; i < n; ++i) {
  651. var ring = rings[i],
  652. ringStart = ring[0] + 1,
  653. ringEnd = ring[1];
  654. previousIndex = indexes[ringEnd - 1];
  655. currentIndex = indexes[ringStart - 1];
  656. nextIndex = indexes[ringStart];
  657. sequence(i, previousIndex, currentIndex, nextIndex);
  658. while (++ringStart <= ringEnd) {
  659. sequence(i, previousIndex = currentIndex, currentIndex = nextIndex, nextIndex = indexes[ringStart]);
  660. }
  661. }
  662. function sequence(i, previousIndex, currentIndex, nextIndex) {
  663. if (visitedByIndex[currentIndex] === i) return; // ignore self-intersection
  664. visitedByIndex[currentIndex] = i;
  665. var leftIndex = leftByIndex[currentIndex];
  666. if (leftIndex >= 0) {
  667. var rightIndex = rightByIndex[currentIndex];
  668. if ((leftIndex !== previousIndex || rightIndex !== nextIndex)
  669. && (leftIndex !== nextIndex || rightIndex !== previousIndex)) {
  670. ++junctionCount, junctionByIndex[currentIndex] = 1;
  671. }
  672. } else {
  673. leftByIndex[currentIndex] = previousIndex;
  674. rightByIndex[currentIndex] = nextIndex;
  675. }
  676. }
  677. function index() {
  678. var indexByPoint = hashmap(coordinates.length * 1.4, hashIndex, equalIndex, Int32Array, -1, Int32Array),
  679. indexes = new Int32Array(coordinates.length);
  680. for (var i = 0, n = coordinates.length; i < n; ++i) {
  681. indexes[i] = indexByPoint.maybeSet(i, i);
  682. }
  683. return indexes;
  684. }
  685. function hashIndex(i) {
  686. return hashPoint(coordinates[i]);
  687. }
  688. function equalIndex(i, j) {
  689. return equalPoint(coordinates[i], coordinates[j]);
  690. }
  691. visitedByIndex = leftByIndex = rightByIndex = null;
  692. var junctionByPoint = hashset(junctionCount * 1.4, hashPoint, equalPoint), j;
  693. // Convert back to a standard hashset by point for caller convenience.
  694. for (i = 0, n = coordinates.length; i < n; ++i) {
  695. if (junctionByIndex[j = indexes[i]]) {
  696. junctionByPoint.add(coordinates[j]);
  697. }
  698. }
  699. return junctionByPoint;
  700. };
  701. // Given an extracted (pre-)topology, cuts (or rotates) arcs so that all shared
  702. // point sequences are identified. The topology can then be subsequently deduped
  703. // to remove exact duplicate arcs.
  704. var cut = function(topology) {
  705. var junctions = join(topology),
  706. coordinates = topology.coordinates,
  707. lines = topology.lines,
  708. rings = topology.rings,
  709. next,
  710. i, n;
  711. for (i = 0, n = lines.length; i < n; ++i) {
  712. var line = lines[i],
  713. lineMid = line[0],
  714. lineEnd = line[1];
  715. while (++lineMid < lineEnd) {
  716. if (junctions.has(coordinates[lineMid])) {
  717. next = {0: lineMid, 1: line[1]};
  718. line[1] = lineMid;
  719. line = line.next = next;
  720. }
  721. }
  722. }
  723. for (i = 0, n = rings.length; i < n; ++i) {
  724. var ring = rings[i],
  725. ringStart = ring[0],
  726. ringMid = ringStart,
  727. ringEnd = ring[1],
  728. ringFixed = junctions.has(coordinates[ringStart]);
  729. while (++ringMid < ringEnd) {
  730. if (junctions.has(coordinates[ringMid])) {
  731. if (ringFixed) {
  732. next = {0: ringMid, 1: ring[1]};
  733. ring[1] = ringMid;
  734. ring = ring.next = next;
  735. } else { // For the first junction, we can rotate rather than cut.
  736. rotateArray(coordinates, ringStart, ringEnd, ringEnd - ringMid);
  737. coordinates[ringEnd] = coordinates[ringStart];
  738. ringFixed = true;
  739. ringMid = ringStart; // restart; we may have skipped junctions
  740. }
  741. }
  742. }
  743. }
  744. return topology;
  745. };
  746. function rotateArray(array, start, end, offset) {
  747. reverse$1(array, start, end);
  748. reverse$1(array, start, start + offset);
  749. reverse$1(array, start + offset, end);
  750. }
  751. function reverse$1(array, start, end) {
  752. for (var mid = start + ((end-- - start) >> 1), t; start < mid; ++start, --end) {
  753. t = array[start], array[start] = array[end], array[end] = t;
  754. }
  755. }
  756. // Given a cut topology, combines duplicate arcs.
  757. var dedup = function(topology) {
  758. var coordinates = topology.coordinates,
  759. lines = topology.lines, line,
  760. rings = topology.rings, ring,
  761. arcCount = lines.length + rings.length,
  762. i, n;
  763. delete topology.lines;
  764. delete topology.rings;
  765. // Count the number of (non-unique) arcs to initialize the hashmap safely.
  766. for (i = 0, n = lines.length; i < n; ++i) {
  767. line = lines[i]; while (line = line.next) ++arcCount;
  768. }
  769. for (i = 0, n = rings.length; i < n; ++i) {
  770. ring = rings[i]; while (ring = ring.next) ++arcCount;
  771. }
  772. var arcsByEnd = hashmap(arcCount * 2 * 1.4, hashPoint, equalPoint),
  773. arcs = topology.arcs = [];
  774. for (i = 0, n = lines.length; i < n; ++i) {
  775. line = lines[i];
  776. do {
  777. dedupLine(line);
  778. } while (line = line.next);
  779. }
  780. for (i = 0, n = rings.length; i < n; ++i) {
  781. ring = rings[i];
  782. if (ring.next) { // arc is no longer closed
  783. do {
  784. dedupLine(ring);
  785. } while (ring = ring.next);
  786. } else {
  787. dedupRing(ring);
  788. }
  789. }
  790. function dedupLine(arc) {
  791. var startPoint,
  792. endPoint,
  793. startArcs, startArc,
  794. endArcs, endArc,
  795. i, n;
  796. // Does this arc match an existing arc in order?
  797. if (startArcs = arcsByEnd.get(startPoint = coordinates[arc[0]])) {
  798. for (i = 0, n = startArcs.length; i < n; ++i) {
  799. startArc = startArcs[i];
  800. if (equalLine(startArc, arc)) {
  801. arc[0] = startArc[0];
  802. arc[1] = startArc[1];
  803. return;
  804. }
  805. }
  806. }
  807. // Does this arc match an existing arc in reverse order?
  808. if (endArcs = arcsByEnd.get(endPoint = coordinates[arc[1]])) {
  809. for (i = 0, n = endArcs.length; i < n; ++i) {
  810. endArc = endArcs[i];
  811. if (reverseEqualLine(endArc, arc)) {
  812. arc[1] = endArc[0];
  813. arc[0] = endArc[1];
  814. return;
  815. }
  816. }
  817. }
  818. if (startArcs) startArcs.push(arc); else arcsByEnd.set(startPoint, [arc]);
  819. if (endArcs) endArcs.push(arc); else arcsByEnd.set(endPoint, [arc]);
  820. arcs.push(arc);
  821. }
  822. function dedupRing(arc) {
  823. var endPoint,
  824. endArcs,
  825. endArc,
  826. i, n;
  827. // Does this arc match an existing line in order, or reverse order?
  828. // Rings are closed, so their start point and end point is the same.
  829. if (endArcs = arcsByEnd.get(endPoint = coordinates[arc[0]])) {
  830. for (i = 0, n = endArcs.length; i < n; ++i) {
  831. endArc = endArcs[i];
  832. if (equalRing(endArc, arc)) {
  833. arc[0] = endArc[0];
  834. arc[1] = endArc[1];
  835. return;
  836. }
  837. if (reverseEqualRing(endArc, arc)) {
  838. arc[0] = endArc[1];
  839. arc[1] = endArc[0];
  840. return;
  841. }
  842. }
  843. }
  844. // Otherwise, does this arc match an existing ring in order, or reverse order?
  845. if (endArcs = arcsByEnd.get(endPoint = coordinates[arc[0] + findMinimumOffset(arc)])) {
  846. for (i = 0, n = endArcs.length; i < n; ++i) {
  847. endArc = endArcs[i];
  848. if (equalRing(endArc, arc)) {
  849. arc[0] = endArc[0];
  850. arc[1] = endArc[1];
  851. return;
  852. }
  853. if (reverseEqualRing(endArc, arc)) {
  854. arc[0] = endArc[1];
  855. arc[1] = endArc[0];
  856. return;
  857. }
  858. }
  859. }
  860. if (endArcs) endArcs.push(arc); else arcsByEnd.set(endPoint, [arc]);
  861. arcs.push(arc);
  862. }
  863. function equalLine(arcA, arcB) {
  864. var ia = arcA[0], ib = arcB[0],
  865. ja = arcA[1], jb = arcB[1];
  866. if (ia - ja !== ib - jb) return false;
  867. for (; ia <= ja; ++ia, ++ib) if (!equalPoint(coordinates[ia], coordinates[ib])) return false;
  868. return true;
  869. }
  870. function reverseEqualLine(arcA, arcB) {
  871. var ia = arcA[0], ib = arcB[0],
  872. ja = arcA[1], jb = arcB[1];
  873. if (ia - ja !== ib - jb) return false;
  874. for (; ia <= ja; ++ia, --jb) if (!equalPoint(coordinates[ia], coordinates[jb])) return false;
  875. return true;
  876. }
  877. function equalRing(arcA, arcB) {
  878. var ia = arcA[0], ib = arcB[0],
  879. ja = arcA[1], jb = arcB[1],
  880. n = ja - ia;
  881. if (n !== jb - ib) return false;
  882. var ka = findMinimumOffset(arcA),
  883. kb = findMinimumOffset(arcB);
  884. for (var i = 0; i < n; ++i) {
  885. if (!equalPoint(coordinates[ia + (i + ka) % n], coordinates[ib + (i + kb) % n])) return false;
  886. }
  887. return true;
  888. }
  889. function reverseEqualRing(arcA, arcB) {
  890. var ia = arcA[0], ib = arcB[0],
  891. ja = arcA[1], jb = arcB[1],
  892. n = ja - ia;
  893. if (n !== jb - ib) return false;
  894. var ka = findMinimumOffset(arcA),
  895. kb = n - findMinimumOffset(arcB);
  896. for (var i = 0; i < n; ++i) {
  897. if (!equalPoint(coordinates[ia + (i + ka) % n], coordinates[jb - (i + kb) % n])) return false;
  898. }
  899. return true;
  900. }
  901. // Rings are rotated to a consistent, but arbitrary, start point.
  902. // This is necessary to detect when a ring and a rotated copy are dupes.
  903. function findMinimumOffset(arc) {
  904. var start = arc[0],
  905. end = arc[1],
  906. mid = start,
  907. minimum = mid,
  908. minimumPoint = coordinates[mid];
  909. while (++mid < end) {
  910. var point = coordinates[mid];
  911. if (point[0] < minimumPoint[0] || point[0] === minimumPoint[0] && point[1] < minimumPoint[1]) {
  912. minimum = mid;
  913. minimumPoint = point;
  914. }
  915. }
  916. return minimum - start;
  917. }
  918. return topology;
  919. };
  920. // Given an array of arcs in absolute (but already quantized!) coordinates,
  921. // converts to fixed-point delta encoding.
  922. // This is a destructive operation that modifies the given arcs!
  923. var delta = function(arcs) {
  924. var i = -1,
  925. n = arcs.length;
  926. while (++i < n) {
  927. var arc = arcs[i],
  928. j = 0,
  929. k = 1,
  930. m = arc.length,
  931. point = arc[0],
  932. x0 = point[0],
  933. y0 = point[1],
  934. x1,
  935. y1;
  936. while (++j < m) {
  937. point = arc[j], x1 = point[0], y1 = point[1];
  938. if (x1 !== x0 || y1 !== y0) arc[k++] = [x1 - x0, y1 - y0], x0 = x1, y0 = y1;
  939. }
  940. if (k === 1) arc[k++] = [0, 0]; // Each arc must be an array of two or more positions.
  941. arc.length = k;
  942. }
  943. return arcs;
  944. };
  945. // Extracts the lines and rings from the specified hash of geometry objects.
  946. //
  947. // Returns an object with three properties:
  948. //
  949. // * coordinates - shared buffer of [x, y] coordinates
  950. // * lines - lines extracted from the hash, of the form [start, end]
  951. // * rings - rings extracted from the hash, of the form [start, end]
  952. //
  953. // For each ring or line, start and end represent inclusive indexes into the
  954. // coordinates buffer. For rings (and closed lines), coordinates[start] equals
  955. // coordinates[end].
  956. //
  957. // For each line or polygon geometry in the input hash, including nested
  958. // geometries as in geometry collections, the `coordinates` array is replaced
  959. // with an equivalent `arcs` array that, for each line (for line string
  960. // geometries) or ring (for polygon geometries), points to one of the above
  961. // lines or rings.
  962. var extract = function(objects) {
  963. var index = -1,
  964. lines = [],
  965. rings = [],
  966. coordinates = [];
  967. function extractGeometry(geometry) {
  968. if (geometry && extractGeometryType.hasOwnProperty(geometry.type)) extractGeometryType[geometry.type](geometry);
  969. }
  970. var extractGeometryType = {
  971. GeometryCollection: function(o) { o.geometries.forEach(extractGeometry); },
  972. LineString: function(o) { o.arcs = extractLine(o.arcs); },
  973. MultiLineString: function(o) { o.arcs = o.arcs.map(extractLine); },
  974. Polygon: function(o) { o.arcs = o.arcs.map(extractRing); },
  975. MultiPolygon: function(o) { o.arcs = o.arcs.map(extractMultiRing); }
  976. };
  977. function extractLine(line) {
  978. for (var i = 0, n = line.length; i < n; ++i) coordinates[++index] = line[i];
  979. var arc = {0: index - n + 1, 1: index};
  980. lines.push(arc);
  981. return arc;
  982. }
  983. function extractRing(ring) {
  984. for (var i = 0, n = ring.length; i < n; ++i) coordinates[++index] = ring[i];
  985. var arc = {0: index - n + 1, 1: index};
  986. rings.push(arc);
  987. return arc;
  988. }
  989. function extractMultiRing(rings) {
  990. return rings.map(extractRing);
  991. }
  992. for (var key in objects) {
  993. extractGeometry(objects[key]);
  994. }
  995. return {
  996. type: "Topology",
  997. coordinates: coordinates,
  998. lines: lines,
  999. rings: rings,
  1000. objects: objects
  1001. };
  1002. };
  1003. // Given a hash of GeoJSON objects, returns a hash of GeoJSON geometry objects.
  1004. // Any null input geometry objects are represented as {type: null} in the output.
  1005. // Any feature.{id,properties,bbox} are transferred to the output geometry object.
  1006. // Each output geometry object is a shallow copy of the input (e.g., properties, coordinates)!
  1007. var geometry = function(inputs) {
  1008. var outputs = {}, key;
  1009. for (key in inputs) outputs[key] = geomifyObject(inputs[key]);
  1010. return outputs;
  1011. };
  1012. function geomifyObject(input) {
  1013. return input == null ? {type: null}
  1014. : (input.type === "FeatureCollection" ? geomifyFeatureCollection
  1015. : input.type === "Feature" ? geomifyFeature
  1016. : geomifyGeometry)(input);
  1017. }
  1018. function geomifyFeatureCollection(input) {
  1019. var output = {type: "GeometryCollection", geometries: input.features.map(geomifyFeature)};
  1020. if (input.bbox != null) output.bbox = input.bbox;
  1021. return output;
  1022. }
  1023. function geomifyFeature(input) {
  1024. var output = geomifyGeometry(input.geometry), key; // eslint-disable-line no-unused-vars
  1025. if (input.id != null) output.id = input.id;
  1026. if (input.bbox != null) output.bbox = input.bbox;
  1027. for (key in input.properties) { output.properties = input.properties; break; }
  1028. return output;
  1029. }
  1030. function geomifyGeometry(input) {
  1031. if (input == null) return {type: null};
  1032. var output = input.type === "GeometryCollection" ? {type: "GeometryCollection", geometries: input.geometries.map(geomifyGeometry)}
  1033. : input.type === "Point" || input.type === "MultiPoint" ? {type: input.type, coordinates: input.coordinates}
  1034. : {type: input.type, arcs: input.coordinates}; // TODO Check for unknown types?
  1035. if (input.bbox != null) output.bbox = input.bbox;
  1036. return output;
  1037. }
  1038. var prequantize = function(objects, bbox, n) {
  1039. var x0 = bbox[0],
  1040. y0 = bbox[1],
  1041. x1 = bbox[2],
  1042. y1 = bbox[3],
  1043. kx = x1 - x0 ? (n - 1) / (x1 - x0) : 1,
  1044. ky = y1 - y0 ? (n - 1) / (y1 - y0) : 1;
  1045. function quantizePoint(input) {
  1046. return [Math.round((input[0] - x0) * kx), Math.round((input[1] - y0) * ky)];
  1047. }
  1048. function quantizePoints(input, m) {
  1049. var i = -1,
  1050. j = 0,
  1051. n = input.length,
  1052. output = new Array(n), // pessimistic
  1053. pi,
  1054. px,
  1055. py,
  1056. x,
  1057. y;
  1058. while (++i < n) {
  1059. pi = input[i];
  1060. x = Math.round((pi[0] - x0) * kx);
  1061. y = Math.round((pi[1] - y0) * ky);
  1062. if (x !== px || y !== py) output[j++] = [px = x, py = y]; // non-coincident points
  1063. }
  1064. output.length = j;
  1065. while (j < m) j = output.push([output[0][0], output[0][1]]);
  1066. return output;
  1067. }
  1068. function quantizeLine(input) {
  1069. return quantizePoints(input, 2);
  1070. }
  1071. function quantizeRing(input) {
  1072. return quantizePoints(input, 4);
  1073. }
  1074. function quantizePolygon(input) {
  1075. return input.map(quantizeRing);
  1076. }
  1077. function quantizeGeometry(o) {
  1078. if (o != null && quantizeGeometryType.hasOwnProperty(o.type)) quantizeGeometryType[o.type](o);
  1079. }
  1080. var quantizeGeometryType = {
  1081. GeometryCollection: function(o) { o.geometries.forEach(quantizeGeometry); },
  1082. Point: function(o) { o.coordinates = quantizePoint(o.coordinates); },
  1083. MultiPoint: function(o) { o.coordinates = o.coordinates.map(quantizePoint); },
  1084. LineString: function(o) { o.arcs = quantizeLine(o.arcs); },
  1085. MultiLineString: function(o) { o.arcs = o.arcs.map(quantizeLine); },
  1086. Polygon: function(o) { o.arcs = quantizePolygon(o.arcs); },
  1087. MultiPolygon: function(o) { o.arcs = o.arcs.map(quantizePolygon); }
  1088. };
  1089. for (var key in objects) {
  1090. quantizeGeometry(objects[key]);
  1091. }
  1092. return {
  1093. scale: [1 / kx, 1 / ky],
  1094. translate: [x0, y0]
  1095. };
  1096. };
  1097. // Constructs the TopoJSON Topology for the specified hash of features.
  1098. // Each object in the specified hash must be a GeoJSON object,
  1099. // meaning FeatureCollection, a Feature or a geometry object.
  1100. var topology = function(objects, quantization) {
  1101. var bbox = bounds(objects = geometry(objects)),
  1102. transform = quantization > 0 && bbox && prequantize(objects, bbox, quantization),
  1103. topology = dedup(cut(extract(objects))),
  1104. coordinates = topology.coordinates,
  1105. indexByArc = hashmap(topology.arcs.length * 1.4, hashArc, equalArc);
  1106. objects = topology.objects; // for garbage collection
  1107. topology.bbox = bbox;
  1108. topology.arcs = topology.arcs.map(function(arc, i) {
  1109. indexByArc.set(arc, i);
  1110. return coordinates.slice(arc[0], arc[1] + 1);
  1111. });
  1112. delete topology.coordinates;
  1113. coordinates = null;
  1114. function indexGeometry(geometry$$1) {
  1115. if (geometry$$1 && indexGeometryType.hasOwnProperty(geometry$$1.type)) indexGeometryType[geometry$$1.type](geometry$$1);
  1116. }
  1117. var indexGeometryType = {
  1118. GeometryCollection: function(o) { o.geometries.forEach(indexGeometry); },
  1119. LineString: function(o) { o.arcs = indexArcs(o.arcs); },
  1120. MultiLineString: function(o) { o.arcs = o.arcs.map(indexArcs); },
  1121. Polygon: function(o) { o.arcs = o.arcs.map(indexArcs); },
  1122. MultiPolygon: function(o) { o.arcs = o.arcs.map(indexMultiArcs); }
  1123. };
  1124. function indexArcs(arc) {
  1125. var indexes = [];
  1126. do {
  1127. var index = indexByArc.get(arc);
  1128. indexes.push(arc[0] < arc[1] ? index : ~index);
  1129. } while (arc = arc.next);
  1130. return indexes;
  1131. }
  1132. function indexMultiArcs(arcs) {
  1133. return arcs.map(indexArcs);
  1134. }
  1135. for (var key in objects) {
  1136. indexGeometry(objects[key]);
  1137. }
  1138. if (transform) {
  1139. topology.transform = transform;
  1140. topology.arcs = delta(topology.arcs);
  1141. }
  1142. return topology;
  1143. };
  1144. function hashArc(arc) {
  1145. var i = arc[0], j = arc[1], t;
  1146. if (j < i) t = i, i = j, j = t;
  1147. return i + 31 * j;
  1148. }
  1149. function equalArc(arcA, arcB) {
  1150. var ia = arcA[0], ja = arcA[1],
  1151. ib = arcB[0], jb = arcB[1], t;
  1152. if (ja < ia) t = ia, ia = ja, ja = t;
  1153. if (jb < ib) t = ib, ib = jb, jb = t;
  1154. return ia === ib && ja === jb;
  1155. }
  1156. var prune = function(topology) {
  1157. var oldObjects = topology.objects,
  1158. newObjects = {},
  1159. oldArcs = topology.arcs,
  1160. oldArcsLength = oldArcs.length,
  1161. oldIndex = -1,
  1162. newIndexByOldIndex = new Array(oldArcsLength),
  1163. newArcsLength = 0,
  1164. newArcs,
  1165. newIndex = -1,
  1166. key;
  1167. function scanGeometry(input) {
  1168. switch (input.type) {
  1169. case "GeometryCollection": input.geometries.forEach(scanGeometry); break;
  1170. case "LineString": scanArcs(input.arcs); break;
  1171. case "MultiLineString": input.arcs.forEach(scanArcs); break;
  1172. case "Polygon": input.arcs.forEach(scanArcs); break;
  1173. case "MultiPolygon": input.arcs.forEach(scanMultiArcs); break;
  1174. }
  1175. }
  1176. function scanArc(index) {
  1177. if (index < 0) index = ~index;
  1178. if (!newIndexByOldIndex[index]) newIndexByOldIndex[index] = 1, ++newArcsLength;
  1179. }
  1180. function scanArcs(arcs) {
  1181. arcs.forEach(scanArc);
  1182. }
  1183. function scanMultiArcs(arcs) {
  1184. arcs.forEach(scanArcs);
  1185. }
  1186. function reindexGeometry(input) {
  1187. var output;
  1188. switch (input.type) {
  1189. case "GeometryCollection": output = {type: "GeometryCollection", geometries: input.geometries.map(reindexGeometry)}; break;
  1190. case "LineString": output = {type: "LineString", arcs: reindexArcs(input.arcs)}; break;
  1191. case "MultiLineString": output = {type: "MultiLineString", arcs: input.arcs.map(reindexArcs)}; break;
  1192. case "Polygon": output = {type: "Polygon", arcs: input.arcs.map(reindexArcs)}; break;
  1193. case "MultiPolygon": output = {type: "MultiPolygon", arcs: input.arcs.map(reindexMultiArcs)}; break;
  1194. default: return input;
  1195. }
  1196. if (input.id != null) output.id = input.id;
  1197. if (input.bbox != null) output.bbox = input.bbox;
  1198. if (input.properties != null) output.properties = input.properties;
  1199. return output;
  1200. }
  1201. function reindexArc(oldIndex) {
  1202. return oldIndex < 0 ? ~newIndexByOldIndex[~oldIndex] : newIndexByOldIndex[oldIndex];
  1203. }
  1204. function reindexArcs(arcs) {
  1205. return arcs.map(reindexArc);
  1206. }
  1207. function reindexMultiArcs(arcs) {
  1208. return arcs.map(reindexArcs);
  1209. }
  1210. for (key in oldObjects) {
  1211. scanGeometry(oldObjects[key]);
  1212. }
  1213. newArcs = new Array(newArcsLength);
  1214. while (++oldIndex < oldArcsLength) {
  1215. if (newIndexByOldIndex[oldIndex]) {
  1216. newIndexByOldIndex[oldIndex] = ++newIndex;
  1217. newArcs[newIndex] = oldArcs[oldIndex];
  1218. }
  1219. }
  1220. for (key in oldObjects) {
  1221. newObjects[key] = reindexGeometry(oldObjects[key]);
  1222. }
  1223. return {
  1224. type: "Topology",
  1225. bbox: topology.bbox,
  1226. transform: topology.transform,
  1227. objects: newObjects,
  1228. arcs: newArcs
  1229. };
  1230. };
  1231. var filter = function(topology, filter) {
  1232. var oldObjects = topology.objects,
  1233. newObjects = {},
  1234. key;
  1235. if (filter == null) filter = filterTrue;
  1236. function filterGeometry(input) {
  1237. var output, arcs;
  1238. switch (input.type) {
  1239. case "Polygon": {
  1240. arcs = filterRings(input.arcs);
  1241. output = arcs ? {type: "Polygon", arcs: arcs} : {type: null};
  1242. break;
  1243. }
  1244. case "MultiPolygon": {
  1245. arcs = input.arcs.map(filterRings).filter(filterIdentity);
  1246. output = arcs.length ? {type: "MultiPolygon", arcs: arcs} : {type: null};
  1247. break;
  1248. }
  1249. case "GeometryCollection": {
  1250. arcs = input.geometries.map(filterGeometry).filter(filterNotNull);
  1251. output = arcs.length ? {type: "GeometryCollection", geometries: arcs} : {type: null};
  1252. break;
  1253. }
  1254. default: return input;
  1255. }
  1256. if (input.id != null) output.id = input.id;
  1257. if (input.bbox != null) output.bbox = input.bbox;
  1258. if (input.properties != null) output.properties = input.properties;
  1259. return output;
  1260. }
  1261. function filterRings(arcs) {
  1262. return arcs.length && filterExteriorRing(arcs[0]) // if the exterior is small, ignore any holes
  1263. ? [arcs[0]].concat(arcs.slice(1).filter(filterInteriorRing))
  1264. : null;
  1265. }
  1266. function filterExteriorRing(ring) {
  1267. return filter(ring, false);
  1268. }
  1269. function filterInteriorRing(ring) {
  1270. return filter(ring, true);
  1271. }
  1272. for (key in oldObjects) {
  1273. newObjects[key] = filterGeometry(oldObjects[key]);
  1274. }
  1275. return prune({
  1276. type: "Topology",
  1277. bbox: topology.bbox,
  1278. transform: topology.transform,
  1279. objects: newObjects,
  1280. arcs: topology.arcs
  1281. });
  1282. };
  1283. function filterTrue() {
  1284. return true;
  1285. }
  1286. function filterIdentity(x) {
  1287. return x;
  1288. }
  1289. function filterNotNull(geometry) {
  1290. return geometry.type != null;
  1291. }
  1292. var filterAttached = function(topology) {
  1293. var ownerByArc = new Array(topology.arcs.length), // arc index -> index of unique associated ring, or -1 if used by multiple rings
  1294. ownerIndex = 0,
  1295. key;
  1296. function testGeometry(o) {
  1297. switch (o.type) {
  1298. case "GeometryCollection": o.geometries.forEach(testGeometry); break;
  1299. case "Polygon": testArcs(o.arcs); break;
  1300. case "MultiPolygon": o.arcs.forEach(testArcs); break;
  1301. }
  1302. }
  1303. function testArcs(arcs) {
  1304. for (var i = 0, n = arcs.length; i < n; ++i, ++ownerIndex) {
  1305. for (var ring = arcs[i], j = 0, m = ring.length; j < m; ++j) {
  1306. var arc = ring[j];
  1307. if (arc < 0) arc = ~arc;
  1308. var owner = ownerByArc[arc];
  1309. if (owner == null) ownerByArc[arc] = ownerIndex;
  1310. else if (owner !== ownerIndex) ownerByArc[arc] = -1;
  1311. }
  1312. }
  1313. }
  1314. for (key in topology.objects) {
  1315. testGeometry(topology.objects[key]);
  1316. }
  1317. return function(ring) {
  1318. for (var j = 0, m = ring.length, arc; j < m; ++j) {
  1319. if (ownerByArc[(arc = ring[j]) < 0 ? ~arc : arc] === -1) {
  1320. return true;
  1321. }
  1322. }
  1323. return false;
  1324. };
  1325. };
  1326. function planarTriangleArea(triangle) {
  1327. var a = triangle[0], b = triangle[1], c = triangle[2];
  1328. return Math.abs((a[0] - c[0]) * (b[1] - a[1]) - (a[0] - b[0]) * (c[1] - a[1])) / 2;
  1329. }
  1330. function planarRingArea$1(ring) {
  1331. var i = -1, n = ring.length, a, b = ring[n - 1], area = 0;
  1332. while (++i < n) a = b, b = ring[i], area += a[0] * b[1] - a[1] * b[0];
  1333. return Math.abs(area) / 2;
  1334. }
  1335. var filterWeight = function(topology, minWeight, weight) {
  1336. minWeight = minWeight == null ? Number.MIN_VALUE : +minWeight;
  1337. if (weight == null) weight = planarRingArea$1;
  1338. return function(ring, interior) {
  1339. return weight(feature(topology, {type: "Polygon", arcs: [ring]}).geometry.coordinates[0], interior) >= minWeight;
  1340. };
  1341. };
  1342. var filterAttachedWeight = function(topology, minWeight, weight) {
  1343. var a = filterAttached(topology),
  1344. w = filterWeight(topology, minWeight, weight);
  1345. return function(ring, interior) {
  1346. return a(ring, interior) || w(ring, interior);
  1347. };
  1348. };
  1349. function compare(a, b) {
  1350. return a[1][2] - b[1][2];
  1351. }
  1352. var newHeap = function() {
  1353. var heap = {},
  1354. array = [],
  1355. size = 0;
  1356. heap.push = function(object) {
  1357. up(array[object._ = size] = object, size++);
  1358. return size;
  1359. };
  1360. heap.pop = function() {
  1361. if (size <= 0) return;
  1362. var removed = array[0], object;
  1363. if (--size > 0) object = array[size], down(array[object._ = 0] = object, 0);
  1364. return removed;
  1365. };
  1366. heap.remove = function(removed) {
  1367. var i = removed._, object;
  1368. if (array[i] !== removed) return; // invalid request
  1369. if (i !== --size) object = array[size], (compare(object, removed) < 0 ? up : down)(array[object._ = i] = object, i);
  1370. return i;
  1371. };
  1372. function up(object, i) {
  1373. while (i > 0) {
  1374. var j = ((i + 1) >> 1) - 1,
  1375. parent = array[j];
  1376. if (compare(object, parent) >= 0) break;
  1377. array[parent._ = i] = parent;
  1378. array[object._ = i = j] = object;
  1379. }
  1380. }
  1381. function down(object, i) {
  1382. while (true) {
  1383. var r = (i + 1) << 1,
  1384. l = r - 1,
  1385. j = i,
  1386. child = array[j];
  1387. if (l < size && compare(array[l], child) < 0) child = array[j = l];
  1388. if (r < size && compare(array[r], child) < 0) child = array[j = r];
  1389. if (j === i) break;
  1390. array[child._ = i] = child;
  1391. array[object._ = i = j] = object;
  1392. }
  1393. }
  1394. return heap;
  1395. };
  1396. function copy(point) {
  1397. return [point[0], point[1], 0];
  1398. }
  1399. var presimplify = function(topology, weight) {
  1400. var point = topology.transform ? transform(topology.transform) : copy,
  1401. heap = newHeap();
  1402. if (weight == null) weight = planarTriangleArea;
  1403. var arcs = topology.arcs.map(function(arc) {
  1404. var triangles = [],
  1405. maxWeight = 0,
  1406. triangle,
  1407. i,
  1408. n;
  1409. arc = arc.map(point);
  1410. for (i = 1, n = arc.length - 1; i < n; ++i) {
  1411. triangle = [arc[i - 1], arc[i], arc[i + 1]];
  1412. triangle[1][2] = weight(triangle);
  1413. triangles.push(triangle);
  1414. heap.push(triangle);
  1415. }
  1416. // Always keep the arc endpoints!
  1417. arc[0][2] = arc[n][2] = Infinity;
  1418. for (i = 0, n = triangles.length; i < n; ++i) {
  1419. triangle = triangles[i];
  1420. triangle.previous = triangles[i - 1];
  1421. triangle.next = triangles[i + 1];
  1422. }
  1423. while (triangle = heap.pop()) {
  1424. var previous = triangle.previous,
  1425. next = triangle.next;
  1426. // If the weight of the current point is less than that of the previous
  1427. // point to be eliminated, use the latter’s weight instead. This ensures
  1428. // that the current point cannot be eliminated without eliminating
  1429. // previously- eliminated points.
  1430. if (triangle[1][2] < maxWeight) triangle[1][2] = maxWeight;
  1431. else maxWeight = triangle[1][2];
  1432. if (previous) {
  1433. previous.next = next;
  1434. previous[2] = triangle[2];
  1435. update(previous);
  1436. }
  1437. if (next) {
  1438. next.previous = previous;
  1439. next[0] = triangle[0];
  1440. update(next);
  1441. }
  1442. }
  1443. return arc;
  1444. });
  1445. function update(triangle) {
  1446. heap.remove(triangle);
  1447. triangle[1][2] = weight(triangle);
  1448. heap.push(triangle);
  1449. }
  1450. return {
  1451. type: "Topology",
  1452. bbox: topology.bbox,
  1453. objects: topology.objects,
  1454. arcs: arcs
  1455. };
  1456. };
  1457. var quantile = function(topology, p) {
  1458. var array = [];
  1459. topology.arcs.forEach(function(arc) {
  1460. arc.forEach(function(point) {
  1461. if (isFinite(point[2])) { // Ignore endpoints, whose weight is Infinity.
  1462. array.push(point[2]);
  1463. }
  1464. });
  1465. });
  1466. return array.length && quantile$1(array.sort(descending), p);
  1467. };
  1468. function quantile$1(array, p) {
  1469. if (!(n = array.length)) return;
  1470. if ((p = +p) <= 0 || n < 2) return array[0];
  1471. if (p >= 1) return array[n - 1];
  1472. var n,
  1473. h = (n - 1) * p,
  1474. i = Math.floor(h),
  1475. a = array[i],
  1476. b = array[i + 1];
  1477. return a + (b - a) * (h - i);
  1478. }
  1479. function descending(a, b) {
  1480. return b - a;
  1481. }
  1482. var simplify = function(topology, minWeight) {
  1483. minWeight = minWeight == null ? Number.MIN_VALUE : +minWeight;
  1484. // Remove points whose weight is less than the minimum weight.
  1485. var arcs = topology.arcs.map(function(input) {
  1486. var i = -1,
  1487. j = 0,
  1488. n = input.length,
  1489. output = new Array(n), // pessimistic
  1490. point;
  1491. while (++i < n) {
  1492. if ((point = input[i])[2] >= minWeight) {
  1493. output[j++] = [point[0], point[1]];
  1494. }
  1495. }
  1496. output.length = j;
  1497. return output;
  1498. });
  1499. return {
  1500. type: "Topology",
  1501. transform: topology.transform,
  1502. bbox: topology.bbox,
  1503. objects: topology.objects,
  1504. arcs: arcs
  1505. };
  1506. };
  1507. var pi = Math.PI;
  1508. var tau = 2 * pi;
  1509. var quarterPi = pi / 4;
  1510. var radians = pi / 180;
  1511. var abs = Math.abs;
  1512. var atan2 = Math.atan2;
  1513. var cos = Math.cos;
  1514. var sin = Math.sin;
  1515. function halfArea(ring, closed) {
  1516. var i = 0,
  1517. n = ring.length,
  1518. sum = 0,
  1519. point = ring[closed ? i++ : n - 1],
  1520. lambda0, lambda1 = point[0] * radians,
  1521. phi1 = (point[1] * radians) / 2 + quarterPi,
  1522. cosPhi0, cosPhi1 = cos(phi1),
  1523. sinPhi0, sinPhi1 = sin(phi1);
  1524. for (; i < n; ++i) {
  1525. point = ring[i];
  1526. lambda0 = lambda1, lambda1 = point[0] * radians;
  1527. phi1 = (point[1] * radians) / 2 + quarterPi;
  1528. cosPhi0 = cosPhi1, cosPhi1 = cos(phi1);
  1529. sinPhi0 = sinPhi1, sinPhi1 = sin(phi1);
  1530. // Spherical excess E for a spherical triangle with vertices: south pole,
  1531. // previous point, current point. Uses a formula derived from Cagnoli’s
  1532. // theorem. See Todhunter, Spherical Trig. (1871), Sec. 103, Eq. (2).
  1533. // See https://github.com/d3/d3-geo/blob/master/README.md#geoArea
  1534. var dLambda = lambda1 - lambda0,
  1535. sdLambda = dLambda >= 0 ? 1 : -1,
  1536. adLambda = sdLambda * dLambda,
  1537. k = sinPhi0 * sinPhi1,
  1538. u = cosPhi0 * cosPhi1 + k * cos(adLambda),
  1539. v = k * sdLambda * sin(adLambda);
  1540. sum += atan2(v, u);
  1541. }
  1542. return sum;
  1543. }
  1544. function sphericalRingArea(ring, interior) {
  1545. var sum = halfArea(ring, true);
  1546. if (interior) sum *= -1;
  1547. return (sum < 0 ? tau + sum : sum) * 2;
  1548. }
  1549. function sphericalTriangleArea(t) {
  1550. return abs(halfArea(t, false)) * 2;
  1551. }
  1552. exports.bbox = bbox;
  1553. exports.feature = feature;
  1554. exports.mesh = mesh;
  1555. exports.meshArcs = meshArcs;
  1556. exports.merge = merge;
  1557. exports.mergeArcs = mergeArcs;
  1558. exports.neighbors = neighbors;
  1559. exports.quantize = quantize;
  1560. exports.transform = transform;
  1561. exports.untransform = untransform;
  1562. exports.topology = topology;
  1563. exports.filter = filter;
  1564. exports.filterAttached = filterAttached;
  1565. exports.filterAttachedWeight = filterAttachedWeight;
  1566. exports.filterWeight = filterWeight;
  1567. exports.planarRingArea = planarRingArea$1;
  1568. exports.planarTriangleArea = planarTriangleArea;
  1569. exports.presimplify = presimplify;
  1570. exports.quantile = quantile;
  1571. exports.simplify = simplify;
  1572. exports.sphericalRingArea = sphericalRingArea;
  1573. exports.sphericalTriangleArea = sphericalTriangleArea;
  1574. Object.defineProperty(exports, '__esModule', { value: true });
  1575. })));
  1576. export default tmp.topojson;