Merge branch 'master' into history
[potlatch2.git] / net / systemeD / potlatch2 / tools / Simplify.as
1 package net.systemeD.potlatch2.tools {
2         import net.systemeD.halcyon.Map;
3         import net.systemeD.halcyon.connection.CompositeUndoableAction;
4         import net.systemeD.halcyon.connection.Way;
5         import net.systemeD.halcyon.connection.Node;
6         import net.systemeD.halcyon.connection.MainUndoStack;
7         import flash.net.SharedObject;
8
9         /** Tool to reduce the number of nodes in a way by filtering out the "least important" ones, using the Douglas-Peucker algorithm. */
10         public class Simplify {
11
12                 /** Carries out simplification on a way, adding an entry to global undo stack.
13                  * @param way Way to be simplified.
14                  * @param map Map it belongs to, for computing offscreen-ness.
15                  * @param keepOffscreen If true, don't delete any nodes that are not currently visible. 
16                  * @param tolerance Curve tolerance.
17                  * */
18
19         /* FIXME this should take an action, and push the work onto that. Simplify is called from various places
20         * so shouldn't be adding to the global undo stack */
21                   
22                 public static function simplify(way:Way, map:Map, keepOffscreen:Boolean, tolerance:Number=NaN):void {
23                         if (way.length<3) { return; }
24                         if (isNaN(tolerance)) {
25                                 if (SharedObject.getLocal("user_state").data['simplify_tolerance']!=undefined) {
26                                         tolerance=Number(SharedObject.getLocal("user_state").data['simplify_tolerance']);
27                                 } else {
28                                         tolerance=0.00005;
29                                 }
30                         }
31
32                         var action:CompositeUndoableAction = new CompositeUndoableAction("Simplify");
33                         
34                         var xa:Number, xb:Number;
35                         var ya:Number, yb:Number;
36                         var l:Number, d:Number, i:uint;
37                         var furthest:uint, furthdist:Number, float:Number;
38                         var n:Node;
39                         
40                         var tokeep:Object={};
41                         var stack:Array=[way.length-1];
42                         var anchor:uint=0;
43                         var todelete:Array=[];
44                 
45                         // Douglas-Peucker
46                         while (stack.length) {
47                                 float=stack[stack.length-1];
48                                 furthest=0; furthdist=0;
49                                 xa=way.getNode(anchor).lon ; xb=way.getNode(float).lon ;
50                                 ya=way.getNode(anchor).latp; yb=way.getNode(float).latp;
51                                 l=Math.sqrt((xb-xa)*(xb-xa)+(yb-ya)*(yb-ya));
52         
53                                 // find furthest-out point
54                                 for (i=anchor+1; i<float; i+=1) {
55                                         d=getDistance(xa,ya,xb,yb,l,way.getNode(i).lon,way.getNode(i).latp);
56                                         if (d>furthdist && d>tolerance) { furthest=i; furthdist=d; }
57                                 }
58                         
59                                 if (furthest==0) {
60                                         anchor=stack.pop();
61                                         tokeep[way.getNode(float).id]=true;
62                                 } else {
63                                         stack.push(furthest);
64                                 }
65                         }
66                         
67                         // Delete unwanted nodes, unless they're tagged or junction nodes
68                         for (i=1; i<way.length; i++) {
69                                 n=way.getNode(i)
70                                 if (tokeep[n.id] || n.hasTags() || n.parentWays.length>1 ||
71                                     (keepOffscreen && (n.lon<map.edge_l || n.lon>map.edge_r || n.lat<map.edge_b || n.lat>map.edge_t )) ) {
72                                         // keep it
73                                 } else {
74                                         // delete it
75                                         todelete.push(n);
76                                 }
77                         }
78                         for each (n in todelete) { n.remove(action.push); }
79                         MainUndoStack.getGlobalStack().addAction(action);
80                 }
81                 
82                 private static function getDistance(ax:Number,ay:Number,bx:Number,by:Number,l:Number,cx:Number,cy:Number):Number {
83                         // l=length of line
84                         // r=proportion along AB line (0-1) of nearest point
85                         var r:Number;
86                         if (l > 0) {
87                                 r=((cx-ax)*(bx-ax)+(cy-ay)*(by-ay))/(l*l);
88                         } else {
89                                 r=0;
90                         }
91                         // now find the length from cx,cy to ax+r*(bx-ax),ay+r*(by-ay)
92                         var px:Number=(ax+r*(bx-ax)-cx);
93                         var py:Number=(ay+r*(by-ay)-cy);
94                         return Math.sqrt(px*px+py*py);
95                 }
96
97         }
98 }