Daniel@0: !function() {
Daniel@0:   var topojson = {
Daniel@0:     version: "1.6.19",
Daniel@0:     mesh: function(topology) { return object(topology, meshArcs.apply(this, arguments)); },
Daniel@0:     meshArcs: meshArcs,
Daniel@0:     merge: function(topology) { return object(topology, mergeArcs.apply(this, arguments)); },
Daniel@0:     mergeArcs: mergeArcs,
Daniel@0:     feature: featureOrCollection,
Daniel@0:     neighbors: neighbors,
Daniel@0:     presimplify: presimplify
Daniel@0:   };
Daniel@0: 
Daniel@0:   function stitchArcs(topology, arcs) {
Daniel@0:     var stitchedArcs = {},
Daniel@0:         fragmentByStart = {},
Daniel@0:         fragmentByEnd = {},
Daniel@0:         fragments = [],
Daniel@0:         emptyIndex = -1;
Daniel@0: 
Daniel@0:     // Stitch empty arcs first, since they may be subsumed by other arcs.
Daniel@0:     arcs.forEach(function(i, j) {
Daniel@0:       var arc = topology.arcs[i < 0 ? ~i : i], t;
Daniel@0:       if (arc.length < 3 && !arc[1][0] && !arc[1][1]) {
Daniel@0:         t = arcs[++emptyIndex], arcs[emptyIndex] = i, arcs[j] = t;
Daniel@0:       }
Daniel@0:     });
Daniel@0: 
Daniel@0:     arcs.forEach(function(i) {
Daniel@0:       var e = ends(i),
Daniel@0:           start = e[0],
Daniel@0:           end = e[1],
Daniel@0:           f, g;
Daniel@0: 
Daniel@0:       if (f = fragmentByEnd[start]) {
Daniel@0:         delete fragmentByEnd[f.end];
Daniel@0:         f.push(i);
Daniel@0:         f.end = end;
Daniel@0:         if (g = fragmentByStart[end]) {
Daniel@0:           delete fragmentByStart[g.start];
Daniel@0:           var fg = g === f ? f : f.concat(g);
Daniel@0:           fragmentByStart[fg.start = f.start] = fragmentByEnd[fg.end = g.end] = fg;
Daniel@0:         } else {
Daniel@0:           fragmentByStart[f.start] = fragmentByEnd[f.end] = f;
Daniel@0:         }
Daniel@0:       } else if (f = fragmentByStart[end]) {
Daniel@0:         delete fragmentByStart[f.start];
Daniel@0:         f.unshift(i);
Daniel@0:         f.start = start;
Daniel@0:         if (g = fragmentByEnd[start]) {
Daniel@0:           delete fragmentByEnd[g.end];
Daniel@0:           var gf = g === f ? f : g.concat(f);
Daniel@0:           fragmentByStart[gf.start = g.start] = fragmentByEnd[gf.end = f.end] = gf;
Daniel@0:         } else {
Daniel@0:           fragmentByStart[f.start] = fragmentByEnd[f.end] = f;
Daniel@0:         }
Daniel@0:       } else {
Daniel@0:         f = [i];
Daniel@0:         fragmentByStart[f.start = start] = fragmentByEnd[f.end = end] = f;
Daniel@0:       }
Daniel@0:     });
Daniel@0: 
Daniel@0:     function ends(i) {
Daniel@0:       var arc = topology.arcs[i < 0 ? ~i : i], p0 = arc[0], p1;
Daniel@0:       if (topology.transform) p1 = [0, 0], arc.forEach(function(dp) { p1[0] += dp[0], p1[1] += dp[1]; });
Daniel@0:       else p1 = arc[arc.length - 1];
Daniel@0:       return i < 0 ? [p1, p0] : [p0, p1];
Daniel@0:     }
Daniel@0: 
Daniel@0:     function flush(fragmentByEnd, fragmentByStart) {
Daniel@0:       for (var k in fragmentByEnd) {
Daniel@0:         var f = fragmentByEnd[k];
Daniel@0:         delete fragmentByStart[f.start];
Daniel@0:         delete f.start;
Daniel@0:         delete f.end;
Daniel@0:         f.forEach(function(i) { stitchedArcs[i < 0 ? ~i : i] = 1; });
Daniel@0:         fragments.push(f);
Daniel@0:       }
Daniel@0:     }
Daniel@0: 
Daniel@0:     flush(fragmentByEnd, fragmentByStart);
Daniel@0:     flush(fragmentByStart, fragmentByEnd);
Daniel@0:     arcs.forEach(function(i) { if (!stitchedArcs[i < 0 ? ~i : i]) fragments.push([i]); });
Daniel@0: 
Daniel@0:     return fragments;
Daniel@0:   }
Daniel@0: 
Daniel@0:   function meshArcs(topology, o, filter) {
Daniel@0:     var arcs = [];
Daniel@0: 
Daniel@0:     if (arguments.length > 1) {
Daniel@0:       var geomsByArc = [],
Daniel@0:           geom;
Daniel@0: 
Daniel@0:       function arc(i) {
Daniel@0:         var j = i < 0 ? ~i : i;
Daniel@0:         (geomsByArc[j] || (geomsByArc[j] = [])).push({i: i, g: geom});
Daniel@0:       }
Daniel@0: 
Daniel@0:       function line(arcs) {
Daniel@0:         arcs.forEach(arc);
Daniel@0:       }
Daniel@0: 
Daniel@0:       function polygon(arcs) {
Daniel@0:         arcs.forEach(line);
Daniel@0:       }
Daniel@0: 
Daniel@0:       function geometry(o) {
Daniel@0:         if (o.type === "GeometryCollection") o.geometries.forEach(geometry);
Daniel@0:         else if (o.type in geometryType) geom = o, geometryType[o.type](o.arcs);
Daniel@0:       }
Daniel@0: 
Daniel@0:       var geometryType = {
Daniel@0:         LineString: line,
Daniel@0:         MultiLineString: polygon,
Daniel@0:         Polygon: polygon,
Daniel@0:         MultiPolygon: function(arcs) { arcs.forEach(polygon); }
Daniel@0:       };
Daniel@0: 
Daniel@0:       geometry(o);
Daniel@0: 
Daniel@0:       geomsByArc.forEach(arguments.length < 3
Daniel@0:           ? function(geoms) { arcs.push(geoms[0].i); }
Daniel@0:           : function(geoms) { if (filter(geoms[0].g, geoms[geoms.length - 1].g)) arcs.push(geoms[0].i); });
Daniel@0:     } else {
Daniel@0:       for (var i = 0, n = topology.arcs.length; i < n; ++i) arcs.push(i);
Daniel@0:     }
Daniel@0: 
Daniel@0:     return {type: "MultiLineString", arcs: stitchArcs(topology, arcs)};
Daniel@0:   }
Daniel@0: 
Daniel@0:   function mergeArcs(topology, objects) {
Daniel@0:     var polygonsByArc = {},
Daniel@0:         polygons = [],
Daniel@0:         components = [];
Daniel@0: 
Daniel@0:     objects.forEach(function(o) {
Daniel@0:       if (o.type === "Polygon") register(o.arcs);
Daniel@0:       else if (o.type === "MultiPolygon") o.arcs.forEach(register);
Daniel@0:     });
Daniel@0: 
Daniel@0:     function register(polygon) {
Daniel@0:       polygon.forEach(function(ring) {
Daniel@0:         ring.forEach(function(arc) {
Daniel@0:           (polygonsByArc[arc = arc < 0 ? ~arc : arc] || (polygonsByArc[arc] = [])).push(polygon);
Daniel@0:         });
Daniel@0:       });
Daniel@0:       polygons.push(polygon);
Daniel@0:     }
Daniel@0: 
Daniel@0:     function exterior(ring) {
Daniel@0:       return cartesianRingArea(object(topology, {type: "Polygon", arcs: [ring]}).coordinates[0]) > 0; // TODO allow spherical?
Daniel@0:     }
Daniel@0: 
Daniel@0:     polygons.forEach(function(polygon) {
Daniel@0:       if (!polygon._) {
Daniel@0:         var component = [],
Daniel@0:             neighbors = [polygon];
Daniel@0:         polygon._ = 1;
Daniel@0:         components.push(component);
Daniel@0:         while (polygon = neighbors.pop()) {
Daniel@0:           component.push(polygon);
Daniel@0:           polygon.forEach(function(ring) {
Daniel@0:             ring.forEach(function(arc) {
Daniel@0:               polygonsByArc[arc < 0 ? ~arc : arc].forEach(function(polygon) {
Daniel@0:                 if (!polygon._) {
Daniel@0:                   polygon._ = 1;
Daniel@0:                   neighbors.push(polygon);
Daniel@0:                 }
Daniel@0:               });
Daniel@0:             });
Daniel@0:           });
Daniel@0:         }
Daniel@0:       }
Daniel@0:     });
Daniel@0: 
Daniel@0:     polygons.forEach(function(polygon) {
Daniel@0:       delete polygon._;
Daniel@0:     });
Daniel@0: 
Daniel@0:     return {
Daniel@0:       type: "MultiPolygon",
Daniel@0:       arcs: components.map(function(polygons) {
Daniel@0:         var arcs = [];
Daniel@0: 
Daniel@0:         // Extract the exterior (unique) arcs.
Daniel@0:         polygons.forEach(function(polygon) {
Daniel@0:           polygon.forEach(function(ring) {
Daniel@0:             ring.forEach(function(arc) {
Daniel@0:               if (polygonsByArc[arc < 0 ? ~arc : arc].length < 2) {
Daniel@0:                 arcs.push(arc);
Daniel@0:               }
Daniel@0:             });
Daniel@0:           });
Daniel@0:         });
Daniel@0: 
Daniel@0:         // Stitch the arcs into one or more rings.
Daniel@0:         arcs = stitchArcs(topology, arcs);
Daniel@0: 
Daniel@0:         // If more than one ring is returned,
Daniel@0:         // at most one of these rings can be the exterior;
Daniel@0:         // this exterior ring has the same winding order
Daniel@0:         // as any exterior ring in the original polygons.
Daniel@0:         if ((n = arcs.length) > 1) {
Daniel@0:           var sgn = exterior(polygons[0][0]);
Daniel@0:           for (var i = 0, t; i < n; ++i) {
Daniel@0:             if (sgn === exterior(arcs[i])) {
Daniel@0:               t = arcs[0], arcs[0] = arcs[i], arcs[i] = t;
Daniel@0:               break;
Daniel@0:             }
Daniel@0:           }
Daniel@0:         }
Daniel@0: 
Daniel@0:         return arcs;
Daniel@0:       })
Daniel@0:     };
Daniel@0:   }
Daniel@0: 
Daniel@0:   function featureOrCollection(topology, o) {
Daniel@0:     return o.type === "GeometryCollection" ? {
Daniel@0:       type: "FeatureCollection",
Daniel@0:       features: o.geometries.map(function(o) { return feature(topology, o); })
Daniel@0:     } : feature(topology, o);
Daniel@0:   }
Daniel@0: 
Daniel@0:   function feature(topology, o) {
Daniel@0:     var f = {
Daniel@0:       type: "Feature",
Daniel@0:       id: o.id,
Daniel@0:       properties: o.properties || {},
Daniel@0:       geometry: object(topology, o)
Daniel@0:     };
Daniel@0:     if (o.id == null) delete f.id;
Daniel@0:     return f;
Daniel@0:   }
Daniel@0: 
Daniel@0:   function object(topology, o) {
Daniel@0:     var absolute = transformAbsolute(topology.transform),
Daniel@0:         arcs = topology.arcs;
Daniel@0: 
Daniel@0:     function arc(i, points) {
Daniel@0:       if (points.length) points.pop();
Daniel@0:       for (var a = arcs[i < 0 ? ~i : i], k = 0, n = a.length, p; k < n; ++k) {
Daniel@0:         points.push(p = a[k].slice());
Daniel@0:         absolute(p, k);
Daniel@0:       }
Daniel@0:       if (i < 0) reverse(points, n);
Daniel@0:     }
Daniel@0: 
Daniel@0:     function point(p) {
Daniel@0:       p = p.slice();
Daniel@0:       absolute(p, 0);
Daniel@0:       return p;
Daniel@0:     }
Daniel@0: 
Daniel@0:     function line(arcs) {
Daniel@0:       var points = [];
Daniel@0:       for (var i = 0, n = arcs.length; i < n; ++i) arc(arcs[i], points);
Daniel@0:       if (points.length < 2) points.push(points[0].slice());
Daniel@0:       return points;
Daniel@0:     }
Daniel@0: 
Daniel@0:     function ring(arcs) {
Daniel@0:       var points = line(arcs);
Daniel@0:       while (points.length < 4) points.push(points[0].slice());
Daniel@0:       return points;
Daniel@0:     }
Daniel@0: 
Daniel@0:     function polygon(arcs) {
Daniel@0:       return arcs.map(ring);
Daniel@0:     }
Daniel@0: 
Daniel@0:     function geometry(o) {
Daniel@0:       var t = o.type;
Daniel@0:       return t === "GeometryCollection" ? {type: t, geometries: o.geometries.map(geometry)}
Daniel@0:           : t in geometryType ? {type: t, coordinates: geometryType[t](o)}
Daniel@0:           : null;
Daniel@0:     }
Daniel@0: 
Daniel@0:     var geometryType = {
Daniel@0:       Point: function(o) { return point(o.coordinates); },
Daniel@0:       MultiPoint: function(o) { return o.coordinates.map(point); },
Daniel@0:       LineString: function(o) { return line(o.arcs); },
Daniel@0:       MultiLineString: function(o) { return o.arcs.map(line); },
Daniel@0:       Polygon: function(o) { return polygon(o.arcs); },
Daniel@0:       MultiPolygon: function(o) { return o.arcs.map(polygon); }
Daniel@0:     };
Daniel@0: 
Daniel@0:     return geometry(o);
Daniel@0:   }
Daniel@0: 
Daniel@0:   function reverse(array, n) {
Daniel@0:     var t, j = array.length, i = j - n; while (i < --j) t = array[i], array[i++] = array[j], array[j] = t;
Daniel@0:   }
Daniel@0: 
Daniel@0:   function bisect(a, x) {
Daniel@0:     var lo = 0, hi = a.length;
Daniel@0:     while (lo < hi) {
Daniel@0:       var mid = lo + hi >>> 1;
Daniel@0:       if (a[mid] < x) lo = mid + 1;
Daniel@0:       else hi = mid;
Daniel@0:     }
Daniel@0:     return lo;
Daniel@0:   }
Daniel@0: 
Daniel@0:   function neighbors(objects) {
Daniel@0:     var indexesByArc = {}, // arc index -> array of object indexes
Daniel@0:         neighbors = objects.map(function() { return []; });
Daniel@0: 
Daniel@0:     function line(arcs, i) {
Daniel@0:       arcs.forEach(function(a) {
Daniel@0:         if (a < 0) a = ~a;
Daniel@0:         var o = indexesByArc[a];
Daniel@0:         if (o) o.push(i);
Daniel@0:         else indexesByArc[a] = [i];
Daniel@0:       });
Daniel@0:     }
Daniel@0: 
Daniel@0:     function polygon(arcs, i) {
Daniel@0:       arcs.forEach(function(arc) { line(arc, i); });
Daniel@0:     }
Daniel@0: 
Daniel@0:     function geometry(o, i) {
Daniel@0:       if (o.type === "GeometryCollection") o.geometries.forEach(function(o) { geometry(o, i); });
Daniel@0:       else if (o.type in geometryType) geometryType[o.type](o.arcs, i);
Daniel@0:     }
Daniel@0: 
Daniel@0:     var geometryType = {
Daniel@0:       LineString: line,
Daniel@0:       MultiLineString: polygon,
Daniel@0:       Polygon: polygon,
Daniel@0:       MultiPolygon: function(arcs, i) { arcs.forEach(function(arc) { polygon(arc, i); }); }
Daniel@0:     };
Daniel@0: 
Daniel@0:     objects.forEach(geometry);
Daniel@0: 
Daniel@0:     for (var i in indexesByArc) {
Daniel@0:       for (var indexes = indexesByArc[i], m = indexes.length, j = 0; j < m; ++j) {
Daniel@0:         for (var k = j + 1; k < m; ++k) {
Daniel@0:           var ij = indexes[j], ik = indexes[k], n;
Daniel@0:           if ((n = neighbors[ij])[i = bisect(n, ik)] !== ik) n.splice(i, 0, ik);
Daniel@0:           if ((n = neighbors[ik])[i = bisect(n, ij)] !== ij) n.splice(i, 0, ij);
Daniel@0:         }
Daniel@0:       }
Daniel@0:     }
Daniel@0: 
Daniel@0:     return neighbors;
Daniel@0:   }
Daniel@0: 
Daniel@0:   function presimplify(topology, triangleArea) {
Daniel@0:     var absolute = transformAbsolute(topology.transform),
Daniel@0:         relative = transformRelative(topology.transform),
Daniel@0:         heap = minAreaHeap();
Daniel@0: 
Daniel@0:     if (!triangleArea) triangleArea = cartesianTriangleArea;
Daniel@0: 
Daniel@0:     topology.arcs.forEach(function(arc) {
Daniel@0:       var triangles = [],
Daniel@0:           maxArea = 0,
Daniel@0:           triangle;
Daniel@0: 
Daniel@0:       // To store each point’s effective area, we create a new array rather than
Daniel@0:       // extending the passed-in point to workaround a Chrome/V8 bug (getting
Daniel@0:       // stuck in smi mode). For midpoints, the initial effective area of
Daniel@0:       // Infinity will be computed in the next step.
Daniel@0:       for (var i = 0, n = arc.length, p; i < n; ++i) {
Daniel@0:         p = arc[i];
Daniel@0:         absolute(arc[i] = [p[0], p[1], Infinity], i);
Daniel@0:       }
Daniel@0: 
Daniel@0:       for (var i = 1, n = arc.length - 1; i < n; ++i) {
Daniel@0:         triangle = arc.slice(i - 1, i + 2);
Daniel@0:         triangle[1][2] = triangleArea(triangle);
Daniel@0:         triangles.push(triangle);
Daniel@0:         heap.push(triangle);
Daniel@0:       }
Daniel@0: 
Daniel@0:       for (var i = 0, n = triangles.length; i < n; ++i) {
Daniel@0:         triangle = triangles[i];
Daniel@0:         triangle.previous = triangles[i - 1];
Daniel@0:         triangle.next = triangles[i + 1];
Daniel@0:       }
Daniel@0: 
Daniel@0:       while (triangle = heap.pop()) {
Daniel@0:         var previous = triangle.previous,
Daniel@0:             next = triangle.next;
Daniel@0: 
Daniel@0:         // If the area of the current point is less than that of the previous point
Daniel@0:         // to be eliminated, use the latter's area instead. This ensures that the
Daniel@0:         // current point cannot be eliminated without eliminating previously-
Daniel@0:         // eliminated points.
Daniel@0:         if (triangle[1][2] < maxArea) triangle[1][2] = maxArea;
Daniel@0:         else maxArea = triangle[1][2];
Daniel@0: 
Daniel@0:         if (previous) {
Daniel@0:           previous.next = next;
Daniel@0:           previous[2] = triangle[2];
Daniel@0:           update(previous);
Daniel@0:         }
Daniel@0: 
Daniel@0:         if (next) {
Daniel@0:           next.previous = previous;
Daniel@0:           next[0] = triangle[0];
Daniel@0:           update(next);
Daniel@0:         }
Daniel@0:       }
Daniel@0: 
Daniel@0:       arc.forEach(relative);
Daniel@0:     });
Daniel@0: 
Daniel@0:     function update(triangle) {
Daniel@0:       heap.remove(triangle);
Daniel@0:       triangle[1][2] = triangleArea(triangle);
Daniel@0:       heap.push(triangle);
Daniel@0:     }
Daniel@0: 
Daniel@0:     return topology;
Daniel@0:   };
Daniel@0: 
Daniel@0:   function cartesianRingArea(ring) {
Daniel@0:     var i = -1,
Daniel@0:         n = ring.length,
Daniel@0:         a,
Daniel@0:         b = ring[n - 1],
Daniel@0:         area = 0;
Daniel@0: 
Daniel@0:     while (++i < n) {
Daniel@0:       a = b;
Daniel@0:       b = ring[i];
Daniel@0:       area += a[0] * b[1] - a[1] * b[0];
Daniel@0:     }
Daniel@0: 
Daniel@0:     return area * .5;
Daniel@0:   }
Daniel@0: 
Daniel@0:   function cartesianTriangleArea(triangle) {
Daniel@0:     var a = triangle[0], b = triangle[1], c = triangle[2];
Daniel@0:     return Math.abs((a[0] - c[0]) * (b[1] - a[1]) - (a[0] - b[0]) * (c[1] - a[1]));
Daniel@0:   }
Daniel@0: 
Daniel@0:   function compareArea(a, b) {
Daniel@0:     return a[1][2] - b[1][2];
Daniel@0:   }
Daniel@0: 
Daniel@0:   function minAreaHeap() {
Daniel@0:     var heap = {},
Daniel@0:         array = [],
Daniel@0:         size = 0;
Daniel@0: 
Daniel@0:     heap.push = function(object) {
Daniel@0:       up(array[object._ = size] = object, size++);
Daniel@0:       return size;
Daniel@0:     };
Daniel@0: 
Daniel@0:     heap.pop = function() {
Daniel@0:       if (size <= 0) return;
Daniel@0:       var removed = array[0], object;
Daniel@0:       if (--size > 0) object = array[size], down(array[object._ = 0] = object, 0);
Daniel@0:       return removed;
Daniel@0:     };
Daniel@0: 
Daniel@0:     heap.remove = function(removed) {
Daniel@0:       var i = removed._, object;
Daniel@0:       if (array[i] !== removed) return; // invalid request
Daniel@0:       if (i !== --size) object = array[size], (compareArea(object, removed) < 0 ? up : down)(array[object._ = i] = object, i);
Daniel@0:       return i;
Daniel@0:     };
Daniel@0: 
Daniel@0:     function up(object, i) {
Daniel@0:       while (i > 0) {
Daniel@0:         var j = ((i + 1) >> 1) - 1,
Daniel@0:             parent = array[j];
Daniel@0:         if (compareArea(object, parent) >= 0) break;
Daniel@0:         array[parent._ = i] = parent;
Daniel@0:         array[object._ = i = j] = object;
Daniel@0:       }
Daniel@0:     }
Daniel@0: 
Daniel@0:     function down(object, i) {
Daniel@0:       while (true) {
Daniel@0:         var r = (i + 1) << 1,
Daniel@0:             l = r - 1,
Daniel@0:             j = i,
Daniel@0:             child = array[j];
Daniel@0:         if (l < size && compareArea(array[l], child) < 0) child = array[j = l];
Daniel@0:         if (r < size && compareArea(array[r], child) < 0) child = array[j = r];
Daniel@0:         if (j === i) break;
Daniel@0:         array[child._ = i] = child;
Daniel@0:         array[object._ = i = j] = object;
Daniel@0:       }
Daniel@0:     }
Daniel@0: 
Daniel@0:     return heap;
Daniel@0:   }
Daniel@0: 
Daniel@0:   function transformAbsolute(transform) {
Daniel@0:     if (!transform) return noop;
Daniel@0:     var x0,
Daniel@0:         y0,
Daniel@0:         kx = transform.scale[0],
Daniel@0:         ky = transform.scale[1],
Daniel@0:         dx = transform.translate[0],
Daniel@0:         dy = transform.translate[1];
Daniel@0:     return function(point, i) {
Daniel@0:       if (!i) x0 = y0 = 0;
Daniel@0:       point[0] = (x0 += point[0]) * kx + dx;
Daniel@0:       point[1] = (y0 += point[1]) * ky + dy;
Daniel@0:     };
Daniel@0:   }
Daniel@0: 
Daniel@0:   function transformRelative(transform) {
Daniel@0:     if (!transform) return noop;
Daniel@0:     var x0,
Daniel@0:         y0,
Daniel@0:         kx = transform.scale[0],
Daniel@0:         ky = transform.scale[1],
Daniel@0:         dx = transform.translate[0],
Daniel@0:         dy = transform.translate[1];
Daniel@0:     return function(point, i) {
Daniel@0:       if (!i) x0 = y0 = 0;
Daniel@0:       var x1 = (point[0] - dx) / kx | 0,
Daniel@0:           y1 = (point[1] - dy) / ky | 0;
Daniel@0:       point[0] = x1 - x0;
Daniel@0:       point[1] = y1 - y0;
Daniel@0:       x0 = x1;
Daniel@0:       y0 = y1;
Daniel@0:     };
Daniel@0:   }
Daniel@0: 
Daniel@0:   function noop() {}
Daniel@0: 
Daniel@0:   if (typeof define === "function" && define.amd) define(topojson);
Daniel@0:   else if (typeof module === "object" && module.exports) module.exports = topojson;
Daniel@0:   else this.topojson = topojson;
Daniel@0: }();