EVOLUTION-NINJA

Edit File: topojson.js

function stitchArcs(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];
        }

flush(fragmentByEnd, fragmentByStart);
        flush(fragmentByStart, fragmentByEnd);
        arcs.forEach(function(i) { if (!stitchedArcs[i < 0 ? ~i : i]) fragments.push([i]); });

return fragments;
    }

function meshArcs(topology, o, filter) {
        var arcs = [];

if (arguments.length > 1) {
            var geomsByArc = [],
                geom;

function arc(i) {
                var j = i < 0 ? ~i : i;
                (geomsByArc[j] || (geomsByArc[j] = [])).push({i: i, g: geom});
            }

function line(arcs) {
                arcs.forEach(arc);
            }

function polygon(arcs) {
                arcs.forEach(line);
            }

function geometry(o) {
                if (o.type === "GeometryCollection") o.geometries.forEach(geometry);
                else if (o.type in geometryType) geom = o, geometryType[o.type](o.arcs);
            }

var geometryType = {
                LineString: line,
                MultiLineString: polygon,
                Polygon: polygon,
                MultiPolygon: function(arcs) { arcs.forEach(polygon); }
            };

geometry(o);

geomsByArc.forEach(arguments.length < 3
                ? function(geoms) { arcs.push(geoms[0].i); }
                : function(geoms) { if (filter(geoms[0].g, geoms[geoms.length - 1].g)) arcs.push(geoms[0].i); });
        } else {
            for (var i = 0, n = topology.arcs.length; i < n; ++i) arcs.push(i);
        }

return {type: "MultiLineString", arcs: stitchArcs(topology, arcs)};
    }

function mergeArcs(topology, objects) {
        var polygonsByArc = {},
            polygons = [],
            components = [];

objects.forEach(function(o) {
            if (o.type === "Polygon") register(o.arcs);
            else if (o.type === "MultiPolygon") o.arcs.forEach(register);
        });

function exterior(ring) {
            return cartesianRingArea(object(topology, {type: "Polygon", arcs: [ring]}).coordinates[0]) > 0; // TODO allow spherical?
        }

polygons.forEach(function(polygon) {
            if (!polygon._) {
                var component = [],
                    neighbors = [polygon];
                polygon._ = 1;
                components.push(component);
                while (polygon = neighbors.pop()) {
                    component.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: components.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 = stitchArcs(topology, arcs);

// If more than one ring is returned,
                // at most one of these rings can be the exterior;
                // this exterior ring has the same winding order
                // as any exterior ring in the original polygons.
                if ((n = arcs.length) > 1) {
                    var sgn = exterior(polygons[0][0]);
                    for (var i = 0, t; i < n; ++i) {
                        if (sgn === exterior(arcs[i])) {
                            t = arcs[0], arcs[0] = arcs[i], arcs[i] = t;
                            break;
                        }
                    }
                }

return arcs;
            })
        };
    }

function featureOrCollection(topology, o) {
        return o.type === "GeometryCollection" ? {
            type: "FeatureCollection",
            features: o.geometries.map(function(o) { return feature(topology, o); })
        } : feature(topology, o);
    }

function object(topology, o) {
        var absolute = transformAbsolute(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, p; k < n; ++k) {
                points.push(p = a[k].slice());
                absolute(p, k);
            }
            if (i < 0) reverse(points, n);
        }

function point(p) {
            p = p.slice();
            absolute(p, 0);
            return 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].slice());
            return points;
        }

function ring(arcs) {
            var points = line(arcs);
            while (points.length < 4) points.push(points[0].slice());
            return points;
        }

function polygon(arcs) {
            return arcs.map(ring);
        }

function geometry(o) {
            var t = o.type;
            return t === "GeometryCollection" ? {type: t, geometries: o.geometries.map(geometry)}
                : t in geometryType ? {type: t, coordinates: geometryType[t](o)}
                : null;
        }

