shawnbot/index.html

## index.html
<!DOCTYPE html>
<html>
  <head>
    <title>Topological line simplification segments</title>
    <script src="http://d3js.org/d3.v2.min.js?v2.10.3"></script>
    <script src="simplify.js"></script>
    <style type="text/css">

      #container {
        width: 800px;
        margin: 1em auto;
      }

      #map {
        height: 450px;
        background: #f8f8f8;
        margin: 1em auto;
      }

      #map svg {
        border: 1px solid #999;
      }

      #area {
        display: block;
        width: 100%;
      }

      #states .state {
        fill: #fff;
        stroke: #ccc;
        stroke-width: .25;
      }

      #states .edge path {
        fill: none;
        stroke-width: 1;
        stroke-opacity: .2;
      }

      #states .circle {
        fill: #000;
        fill-opacity: .5;
        stroke: none;
      }

    </style>
  </head>
  <body>
    <div id="container">
      <div id="map">
      </div>
      <input id="area" type="range" min="0" max="1000" step="10">
    </div>
    <script>

      var map = d3.select("#map"),
          width = map.property("offsetWidth"),
          height = map.property("offsetHeight"),
          minArea = location.search
            ? +location.search.substr(1) || 0
            : 0,
          range = d3.select("#area")
            .property("value", minArea)
            .on("change", function() {
              minArea = +this.value;
              update();
            });

      var zoom = d3.behavior.zoom()
        // .translate([-80, 10])
        .translate([-1841, -526])
        .scale(3.5)
        .scaleExtent([0.5, 4.0])
        .on("zoom", updateZoom);

      function updateZoom() {
        var scale = zoom.scale();
        g.attr("transform", "translate(" + zoom.translate() + ") scale(" + [scale, scale] + ")");
      }

      var svg = map.append("svg")
        .attr("width", width)
        .attr("height", height)
        .call(zoom);

      var g = svg.append("g")
        .attr("id", "states");

      updateZoom();

      var proj = d3.geo.albers(),
          linear = function(c) {
            return [c[0], c[1]];
          };

      var path = d3.geo.path()
        .projection(linear);

      var simplify = d3.simplify()
        .topology(true)
        .projection(proj)
        .area(minArea);

      var collection;
      d3.json("us-states.json", function(us) {

        /*
        var ignore = [
          "Alaska",
          "Hawaii",
          "Guam",
          "Puerto Rico"
        ];
        us.features = us.features.filter(function(state) {
          return ignore.indexOf(state.properties.name) === -1;
        });
        */

        var stateNames = [
          "Illinois",
          "Indiana",
          "Ohio",
          "Kentucky"
        ];
        us.features = us.features.filter(function(state) {
          return stateNames.indexOf(state.properties.name) > -1;
        });

        collection = us;
        update();
      });

      function update() {
        // console.log("minArea:", minArea);

        var simplified = simplify
          .area(minArea)
          .project(copy(collection));

        // XXX: you have to do this to "apply" the simplification,
        // or call path(simplify(d)) in side the "d" setter below
        simplified = simplify(simplified);

        var states = g.selectAll("path.state")
          .data(simplified.features, function(d) {
            return d.id;
          });

        states.enter()
          .append("path")
            .attr("class", "state")
            .attr("id", function(d) {
              return d.properties.name;
            })
            .append("title")
              .text(function(d) {
                return d.properties.name;
              });

        states.exit().remove();

        states.attr("d", path);

        // topology analysis
        var edges = getEdges(simplified.features, simplified.topology);
        console.log("edges:", edges);

        var color = d3.scale.linear()
          .domain([0, edges.length - 1])
          .range(["#00f", "#f00"]);

        var eg = g.selectAll("g.edge")
          .data(edges, function(d) {
            return d.id;
          });

        var enter = eg.enter()
          .append("g")
            .attr("class", "edge")
            .attr("id", function(d) {
              return "edge" + d.id;
            });

        eg.exit().remove();

        enter.append("path");

        var dots = eg.selectAll("circle")
          .data(function(d) {
            return d.coords;
          });

        dots.enter()
          .append("circle")
            .attr("class", "point")
            .attr("r", .5);

        dots.exit().remove();

        dots.attr("cx", function(d) {
            return d[0];
          })
          .attr("cy", function(d) {
            return d[1];
          });

        var line = d3.svg.line(),
            lines = eg.select("path")
              .attr("stroke", function(d, i) {
                return color(i);
              })
              .attr("d", function(d) {
                return line(d.coords);
              });
      }

      function getEdges(features, topo) {
        var edgesById = {};
        console.log("topo:", topo);
        features.forEach(function(feature) {
          // get all the rings
          var rings = getRings(feature.geometry);
          rings.forEach(function(ring) {
            // remember the last edge
            var lastEdge;
            ring.forEach(function(coord, i) {
              var coord = coord.slice(0, 2),
                  key = coord.join(","),
                  id = topo.idByPoint[key];

              // shared coords are always solo,
              // and get pushed onto the last edge
              if (topo.sharedPoints[key] && lastEdge) {
                lastEdge.coords.push(coord);
                return;
              }

              var edge;
              // if we have an edge with this id...
              if (edgesById.hasOwnProperty(id)) {
                edge = edgesById[id];
                // if the edge doesn't already reference this feature
                if (edge.features.indexOf(feature) === -1) {
                  // add it to the features list
                  edge.features.push(feature);
                }
                // if the edge doesn't alreay contain this coord
                if (!edge.seen.hasOwnProperty(key)) {
                  // push it onto the list
                  edge.coords.push(coord);
                  // and mark it as seen
                  edge.seen[key] = 1;
                }
              } else {
                // otherwise, create the new edge
                edge = edgesById[id] = {
                  features: [feature],
                  coords: [coord],
                  seen: {}
                };

                // if the last edge has the same id...
                if (lastEdge && lastEdge.id === id) {
                  // get its last coordinate and key
                  var prev = lastEdge.coords[lastEdge.coords.length - 1],
                      prevKey = prev.join(",");
                  // and if the edge doesn't already contain that coord
                  if (!edge.seen.hasOwnProperty(prevKey)) {
                    // push it onto the list
                    edge.coords.unshift(prev);
                    // and mark it as seen
                    edge.seen[prevKey] = 1;
                  }
                }
                edge.seen[key] = 1;
              }

              lastEdge = edge;
            });
          });
        });

        for (var id in edgesById) {
          var edge = edgesById[id];
        }

        return d3.entries(edgesById)
          .filter(function(entry) {
            return true; // entry.value.coords.length > 1;
          })
          .map(function(entry) {
            return {
              id: entry.key,
              features: entry.value.features,
              coords: d3.values(entry.value.coords)
            };
          });
      }

      function getRings(geometry) {
        var rings = [];
        switch (geometry.type) {
          case "Line":
          case "LineString":
            return geometry.coordinates;

          case "Polygon":
            geometry.coordinates.forEach(function(ring) {
              rings.push(ring);
            });
            break;

          case "MultiPolygon":
            geometry.coordinates.forEach(function(poly) {
              poly.forEach(function(ring) {
                rings.push(ring);
              });
            });
            break;

          // TODO: support other geometry types:
          // GeometryCollection
        }
        return rings;
      }

      function copy(d) {
        return d instanceof Array
          ? d.map(copy)
          : (typeof d === "number" || typeof d === "string")
            ? d
            : copyObject(d);
      }

      function copyObject(d) {
        var o = {};
        for (var k in d) o[k] = copy(d[k]);
        return o;
      }

    </script>
  </body>
