3ddeb2207695e39cd528ab2f87259feba9f6f872
[potlatch2.git] / net / systemeD / potlatch2 / tools / Quadrilateralise.as
1 package net.systemeD.potlatch2.tools {
2   import net.systemeD.halcyon.connection.Way;
3   import net.systemeD.halcyon.connection.Node;
4   import flash.geom.Point;
5   import net.systemeD.halcyon.connection.*;
6
7   /** Tool to transform a closed way by making corners right-angled, if possible. Call the static function quadrilateralise(). */
8   public class Quadrilateralise {
9     private static const NUM_STEPS:uint = 1000;
10     private static const TOLERANCE:Number = 1.0e-8;
11
12     /**
13      * Attempts to make all corners of a way right angles. Returns true if it
14      * thought it was successful and false if it failed. If it fails it does not
15      * modify the way.
16      * @param way Way to be transformed.
17      * @performAction Function that will be passed a CompositeUndoableAction parameter representing the transformation.
18      */
19     public static function quadrilateralise(way:Way,performAction:Function):Boolean {
20       // needs a closed way to work properly.
21       if (!way.isArea()) {
22         return false;
23       }
24
25       var functor:Quadrilateralise = new Quadrilateralise(way,performAction);
26       var score:Number = functor.goodness;
27       for (var i:uint = 0; i < NUM_STEPS; ++i) {
28         functor.step();
29         var newScore:Number = functor.goodness;
30         if (newScore > score) {
31           trace("Quadrilateralise blew up! " + newScore + " > " + score);
32           return false;
33             }
34         score = newScore;
35         if (score < TOLERANCE) {
36         break;
37         }
38       }
39
40       functor.updateWay();
41       return true;
42     }
43
44     private var way:Way;
45     private var points:Array;
46     private var performAction:Function;
47     
48     /** Private function that had to be declared public - do not call from outside this package. */
49     public function Quadrilateralise(way_:Way, performAction_:Function) {
50       way = way_;
51       performAction = performAction_;
52       points = way.sliceNodes(0, way.length - 1).map(function (n:Node, i:int, a:Array) : Point {
53           return new Point(n.lon, n.latp);
54         });
55     }
56
57     /**
58      * returns the score of a particular corner, which is constructed so that all corners
59      * which are straight lines or 90-degree corners score close to zero and other angles
60      * score higher. The goal of this action is to minimise the sum of all scores.
61      */
62     private function scoreOf(a:Point, b:Point, c:Point):Number {
63       var p:Point = a.subtract(b);
64       var q:Point = c.subtract(b);
65       p.normalize(1.0);
66       q.normalize(1.0);
67       var dotp:Number = p.x*q.x + p.y*q.y;
68       // score is constructed so that +1, -1 and 0 are all scored 0, any other angle
69       // is scored higher.
70       var score:Number = 2.0 * Math.min(Math.abs(dotp-1.0), Math.min(Math.abs(dotp), Math.abs(dotp+1)));
71       return score;
72     }
73
74     // get the goodness (sum of scores) of the whole way.
75     private function get goodness():Number {
76       var g:Number = 0.0;
77       for (var i:uint = 1; i < points.length - 1; ++i) {
78         var score:Number = scoreOf(points[i-1], points[i], points[i+1]);
79         g += score;
80       }
81       var startScore:Number = scoreOf(points[points.length-1], points[0], points[1]);
82       var endScore:Number = scoreOf(points[points.length-2], points[points.length-1], points[0]);
83       g += startScore;
84       g += endScore;
85       return g;
86     }
87
88     /**
89      * One step of the solver. Moves points towards their neighbours, or away from them, depending on 
90      * the angle of that corner.
91      */
92     private function step():void {
93       var motions:Array = points.map(function (b:Point, i:int, array:Array) : Point {
94           var a:Point = array[(i-1+array.length) % array.length];
95           var c:Point = array[(i+1) % array.length];
96           var p:Point = a.subtract(b);
97           var q:Point = c.subtract(b);
98           var scale:Number = p.length + q.length;
99           p.normalize(1.0);
100           q.normalize(1.0);
101           var dotp:Number = p.x*q.x + p.y*q.y;
102           // nasty hack to deal with almost-straight segments (angle is closer to 180 than to 90/270).
103           if (dotp < -0.707106781186547) {
104             dotp += 1.0;
105           }
106           var v:Point = p.add(q);
107           v.normalize(0.1 * dotp * scale);
108           return v;
109         });
110       for (var i:uint = 0; i < motions.length; ++i) {
111         points[i] = points[i].add(motions[i]);
112       }
113     }
114
115     /**
116      * call this only when happy with the result - it writes the positions back to the
117      * way, and hence to the DB or whatever.
118      */
119     private function updateWay():void {
120       var moveAction:CompositeUndoableAction = new CompositeUndoableAction("Move Way");
121       for (var i:uint = 0; i < points.length; ++i) {
122         way.getNode(i).setLonLatp( points[i].x, points[i].y, moveAction.push);
123       }
124       performAction(moveAction);
125     }
126   }
127 }