return geometry(o);
    }

function reverse(array, n) {
        var t, j = array.length, i = j - n; while (i < --j) t = array[i], array[i++] = array[j], array[j] = t;
    }

function bisect(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;
    }

function neighbors(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);
        }

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;
    }

function presimplify(topology, triangleArea) {
        var absolute = transformAbsolute(topology.transform),
            relative = transformRelative(topology.transform),
            heap = minAreaHeap();

if (!triangleArea) triangleArea = cartesianTriangleArea;

topology.arcs.forEach(function(arc) {
            var triangles = [],
                maxArea = 0,
                triangle;

// To store each pointÃ¢â‚¬â„¢s effective area, we create a new array rather than
            // extending the passed-in point to workaround a Chrome/V8 bug (getting
            // stuck in smi mode). For midpoints, the initial effective area of
            // Infinity will be computed in the next step.
            for (var i = 0, n = arc.length, p; i < n; ++i) {
                p = arc[i];
                absolute(arc[i] = [p[0], p[1], Infinity], i);
            }

for (var i = 1, n = arc.length - 1; i < n; ++i) {
                triangle = arc.slice(i - 1, i + 2);
                triangle[1][2] = triangleArea(triangle);
                triangles.push(triangle);
                heap.push(triangle);
            }

for (var 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 area of the current point is less than that of the previous point
                // to be eliminated, use the latter's area instead. This ensures that the
                // current point cannot be eliminated without eliminating previously-
                // eliminated points.
                if (triangle[1][2] < maxArea) triangle[1][2] = maxArea;
                else maxArea = triangle[1][2];

if (previous) {
                    previous.next = next;
                    previous[2] = triangle[2];
                    update(previous);
                }

if (next) {
                    next.previous = previous;
                    next[0] = triangle[0];
                    update(next);
                }
            }

arc.forEach(relative);
        });

function update(triangle) {
            heap.remove(triangle);
            triangle[1][2] = triangleArea(triangle);
            heap.push(triangle);
        }

return topology;
    }

function cartesianRingArea(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 area / 2;
    }

function cartesianTriangleArea(triangle) {
        var a = triangle[0], b = triangle[1], c = triangle[2];
        return Math.abs((a[0] - c[0]) * (b[1] - a[1]) - (a[0] - b[0]) * (c[1] - a[1]));
    }

function compareArea(a, b) {
        return a[1][2] - b[1][2];
    }

function minAreaHeap() {
        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], (compareArea(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 (compareArea(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 && compareArea(array[l], child) < 0) child = array[j = l];
                if (r < size && compareArea(array[r], child) < 0) child = array[j = r];
                if (j === i) break;
                array[child._ = i] = child;
                array[object._ = i = j] = object;
            }
        }

return heap;
    }

function transformAbsolute(transform) {
        if (!transform) return noop;
        var x0,
            y0,
            kx = transform.scale[0],
            ky = transform.scale[1],
            dx = transform.translate[0],
            dy = transform.translate[1];
        return function(point, i) {
            if (!i) x0 = y0 = 0;
            point[0] = (x0 += point[0]) * kx + dx;
            point[1] = (y0 += point[1]) * ky + dy;
        };
    }

function transformRelative(transform) {
        if (!transform) return noop;
        var x0,
            y0,
            kx = transform.scale[0],
            ky = transform.scale[1],
            dx = transform.translate[0],
            dy = transform.translate[1];
        return function(point, i) {
            if (!i) x0 = y0 = 0;
            var x1 = (point[0] - dx) / kx | 0,
                y1 = (point[1] - dy) / ky | 0;
            point[0] = x1 - x0;
            point[1] = y1 - y0;
            x0 = x1;
            y0 = y1;
        };
    }

function noop() {}

if (typeof define === "function" && define.amd) define(topojson);
    else if (typeof module === "object" && module.exports) module.exports = topojson;
    else this.topojson = topojson;
}();