</html>

## simplify.js
(function() {

d3.simplify = function() {
  var projection = d3.geo.albers(),
      triangulateLineString = triangulateLineStringSimple,
      heap,
      minArea = 3,
      topology = false,
      ringId,
      id,
      idByRings,
      idByPoint,
      ringsByPoint,
      sharedPoints,
      lastRingByPoint,
      isShared,
      graph;

  var projectCoordinates = {
    MultiPolygon: projectMultiPolygon,
    Polygon: projectPolygon,
    MultiLineString: projectPolygon,
    LineString: projectLineString
  };

  var triangulateCoordinates = {
    MultiPolygon: triangulateMultiPolygon,
    Polygon: triangulatePolygon,
    MultiLineString: triangulatePolygon,
    LineString: triangulateLineString
  };

  var simplifyCoordinates = {
    MultiPolygon: simplifyMultiPolygon,
    Polygon: simplifyPolygon,
    MultiLineString: simplifyPolygon,
    LineString: simplifyLineString
  };

  function simplify(object) {
    var type = object.type;
    if (type === "FeatureCollection") {
      object = copy(object);
      object.features = object.features.map(simplifyFeature).filter(nonemptyFeature);
      return object;
    }
    return (type === "Feature" ? simplifyFeature : simplifyGeometry)(object);
  }

  simplify.project = function(feature) {
    var maxArea = 0,
        maxAreas = {},
        triangle;

    heap = minHeap();

    if (topology) {
      id = 0;
      idByRings = {};
      ringsByPoint = {};
      idByPoint = {};
      sharedPoints = {};
      lastRingByPoint = {};
      isShared = {};
      graph = {};
      triangulateTopology(feature);
    } else {
      triangulateSimple(feature);
    }

    while (triangle = heap.pop()) {
      // 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 (triangle.previous) {
        triangle.previous.next = triangle.next;
        triangle.previous[2] = triangle[2];
        update(triangle.previous);
      } else if (topology) {
        maxAreas[triangle.ring] = triangle[1][2];
      } else {
        triangle[0][2] = triangle[1][2];
      }

      if (triangle.next) {
        triangle.next.previous = triangle.previous;
        triangle.next[0] = triangle[0];
        update(triangle.next);
      } else if (topology) {
        maxAreas[triangle.ring] = triangle[1][2];
      } else {
        triangle[2][2] = triangle[1][2];
      }
    }

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

    if (topology) {
      var seen = {},
          max,
          m,
          c;
      for (var key in graph) {
        if (seen.hasOwnProperty(key)) continue;
        max = 0;
        for (var k in (c = components(graph, key))) if ((m = maxAreas[k]) > max) max = m;
        for (var k in c) maxAreas[k] = max, seen[k] = 1;
      }

      for (var key in sharedPoints) {
        maxArea = maxAreas[ringsByPoint[key][0]];
        sharedPoints[key].forEach(function(point) { point[2] = maxArea; });
      }
      // export topology data
      feature.topology = {
        idByPoint: idByPoint,
        idByRings: idByRings,
        ringsByPoint: ringsByPoint,
        sharedPoints: sharedPoints,
        isShared: isShared,
        lastRingByPoint: lastRingByPoint,
        graph: graph
      };
      idByPoint = idByRings = ringsByPoint = sharedPoints = isShared = lastRingByPoint = graph = null;
    }

    heap = null;
    return feature;
  };

  function components(graph, source) {
    var seen = {},
        nextLevel = {},
        thisLevel,
        empty;
    nextLevel[source] = 1;
    while (1) {
      empty = true;
      for (var k in nextLevel) empty = false;
      if (empty) break;
      thisLevel = nextLevel;
      nextLevel = {};
      for (var v in thisLevel) {
        if (seen.hasOwnProperty(v)) continue;
        seen[v] = 1;
        var neighbors = graph[v];
        for (var k in neighbors) nextLevel[k] = neighbors[k];
      }
    }
    return seen;
  }

  function projectFeature(feature) {
    projectGeometry(feature.geometry);
  }

  function projectGeometry(geometry) {
    var type = geometry.type;
    if (type === "GeometryCollection") geometry.geometries.forEach(projectGeometry);
    else geometry.coordinates = projectCoordinates[type](geometry.coordinates);
  }

  function projectMultiPolygon(multiPolygon) {
    return multiPolygon.map(projectPolygon);
  }

  function projectPolygon(polygon) {
    return polygon.map(projectLineString);
  }

  function projectLineString(lineString) {
    ++ringId;
    return lineString.map(projectPoint);
  }

  function projectPoint(point) {
    var pointKey = (point = projection(point))[0] + "," + point[1],
        key = (idByPoint.hasOwnProperty(pointKey) ? idByPoint[pointKey] + ":" : "") + ringId;
    idByPoint[pointKey] = idByRings.hasOwnProperty(key)
        ? idByRings[key]
        : idByRings[key] = ++id;
    if (lastRingByPoint.hasOwnProperty(pointKey) && lastRingByPoint[pointKey] !== ringId) {
      isShared[pointKey] = 1;
    }
    lastRingByPoint[pointKey] = ringId;
    return point;
  }

  function triangulateLineStringTopology(lineString) {
    ++ringId;
    var n = lineString.length - 1,
        triangle0,
        triangle,
        a = lineString[0],
        b = lineString[1],
        c,
        key0,
        key,
        idA = idByPoint[a[0] + "," + a[1]],
        idB = idByPoint[key0 = b[0] + "," + b[1]],
        idC;

    lineString[0][2] = lineString[n][2] = 0;
    if (n < 2) return lineString;

    graph[ringId] = {};

    addSharedPoint(a);
    for (var i = 2; i <= n; ++i, a = b, b = c, idA = idB, idB = idC, key0 = key) {
      c = lineString[i];
      idC = idByPoint[key = c[0] + "," + c[1]];
      if (idA === idB && idB === idC || !isShared.hasOwnProperty(key0)) {
        triangle = [a, b, c];
        triangle.ring = ringId;
        b[2] = area(triangle);
        heap.push(triangle);
        if (triangle0) (triangle.previous = triangle0).next = triangle;
        triangle0 = triangle;
      } else {
        addSharedPoint(b);
        triangle0 = null;
      }
    }
    addSharedPoint(b);

    function addSharedPoint(point) {
      var key = point[0] + "," + point[1],
          rings = ringsByPoint.hasOwnProperty(key) ? ringsByPoint[key] : (ringsByPoint[key] = []);
      rings.forEach(function(ring) {
        graph[ring][ringId] = graph[ringId][ring] = 1;
      });
      rings.push(ringId);
      if (sharedPoints.hasOwnProperty(key)) sharedPoints[key].push(point);
      else sharedPoints[key] = [point];
    }

    return lineString;
  }

  // Project and triangulate.
  function triangulateLineStringSimple(lineString) {
    var points = lineString.map(projection),
        n = points.length - 1,
        triangle0,
        triangle,
        a = points[0],
        b = points[1],
        c;

    points[0][2] = points[n][2] = 0;

    for (var i = 2; i <= n; ++i) {
      triangle = [a, b, c = points[i]];
      b[2] = area(triangle);
      heap.push(triangle);
      if (triangle0) (triangle.previous = triangle0).next = triangle;
      triangle0 = triangle;
      a = b;
      b = c;
    }

    return points;
  }

  function triangulateSimple(object) {
    var type = object.type;
    if (type === "FeatureCollection") object.features.forEach(triangulateFeature);
    else (type === "Feature" ? triangulateFeature : triangulateGeometry)(object);
  }

  function triangulateTopology(object) {
    var type = object.type;
    ringId = 0;
    if (type === "FeatureCollection") {
      object.features.forEach(projectFeature);
      ringId = 0;
      object.features.forEach(triangulateFeature);
    } else if (type === "Feature") {
      projectFeature(object);
      ringId = 0;
      triangulateFeature(object);
    } else {
      projectGeometry(object);
      ringId = 0;
      triangulateGeometry(object);
    }
  }

  function triangulateFeature(feature) {
    triangulateGeometry(feature.geometry);
  }

  function triangulateGeometry(geometry) {
    var type = geometry.type;
    if (type === "GeometryCollection") geometry.geometries.forEach(triangulateGeometry);
    else geometry.coordinates = triangulateCoordinates[type](geometry.coordinates);
  }

  function triangulateMultiPolygon(multiPolygon) {
    return multiPolygon.map(triangulatePolygon);
  }

  function triangulatePolygon(polygon) {
    return polygon.map(triangulateLineString);
  }

  function simplifyFeature(feature) {
    feature = copy(feature);
    feature.geometry = simplifyGeometry(feature.geometry);
    return feature;
  }

  function simplifyGeometry(geometry) {
    var type = geometry.type;
    geometry = copy(geometry);
    if (type === "GeometryCollection") {
      geometry.geometries = geometry.geometries.map(simplifyGeometry).filter(nonemptyGeometry);
    } else {
      geometry.coordinates = simplifyCoordinates[type](geometry.coordinates);
    }
    return geometry;
  }

  function simplifyMultiPolygon(multiPolygon) {
    return multiPolygon.map(simplifyPolygon).filter(length);
  }

  function simplifyPolygon(polygon) {
    return polygon.map(simplifyLineString).filter(length);
  }

  function simplifyLineString(lineString) {
    return lineString.filter(filterLineString);
  }

  function filterLineString(point) {
    return point[2] >= minArea;
  }

  simplify.projection = function(_) {
    if (!arguments.length) return projection;
    projection = _;
    return simplify;
  };

  simplify.area = function(_) {
    if (!arguments.length) return minArea;
    minArea = +_;
    return simplify;
  };

  simplify.topology = function(_) {
    if (!arguments.length) return topology;
    triangulateCoordinates.LineString =
    triangulateLineString = (topology = !!_)
        ? triangulateLineStringTopology
        : triangulateLineStringSimple;
    return simplify;
  };

  return simplify;
};

function compare(a, b) {
  return a[1][2] - b[1][2] || a[1][1] - b[1][1] || a[1][0] - b[1][0];
}

function area(t) {
  return Math.abs((t[0][0] - t[2][0]) * (t[1][1] - t[0][1]) - (t[0][0] - t[1][0]) * (t[2][1] - t[0][1]));
}

function minHeap() {
  var heap = {},
      array = [];

  heap.push = function() {
    for (var i = 0, n = arguments.length; i < n; ++i) {
      var object = arguments[i];
      up(object.index = array.push(object) - 1);
    }
    return array.length;
  };

  heap.pop = function() {
    var removed = array[0],
        object = array.pop();
    if (array.length) {
      array[object.index = 0] = object;
      down(0);
    }
    return removed;
  };

  heap.remove = function(removed) {
    var i = removed.index,
        object = array.pop();
    if (i !== array.length) {
      array[object.index = i] = object;
      (compare(object, removed) < 0 ? up : down)(i);
    }
    return i;
  };

  function up(i) {
    var object = array[i];
    while (i > 0) {
      var up = ((i + 1) >> 1) - 1,
          parent = array[up];
      if (compare(object, parent) >= 0) break;
      array[parent.index = i] = parent;
      array[object.index = i = up] = object;
    }
  }

  function down(i) {
    var object = array[i];
    while (true) {
      var right = (i + 1) << 1,
          left = right - 1,
          down = i,
          child = array[down];
      if (left < array.length && compare(array[left], child) < 0) child = array[down = left];
      if (right < array.length && compare(array[right], child) < 0) child = array[down = right];
      if (down === i) break;
      array[child.index = i] = child;
      array[object.index = i = down] = object;
    }
  }

  return heap;
}

function nonemptyFeature(d) { return nonemptyGeometry(d.geometry); }

function nonemptyGeometry(d) {
  return length(d.type === "GeometryCollection"
      ? d.geometries : d.coordinates);
}

function length(d) { return d.length; }

function copy(object) {
  var o = {};
  for (var key in object) o[key] = object[key];
  return o;
}

})();

