From 73871f14ed0cd3fb7bd5e5a6afc8be24dc913201 Mon Sep 17 00:00:00 2001
From: Richard Fairhurst <richard@systemed.net>
Date: Fri, 14 May 2010 16:43:35 +0000
Subject: [PATCH] add a Douglas-Peucker simplify action (currently accessed by
 a keypress, but will be more useful in conjunction with vector background
 layers)

---
 .../potlatch2/controller/SelectedWay.as       |  2 +
 net/systemeD/potlatch2/tools/Simplify.as      | 76 +++++++++++++++++++
 2 files changed, 78 insertions(+)
 create mode 100644 net/systemeD/potlatch2/tools/Simplify.as

diff --git a/net/systemeD/potlatch2/controller/SelectedWay.as b/net/systemeD/potlatch2/controller/SelectedWay.as
index f0b2c706..776b2d06 100644
--- a/net/systemeD/potlatch2/controller/SelectedWay.as
+++ b/net/systemeD/potlatch2/controller/SelectedWay.as
@@ -4,6 +4,7 @@ package net.systemeD.potlatch2.controller {
 	import flash.ui.Keyboard;
     import net.systemeD.potlatch2.EditController;
     import net.systemeD.potlatch2.tools.Quadrilateralise;
+    import net.systemeD.potlatch2.tools.Simplify;
     import net.systemeD.halcyon.connection.*;
 	import net.systemeD.halcyon.MapPaint;
 	import net.systemeD.halcyon.Globals;
@@ -61,6 +62,7 @@ package net.systemeD.potlatch2.controller {
 			switch (event.keyCode) {
 				case 81:					Quadrilateralise.quadrilateralise(selectedWay); return this;
                 case 82:                    selectedWay.reverseNodes(MainUndoStack.getGlobalStack().addAction); return this;         
+                case 89:                    Simplify.simplify(selectedWay, controller.map, true); return this;         
 				case Keyboard.BACKSPACE:	if (event.shiftKey) { return deleteWay(); } break;
 				case Keyboard.DELETE:		if (event.shiftKey) { return deleteWay(); } break;
 			}
diff --git a/net/systemeD/potlatch2/tools/Simplify.as b/net/systemeD/potlatch2/tools/Simplify.as
new file mode 100644
index 00000000..009b01b1
--- /dev/null
+++ b/net/systemeD/potlatch2/tools/Simplify.as
@@ -0,0 +1,76 @@
+package net.systemeD.potlatch2.tools {
+	import net.systemeD.halcyon.Map;
+	import net.systemeD.halcyon.connection.CompositeUndoableAction;
+	import net.systemeD.halcyon.connection.Way;
+	import net.systemeD.halcyon.connection.Node;
+	import net.systemeD.halcyon.connection.MainUndoStack;
+
+	public class Simplify {
+
+		private static const TOLERANCE:Number=0.00005;
+
+		public static function simplify(way:Way, map:Map, keepOffscreen:Boolean):void {
+			if (way.length<3 || way.isArea()) { return; }
+
+			var action:CompositeUndoableAction = new CompositeUndoableAction("Straighten");
+			
+			var xa:Number, xb:Number;
+			var ya:Number, yb:Number;
+			var l:Number, d:Number, i:uint;
+			var furthest:uint, furthdist:Number, float:Number;
+			var n:Node;
+			
+			var tokeep:Object={};
+			var stack:Array=[way.length-1];
+			var anchor:uint=0;
+			var todelete:Array=[];
+		
+			// Douglas-Peucker
+			while (stack.length) {
+				float=stack[stack.length-1];
+				furthest=0; furthdist=0;
+				xa=way.getNode(anchor).lon ; xb=way.getNode(float).lon ;
+				ya=way.getNode(anchor).latp; yb=way.getNode(float).latp;
+				l=Math.sqrt((xb-xa)*(xb-xa)+(yb-ya)*(yb-ya));
+	
+				// find furthest-out point
+				for (i=anchor+1; i<float; i+=1) {
+					d=getDistance(xa,ya,xb,yb,l,way.getNode(i).lon,way.getNode(i).latp);
+					if (d>furthdist && d>TOLERANCE) { furthest=i; furthdist=d; }
+				}
+			
+				if (furthest==0) {
+					anchor=stack.pop();
+					tokeep[way.getNode(float).id]=true;
+				} else {
+					stack.push(furthest);
+				}
+			}
+			
+			// Delete unwanted nodes, unless they're tagged or junction nodes
+			for (i=1; i<way.length; i++) {
+				n=way.getNode(i)
+				if (tokeep[n.id] || n.hasTags() || n.parentWays.length>1 ||
+				    (keepOffscreen && (n.lon<map.edge_l || n.lon>map.edge_r || n.lat<map.edge_b || n.lat>map.edge_t )) ) {
+					// keep it
+				} else {
+					// delete it
+					todelete.push(n);
+				}
+			}
+			for each (n in todelete) { n.remove(action.push); }
+			MainUndoStack.getGlobalStack().addAction(action);
+		}
+		
+		private static function getDistance(ax:Number,ay:Number,bx:Number,by:Number,l:Number,cx:Number,cy:Number):Number {
+			// l=length of line
+			// r=proportion along AB line (0-1) of nearest point
+			var r:Number=((cx-ax)*(bx-ax)+(cy-ay)*(by-ay))/(l*l);
+			// now find the length from cx,cy to ax+r*(bx-ax),ay+r*(by-ay)
+			var px:Number=(ax+r*(bx-ax)-cx);
+			var py:Number=(ay+r*(by-ay)-cy);
+			return Math.sqrt(px*px+py*py);
+		}
+
+	}
+}
-- 
2.36.1