Browse files

Fix translation and zoom-dependency of simplify

* Use a fixed projection for simplification
* Correctly translate simplify
  • Loading branch information...
1 parent dbe3020 commit f0577100d90e948d0141b453d9d4c97d3677e20a @tmcw tmcw committed Feb 27, 2013
Showing with 300 additions and 0 deletions.
  1. +3 −0 index.html
  2. +82 −0 js/id/actions/simplify.js
  3. +25 −0 js/id/operations/simplify.js
  4. +181 −0 js/lib/simplify.js
  5. +9 −0 locale/en.js
View
3 index.html
@@ -31,6 +31,7 @@
<script src='js/lib/d3-compat.js'></script>
<script src='js/lib/bootstrap-tooltip.js'></script>
<script src='js/lib/rtree.js'></script>
+ <script src='js/lib/simplify.js'></script>
<script src='js/id/id.js'></script>
<script src='js/id/util.js'></script>
@@ -114,6 +115,7 @@
<script src='js/id/actions/rotate_way.js'></script>
<script src='js/id/actions/circularize.js'></script>
<script src='js/id/actions/orthogonalize.js'></script>
+ <script src='js/id/actions/simplify.js'></script>
<script src='js/id/actions/noop.js'></script>
<script src='js/id/actions/reverse.js'></script>
<script src='js/id/actions/split.js'></script>
@@ -144,6 +146,7 @@
<script src='js/id/operations.js'></script>
<script src='js/id/operations/circularize.js'></script>
<script src='js/id/operations/orthogonalize.js'></script>
+ <script src='js/id/operations/simplify.js'></script>
<script src='js/id/operations/delete.js'></script>
<script src='js/id/operations/disconnect.js'></script>
<script src='js/id/operations/merge.js'></script>
View
82 js/id/actions/simplify.js
@@ -0,0 +1,82 @@
+iD.actions.Simplify = function(wayId, projection) {
+
+
+ function closestIndex(nodes, loc) {
+ var idx, min = Infinity, dist;
+ for (var i = 0; i < nodes.length; i++) {
+ dist = iD.geo.dist(nodes[i].loc, loc);
+ if (dist < min) {
+ min = dist;
+ idx = i;
+ }
+ }
+ return idx;
+ }
+
+ // Handles two corner cases
+ //
+ // 1. Reuse as many old nodes as possible
+ // 2. Don't move or eliminate any nodes that have more than one
+ // parent way.
+ var action = function(graph) {
+
+ // The equivalent of zoom 18: (256 << 18)
+ var fixedproj = d3.geo.mercator().scale(67108864);
+
+ var way = graph.entity(wayId),
+ nodes = graph.childNodes(way),
+ node, i, j, ids = [], idx,
+ singleParent = [], multiParent = [];
+
+ for (i = 0; i < nodes.length; i++) {
+ if (graph.parentWays(nodes[i]).length === 1) singleParent.push(nodes[i]);
+ else multiParent.push(nodes[i]);
+ }
+
+ // all points that have a single way parent
+ var points = singleParent.map(function(n) {
+ // simplify.js accepts {x,y} objects.
+ var p = fixedproj(n.loc);
+ return { x: p[0], y: p[1] };
+ });
+
+ // tolerance of 0.8 - adjust as needed. simplification is guaranteed
+ // to produce fewer points in output than input
+ var simplified = simplify(points, 0.7).map(function(p) {
+ // convert back to iD's 2-elem array pattern
+ return { loc: fixedproj.invert([p.x, p.y]) };
+ });
+
+ // first reuse all singleParent nodes. the
+ // ones not reused will be deleted
+ for (i = 0; i < simplified.length; i++) {
+ // reuse nodes for single parent nodes
+ idx = closestIndex(singleParent, simplified[i].loc);
+ node = singleParent[idx];
+ singleParent.splice(idx, 1);
+ graph = graph.replace(node.move(simplified[i].loc));
+ ids.push(node.id);
+ }
+
+ // then insert all multiParent nodes
+ for (i = 0; i < multiParent.length; i++) {
+ idx = closestIndex(simplified, multiParent[i].loc);
+ ids.splice(idx, 0, multiParent[i].id);
+ }
+
+ graph = graph.replace(way.update({ nodes: ids }));
+
+ // remove all single parent nodes that were not reused earlier
+ for (i = 0; i < singleParent.length; i++) {
+ graph = iD.actions.DeleteNode(singleParent[i].id)(graph);
+ }
+
+ return graph;
+ };
+
+ action.enabled = function(graph) {
+ return true;
+ };
+
+ return action;
+};
View
25 js/id/operations/simplify.js
@@ -0,0 +1,25 @@
+iD.operations.Simplify = function(selection, context) {
+ var entityId = selection[0],
+ action = iD.actions.Simplify(entityId, context.projection);
+
+ var operation = function() {
+ var annotation = t('operations.simplify.annotation.' + context.geometry(entityId));
+ context.perform(action, annotation);
+ };
+
+ operation.available = function() {
+ return selection.length === 1 &&
+ context.entity(entityId).type === 'way';
+ };
+
+ operation.enabled = function() {
+ return action.enabled(context.graph());
+ };
+
+ operation.id = "simplify";
+ operation.keys = [t('operations.simplify.key')];
+ operation.title = t('operations.simplify.title');
+ operation.description = t('operations.simplify.description');
+
+ return operation;
+};
View
181 js/lib/simplify.js
@@ -0,0 +1,181 @@
+/*
+ Copyright (c) 2012, Vladimir Agafonkin
+ Simplify.js is a high-performance polyline simplification library
+ mourner.github.com/simplify-js
+*/
+
+(function (global, undefined) {
+
+ "use strict";
+
+
+ // to suit your point format, run search/replace for '.x' and '.y'
+ // to switch to 3D, uncomment the lines in the next 2 functions
+ // (configurability would draw significant performance overhead)
+
+
+ function getSquareDistance(p1, p2) { // square distance between 2 points
+
+ var dx = p1.x - p2.x,
+ // dz = p1.z - p2.z,
+ dy = p1.y - p2.y;
+
+ return dx * dx +
+ // dz * dz +
+ dy * dy;
+ }
+
+ function getSquareSegmentDistance(p, p1, p2) { // square distance from a point to a segment
+
+ var x = p1.x,
+ y = p1.y,
+ // z = p1.z,
+
+ dx = p2.x - x,
+ dy = p2.y - y,
+ // dz = p2.z - z,
+
+ t;
+
+ if (dx !== 0 || dy !== 0) {
+
+ t = ((p.x - x) * dx +
+ // (p.z - z) * dz +
+ (p.y - y) * dy) /
+ (dx * dx +
+ // dz * dz +
+ dy * dy);
+
+ if (t > 1) {
+ x = p2.x;
+ y = p2.y;
+ // z = p2.z;
+
+ } else if (t > 0) {
+ x += dx * t;
+ y += dy * t;
+ // z += dz * t;
+ }
+ }
+
+ dx = p.x - x;
+ dy = p.y - y;
+ // dz = p.z - z;
+
+ return dx * dx +
+ // dz * dz +
+ dy * dy;
+ }
+
+ // the rest of the code doesn't care for the point format
+
+
+ function simplifyRadialDistance(points, sqTolerance) { // distance-based simplification
+
+ var i,
+ len = points.length,
+ point,
+ prevPoint = points[0],
+ newPoints = [prevPoint];
+
+ for (i = 1; i < len; i++) {
+ point = points[i];
+
+ if (getSquareDistance(point, prevPoint) > sqTolerance) {
+ newPoints.push(point);
+ prevPoint = point;
+ }
+ }
+
+ if (prevPoint !== point) {
+ newPoints.push(point);
+ }
+
+ return newPoints;
+ }
+
+
+ // simplification using optimized Douglas-Peucker algorithm with recursion elimination
+
+ function simplifyDouglasPeucker(points, sqTolerance) {
+
+ var len = points.length,
+
+ MarkerArray = (typeof Uint8Array !== undefined + '')
+ ? Uint8Array
+ : Array,
+
+ markers = new MarkerArray(len),
+
+ first = 0,
+ last = len - 1,
+
+ i,
+ maxSqDist,
+ sqDist,
+ index,
+
+ firstStack = [],
+ lastStack = [],
+
+ newPoints = [];
+
+ markers[first] = markers[last] = 1;
+
+ while (last) {
+
+ maxSqDist = 0;
+
+ for (i = first + 1; i < last; i++) {
+ sqDist = getSquareSegmentDistance(points[i], points[first], points[last]);
+
+ if (sqDist > maxSqDist) {
+ index = i;
+ maxSqDist = sqDist;
+ }
+ }
+
+ if (maxSqDist > sqTolerance) {
+ markers[index] = 1;
+
+ firstStack.push(first);
+ lastStack.push(index);
+
+ firstStack.push(index);
+ lastStack.push(last);
+ }
+
+ first = firstStack.pop();
+ last = lastStack.pop();
+ }
+
+ for (i = 0; i < len; i++) {
+ if (markers[i]) {
+ newPoints.push(points[i]);
+ }
+ }
+
+ return newPoints;
+ }
+
+
+ var root = (typeof exports !== undefined + '')
+ ? exports
+ : global;
+
+
+ root.simplify = function (points, tolerance, highestQuality) {
+
+ var sqTolerance = (tolerance !== undefined)
+ ? tolerance * tolerance
+ : 1;
+
+ if (!highestQuality) {
+ points = simplifyRadialDistance(points, sqTolerance);
+ }
+ points = simplifyDouglasPeucker(points, sqTolerance);
+
+ return points;
+ };
+
+}(this));
View
9 locale/en.js
@@ -70,6 +70,15 @@ locale.en = {
area: "Squared the corners of an area."
}
},
+ simplify: {
+ title: "Simplify",
+ description: "Simplify this shape",
+ key: "A",
+ annotation: {
+ line: "Simplified a line",
+ area: "Simplified an area"
+ }
+ },
'delete': {
title: "Delete",
description: "Remove this from the map.",

0 comments on commit f057710

Please sign in to comment.