## us-states.json

      
Display the source blob

    
Display the rendered blob

    
    Raw
  

              us-states.json
            
          
      Sorry, something went wrong. Reload?
      Sorry, we cannot display this file.
      Sorry, this file is invalid so it cannot be displayed.
      
          Viewer requires iframe.
	<!DOCTYPE html>
	<html>
	<head>
	<title>Topological line simplification segments</title>
	<script src="http://d3js.org/d3.v2.min.js?v2.10.3"></script>
	<script src="simplify.js"></script>
	<style type="text/css">

	#container {
	width: 800px;
	margin: 1em auto;
	}

	#map {
	height: 450px;
	background: #f8f8f8;
	margin: 1em auto;
	}

	#map svg {
	border: 1px solid #999;
	}

	#area {
	display: block;
	width: 100%;
	}

	#states .state {
	fill: #fff;
	stroke: #ccc;
	stroke-width: .25;
	}

	#states .edge path {
	fill: none;
	stroke-width: 1;
	stroke-opacity: .2;
	}

	#states .circle {
	fill: #000;
	fill-opacity: .5;
	stroke: none;
	}

	</style>
	</head>
	<body>
	<div id="container">
	<div id="map">
	</div>
	<input id="area" type="range" min="0" max="1000" step="10">
	</div>
	<script>

	var map = d3.select("#map"),
	width = map.property("offsetWidth"),
	height = map.property("offsetHeight"),
	minArea = location.search
	? +location.search.substr(1) \|\| 0
	: 0,
	range = d3.select("#area")
	.property("value", minArea)
	.on("change", function() {
	minArea = +this.value;
	update();
	});

	var zoom = d3.behavior.zoom()
	// .translate([-80, 10])
	.translate([-1841, -526])
	.scale(3.5)
	.scaleExtent([0.5, 4.0])
	.on("zoom", updateZoom);

	function updateZoom() {
	var scale = zoom.scale();
	g.attr("transform", "translate(" + zoom.translate() + ") scale(" + [scale, scale] + ")");
	}

	var svg = map.append("svg")
	.attr("width", width)
	.attr("height", height)
	.call(zoom);

	var g = svg.append("g")
	.attr("id", "states");

	updateZoom();

	var proj = d3.geo.albers(),
	linear = function(c) {
	return [c[0], c[1]];
	};

	var path = d3.geo.path()
	.projection(linear);

	var simplify = d3.simplify()
	.topology(true)
	.projection(proj)
	.area(minArea);

	var collection;
	d3.json("us-states.json", function(us) {

	/*
	var ignore = [
	"Alaska",
	"Hawaii",
	"Guam",
	"Puerto Rico"
	];
	us.features = us.features.filter(function(state) {
	return ignore.indexOf(state.properties.name) === -1;
	});
	*/

	var stateNames = [
	"Illinois",
	"Indiana",
	"Ohio",
	"Kentucky"
	];
	us.features = us.features.filter(function(state) {
	return stateNames.indexOf(state.properties.name) > -1;
	});

	collection = us;
	update();
	});

	function update() {
	// console.log("minArea:", minArea);

	var simplified = simplify
	.area(minArea)
	.project(copy(collection));

	// XXX: you have to do this to "apply" the simplification,
	// or call path(simplify(d)) in side the "d" setter below
	simplified = simplify(simplified);

	var states = g.selectAll("path.state")
	.data(simplified.features, function(d) {
	return d.id;
	});

	states.enter()
	.append("path")
	.attr("class", "state")
	.attr("id", function(d) {
	return d.properties.name;
	})
	.append("title")
	.text(function(d) {
	return d.properties.name;
	});

	states.exit().remove();

	states.attr("d", path);

	// topology analysis
	var edges = getEdges(simplified.features, simplified.topology);
	console.log("edges:", edges);

	var color = d3.scale.linear()
	.domain([0, edges.length - 1])
	.range(["#00f", "#f00"]);

	var eg = g.selectAll("g.edge")
	.data(edges, function(d) {
	return d.id;
	});

	var enter = eg.enter()
	.append("g")
	.attr("class", "edge")
	.attr("id", function(d) {
	return "edge" + d.id;
	});

	eg.exit().remove();

	enter.append("path");

	var dots = eg.selectAll("circle")
	.data(function(d) {
	return d.coords;
	});

	dots.enter()
	.append("circle")
	.attr("class", "point")
	.attr("r", .5);

	dots.exit().remove();

	dots.attr("cx", function(d) {
	return d[0];
	})
	.attr("cy", function(d) {
	return d[1];
	});

	var line = d3.svg.line(),
	lines = eg.select("path")
	.attr("stroke", function(d, i) {
	return color(i);
	})
	.attr("d", function(d) {
	return line(d.coords);
	});
	}

	function getEdges(features, topo) {
	var edgesById = {};
	console.log("topo:", topo);
	features.forEach(function(feature) {
	// get all the rings
	var rings = getRings(feature.geometry);
	rings.forEach(function(ring) {
	// remember the last edge
	var lastEdge;
	ring.forEach(function(coord, i) {
	var coord = coord.slice(0, 2),
	key = coord.join(","),
	id = topo.idByPoint[key];

	// shared coords are always solo,
	// and get pushed onto the last edge
	if (topo.sharedPoints[key] && lastEdge) {
	lastEdge.coords.push(coord);
	return;
	}

	var edge;
	// if we have an edge with this id...
	if (edgesById.hasOwnProperty(id)) {
	edge = edgesById[id];
	// if the edge doesn't already reference this feature
	if (edge.features.indexOf(feature) === -1) {
	// add it to the features list
	edge.features.push(feature);
	}
	// if the edge doesn't alreay contain this coord
	if (!edge.seen.hasOwnProperty(key)) {
	// push it onto the list
	edge.coords.push(coord);
	// and mark it as seen
	edge.seen[key] = 1;
	}
	} else {
	// otherwise, create the new edge
	edge = edgesById[id] = {
	features: [feature],
	coords: [coord],
	seen: {}
	};

	// if the last edge has the same id...
	if (lastEdge && lastEdge.id === id) {
	// get its last coordinate and key
	var prev = lastEdge.coords[lastEdge.coords.length - 1],
	prevKey = prev.join(",");
	// and if the edge doesn't already contain that coord
	if (!edge.seen.hasOwnProperty(prevKey)) {
	// push it onto the list
	edge.coords.unshift(prev);
	// and mark it as seen
	edge.seen[prevKey] = 1;
	}
	}
	edge.seen[key] = 1;
	}

	lastEdge = edge;
	});
	});
	});

	for (var id in edgesById) {
	var edge = edgesById[id];
	}

	return d3.entries(edgesById)
	.filter(function(entry) {
	return true; // entry.value.coords.length > 1;
	})
	.map(function(entry) {
	return {
	id: entry.key,
	features: entry.value.features,
	coords: d3.values(entry.value.coords)
	};
	});
	}

	function getRings(geometry) {
	var rings = [];
	switch (geometry.type) {
	case "Line":
	case "LineString":
	return geometry.coordinates;

	case "Polygon":
	geometry.coordinates.forEach(function(ring) {
	rings.push(ring);
	});
	break;

	case "MultiPolygon":
	geometry.coordinates.forEach(function(poly) {
	poly.forEach(function(ring) {
	rings.push(ring);
	});
	});
	break;

	// TODO: support other geometry types:
	// GeometryCollection
	}
	return rings;
	}

	function copy(d) {
	return d instanceof Array
	? d.map(copy)
	: (typeof d === "number" \|\| typeof d === "string")
	? d
	: copyObject(d);
	}

	function copyObject(d) {
	var o = {};
	for (var k in d) o[k] = copy(d[k]);
	return o;
	}

	</script>
	</body>
	</html>
	(function() {

	d3.simplify = function() {
	var projection = d3.geo.albers(),
	triangulateLineString = triangulateLineStringSimple,
	heap,
	minArea = 3,
	topology = false,
	ringId,
	id,
	idByRings,
	idByPoint,
	ringsByPoint,
	sharedPoints,
	lastRingByPoint,
	isShared,
	graph;

	var projectCoordinates = {
	MultiPolygon: projectMultiPolygon,
	Polygon: projectPolygon,
	MultiLineString: projectPolygon,
	LineString: projectLineString
	};

	var triangulateCoordinates = {
	MultiPolygon: triangulateMultiPolygon,
	Polygon: triangulatePolygon,
	MultiLineString: triangulatePolygon,
	LineString: triangulateLineString
	};

	var simplifyCoordinates = {
	MultiPolygon: simplifyMultiPolygon,
	Polygon: simplifyPolygon,
	MultiLineString: simplifyPolygon,
	LineString: simplifyLineString
	};

	function simplify(object) {
	var type = object.type;
	if (type === "FeatureCollection") {
	object = copy(object);
	object.features = object.features.map(simplifyFeature).filter(nonemptyFeature);
	return object;
	}
	return (type === "Feature" ? simplifyFeature : simplifyGeometry)(object);
	}

	simplify.project = function(feature) {
	var maxArea = 0,
	maxAreas = {},
	triangle;

	heap = minHeap();

	if (topology) {
	id = 0;
	idByRings = {};
	ringsByPoint = {};
	idByPoint = {};
	sharedPoints = {};
	lastRingByPoint = {};
	isShared = {};
	graph = {};
	triangulateTopology(feature);
	} else {
	triangulateSimple(feature);
	}

	while (triangle = heap.pop()) {
	// 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 (triangle.previous) {
	triangle.previous.next = triangle.next;
	triangle.previous[2] = triangle[2];
	update(triangle.previous);
	} else if (topology) {
	maxAreas[triangle.ring] = triangle[1][2];
	} else {
	triangle[0][2] = triangle[1][2];
	}

	if (triangle.next) {
	triangle.next.previous = triangle.previous;
	triangle.next[0] = triangle[0];
	update(triangle.next);
	} else if (topology) {
	maxAreas[triangle.ring] = triangle[1][2];
	} else {
	triangle[2][2] = triangle[1][2];
	}
	}

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

	if (topology) {
	var seen = {},
	max,
	m,
	c;
	for (var key in graph) {
	if (seen.hasOwnProperty(key)) continue;
	max = 0;
	for (var k in (c = components(graph, key))) if ((m = maxAreas[k]) > max) max = m;
	for (var k in c) maxAreas[k] = max, seen[k] = 1;
	}

	for (var key in sharedPoints) {
	maxArea = maxAreas[ringsByPoint[key][0]];
	sharedPoints[key].forEach(function(point) { point[2] = maxArea; });
	}
	// export topology data
	feature.topology = {
	idByPoint: idByPoint,
	idByRings: idByRings,
	ringsByPoint: ringsByPoint,
	sharedPoints: sharedPoints,
	isShared: isShared,
	lastRingByPoint: lastRingByPoint,
	graph: graph
	};
	idByPoint = idByRings = ringsByPoint = sharedPoints = isShared = lastRingByPoint = graph = null;
	}

	heap = null;
	return feature;
	};

	function components(graph, source) {
	var seen = {},
	nextLevel = {},
	thisLevel,
	empty;
	nextLevel[source] = 1;
	while (1) {
	empty = true;
	for (var k in nextLevel) empty = false;
	if (empty) break;
	thisLevel = nextLevel;
	nextLevel = {};
	for (var v in thisLevel) {
	if (seen.hasOwnProperty(v)) continue;
	seen[v] = 1;
	var neighbors = graph[v];
	for (var k in neighbors) nextLevel[k] = neighbors[k];
	}
	}
	return seen;
	}

	function projectFeature(feature) {
	projectGeometry(feature.geometry);
	}

	function projectGeometry(geometry) {
	var type = geometry.type;
	if (type === "GeometryCollection") geometry.geometries.forEach(projectGeometry);
	else geometry.coordinates = projectCoordinates[type](geometry.coordinates);
	}

	function projectMultiPolygon(multiPolygon) {
	return multiPolygon.map(projectPolygon);
	}

	function projectPolygon(polygon) {
	return polygon.map(projectLineString);
	}

	function projectLineString(lineString) {
	++ringId;
	return lineString.map(projectPoint);
	}

	function projectPoint(point) {
	var pointKey = (point = projection(point))[0] + "," + point[1],
	key = (idByPoint.hasOwnProperty(pointKey) ? idByPoint[pointKey] + ":" : "") + ringId;
	idByPoint[pointKey] = idByRings.hasOwnProperty(key)
	? idByRings[key]
	: idByRings[key] = ++id;
	if (lastRingByPoint.hasOwnProperty(pointKey) && lastRingByPoint[pointKey] !== ringId) {
	isShared[pointKey] = 1;
	}
	lastRingByPoint[pointKey] = ringId;
	return point;
	}

	function triangulateLineStringTopology(lineString) {
	++ringId;
	var n = lineString.length - 1,
	triangle0,
	triangle,
	a = lineString[0],
	b = lineString[1],
	c,
	key0,
	key,
	idA = idByPoint[a[0] + "," + a[1]],
	idB = idByPoint[key0 = b[0] + "," + b[1]],
	idC;

	lineString[0][2] = lineString[n][2] = 0;
	if (n < 2) return lineString;

	graph[ringId] = {};

	addSharedPoint(a);
	for (var i = 2; i <= n; ++i, a = b, b = c, idA = idB, idB = idC, key0 = key) {
	c = lineString[i];
	idC = idByPoint[key = c[0] + "," + c[1]];
	if (idA === idB && idB === idC \|\| !isShared.hasOwnProperty(key0)) {
	triangle = [a, b, c];
	triangle.ring = ringId;
	b[2] = area(triangle);
	heap.push(triangle);
	if (triangle0) (triangle.previous = triangle0).next = triangle;
	triangle0 = triangle;
	} else {
	addSharedPoint(b);
	triangle0 = null;
	}
	}
	addSharedPoint(b);

	function addSharedPoint(point) {
	var key = point[0] + "," + point[1],
	rings = ringsByPoint.hasOwnProperty(key) ? ringsByPoint[key] : (ringsByPoint[key] = []);
	rings.forEach(function(ring) {
	graph[ring][ringId] = graph[ringId][ring] = 1;
	});
	rings.push(ringId);
	if (sharedPoints.hasOwnProperty(key)) sharedPoints[key].push(point);
	else sharedPoints[key] = [point];
	}

	return lineString;
	}

	// Project and triangulate.
	function triangulateLineStringSimple(lineString) {
	var points = lineString.map(projection),
	n = points.length - 1,
	triangle0,
	triangle,
	a = points[0],
	b = points[1],
	c;

	points[0][2] = points[n][2] = 0;

	for (var i = 2; i <= n; ++i) {
	triangle = [a, b, c = points[i]];
	b[2] = area(triangle);
	heap.push(triangle);
	if (triangle0) (triangle.previous = triangle0).next = triangle;
	triangle0 = triangle;
	a = b;
	b = c;
	}

	return points;
	}

	function triangulateSimple(object) {
	var type = object.type;
	if (type === "FeatureCollection") object.features.forEach(triangulateFeature);
	else (type === "Feature" ? triangulateFeature : triangulateGeometry)(object);
	}

	function triangulateTopology(object) {
	var type = object.type;
	ringId = 0;
	if (type === "FeatureCollection") {
	object.features.forEach(projectFeature);
	ringId = 0;
	object.features.forEach(triangulateFeature);
	} else if (type === "Feature") {
	projectFeature(object);
	ringId = 0;
	triangulateFeature(object);
	} else {
	projectGeometry(object);
	ringId = 0;
	triangulateGeometry(object);
	}
	}

	function triangulateFeature(feature) {
	triangulateGeometry(feature.geometry);
	}

	function triangulateGeometry(geometry) {
	var type = geometry.type;
	if (type === "GeometryCollection") geometry.geometries.forEach(triangulateGeometry);
	else geometry.coordinates = triangulateCoordinates[type](geometry.coordinates);
	}

	function triangulateMultiPolygon(multiPolygon) {
	return multiPolygon.map(triangulatePolygon);
	}

	function triangulatePolygon(polygon) {
	return polygon.map(triangulateLineString);
	}

	function simplifyFeature(feature) {
	feature = copy(feature);
	feature.geometry = simplifyGeometry(feature.geometry);
	return feature;
	}

	function simplifyGeometry(geometry) {
	var type = geometry.type;
	geometry = copy(geometry);
	if (type === "GeometryCollection") {
	geometry.geometries = geometry.geometries.map(simplifyGeometry).filter(nonemptyGeometry);
	} else {
	geometry.coordinates = simplifyCoordinates[type](geometry.coordinates);
	}
	return geometry;
	}

	function simplifyMultiPolygon(multiPolygon) {
	return multiPolygon.map(simplifyPolygon).filter(length);
	}

	function simplifyPolygon(polygon) {
	return polygon.map(simplifyLineString).filter(length);
	}

	function simplifyLineString(lineString) {
	return lineString.filter(filterLineString);
	}

	function filterLineString(point) {
	return point[2] >= minArea;
	}

	simplify.projection = function(_) {
	if (!arguments.length) return projection;
	projection = _;
	return simplify;
	};

	simplify.area = function(_) {
	if (!arguments.length) return minArea;
	minArea = +_;
	return simplify;
	};

	simplify.topology = function(_) {
	if (!arguments.length) return topology;
	triangulateCoordinates.LineString =
	triangulateLineString = (topology = !!_)
	? triangulateLineStringTopology
	: triangulateLineStringSimple;
	return simplify;
	};

	return simplify;
	};

	function compare(a, b) {
	return a[1][2] - b[1][2] \|\| a[1][1] - b[1][1] \|\| a[1][0] - b[1][0];
	}

	function area(t) {
	return Math.abs((t[0][0] - t[2][0]) * (t[1][1] - t[0][1]) - (t[0][0] - t[1][0]) * (t[2][1] - t[0][1]));
	}

	function minHeap() {
	var heap = {},
	array = [];

	heap.push = function() {
	for (var i = 0, n = arguments.length; i < n; ++i) {
	var object = arguments[i];
	up(object.index = array.push(object) - 1);
	}
	return array.length;
	};

	heap.pop = function() {
	var removed = array[0],
	object = array.pop();
	if (array.length) {
	array[object.index = 0] = object;
	down(0);
	}
	return removed;
	};

	heap.remove = function(removed) {
	var i = removed.index,
	object = array.pop();
	if (i !== array.length) {
	array[object.index = i] = object;
	(compare(object, removed) < 0 ? up : down)(i);
	}
	return i;
	};

	function up(i) {
	var object = array[i];
	while (i > 0) {
	var up = ((i + 1) >> 1) - 1,
	parent = array[up];
	if (compare(object, parent) >= 0) break;
	array[parent.index = i] = parent;
	array[object.index = i = up] = object;
	}
	}

	function down(i) {
	var object = array[i];
	while (true) {
	var right = (i + 1) << 1,
	left = right - 1,
	down = i,
	child = array[down];
	if (left < array.length && compare(array[left], child) < 0) child = array[down = left];
	if (right < array.length && compare(array[right], child) < 0) child = array[down = right];
	if (down === i) break;
	array[child.index = i] = child;
	array[object.index = i = down] = object;
	}
	}

	return heap;
	}

	function nonemptyFeature(d) { return nonemptyGeometry(d.geometry); }

	function nonemptyGeometry(d) {
	return length(d.type === "GeometryCollection"
	? d.geometries : d.coordinates);
	}

	function length(d) { return d.length; }

	function copy(object) {
	var o = {};
	for (var key in object) o[key] = object[key];
	return o;
	}

	})();