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