First version of quadrilateralise function for PL2. Needs better error handling.

diff --git a/net/systemeD/potlatch2/controller/SelectedWay.as b/net/systemeD/potlatch2/controller/SelectedWay.as
index 217bf11..b4c5c94 100644 (file)
--- a/net/systemeD/potlatch2/controller/SelectedWay.as
+++ b/net/systemeD/potlatch2/controller/SelectedWay.as
@@ -1,6 +1,7 @@
 package net.systemeD.potlatch2.controller {
        import flash.events.*;
     import net.systemeD.potlatch2.EditController;
+    import net.systemeD.potlatch2.tools.Quadrilateralise;
     import net.systemeD.halcyon.connection.*;
        import net.systemeD.halcyon.Globals;
 
@@ -70,6 +71,17 @@ package net.systemeD.potlatch2.controller {
             return this;
         }
         
+       override public function processKeyboardEvent(event:KeyboardEvent):ControllerState {
+         if (event.keyCode == 81) { // 'q' or 'Q'
+           var success:Boolean = Quadrilateralise.quadrilateralise(selectedWay);
+           if (!success) {
+             trace("Quadrilateralise failed.");
+           }
+         }
+
+         return this;
+       }
+
         protected function addNode(event:MouseEvent):Node {
             trace("add node");
             var lat:Number = controller.map.coord2lat(event.localY);

diff --git a/net/systemeD/potlatch2/tools/Quadrilateralise.as b/net/systemeD/potlatch2/tools/Quadrilateralise.as
new file mode 100644 (file)
index 0000000..568c484
--- /dev/null
+++ b/net/systemeD/potlatch2/tools/Quadrilateralise.as
@@ -0,0 +1,120 @@
+package net.systemeD.potlatch2.tools {
+  import net.systemeD.halcyon.connection.Way;
+  import net.systemeD.halcyon.connection.Node;
+  import flash.geom.Point;
+
+  public class Quadrilateralise {
+    const NUM_STEPS:uint = 1000;
+    const TOLERANCE:Number = 1.0e-8;
+
+    /**
+     * Attempts to make all corners of a way right angles. Returns true if it
+     * thought it was successful and false if it failed. If it fails it does not
+     * modify the way.
+     */
+    public static function quadrilateralise(way:Way):Boolean {
+      // needs a closed way to work properly.
+      if (!way.isArea()) {
+       return false;
+      }
+
+      var functor:Quadrilateralise = new Quadrilateralise(way);
+      var score:Number = functor.goodness;
+      for (var i:uint = 0; i < NUM_STEPS; ++i) {
+       functor.step();
+       var newScore:Number = functor.goodness;
+       if (newScore > score) {
+         trace("Quadrilateralise blew up! " + newScore + " > " + score);
+         return false;
+       }
+       score = newScore;
+       if (score < TOLERANCE) {
+         break;
+       }
+      }
+
+      functor.updateWay();
+      return true;
+    }
+
+    private var way:Way;
+    private var points:Array;
+    
+    // i wanted this to be private, but AS3 doesn't allow that. so please don't use it outside this package!
+    public function Quadrilateralise(way_:Way) {
+      way = way_;
+      points = way.sliceNodes(0, way.length - 1).map(function (n:Node, i:int, a:Array) : Point {
+         return new Point(n.lon, n.latp);
+       });
+    }
+
+    /**
+     * returns the score of a particular corner, which is constructed so that all corners
+     * which are straight lines or 90-degree corners score close to zero and other angles
+     * score higher. The goal of this action is to minimise the sum of all scores.
+     */
+    private function scoreOf(a:Point, b:Point, c:Point):Number {
+      var p:Point = a.subtract(b);
+      var q:Point = c.subtract(b);
+      p.normalize(1.0);
+      q.normalize(1.0);
+      var dotp:Number = p.x*q.x + p.y*q.y;
+      // score is constructed so that +1, -1 and 0 are all scored 0, any other angle
+      // is scored higher.
+      var score:Number = 2.0 * Math.min(Math.abs(dotp-1.0), Math.min(Math.abs(dotp), Math.abs(dotp+1)));
+      return score;
+    }
+
+    // get the goodness (sum of scores) of the whole way.
+    private function get goodness():Number {
+      var g:Number = 0.0;
+      for (var i:uint = 1; i < points.length - 1; ++i) {
+       var score:Number = scoreOf(points[i-1], points[i], points[i+1]);
+       g += score;
+      }
+      var startScore:Number = scoreOf(points[points.length-1], points[0], points[1]);
+      var endScore:Number = scoreOf(points[points.length-2], points[points.length-1], points[0]);
+      g += startScore;
+      g += endScore;
+      return g;
+    }
+
+    /**
+     * One step of the solver. Moves points towards their neighbours, or away from them, depending on 
+     * the angle of that corner.
+     */
+    private function step():void {
+      var motions:Array = points.map(function (b:Point, i:int, array:Array) : Point {
+         var a:Point = array[(i-1+array.length) % array.length];
+         var c:Point = array[(i+1) % array.length];
+         var p:Point = a.subtract(b);
+         var q:Point = c.subtract(b);
+         var scale:Number = p.length + q.length;
+         p.normalize(1.0);
+         q.normalize(1.0);
+         var dotp:Number = p.x*q.x + p.y*q.y;
+         // nasty hack to deal with almost-straight segments (angle is closer to 180 than to 90/270).
+         if (dotp < -0.707106781186547) {
+           dotp += 1.0;
+         }
+         var v:Point = p.add(q);
+         v.normalize(0.1 * dotp * scale);
+         return v;
+       });
+      for (var i:uint = 0; i < motions.length; ++i) {
+       points[i] = points[i].add(motions[i]);
+      }
+    }
+
+    /**
+     * call this only when happy with the result - it writes the positions back to the
+     * way, and hence to the DB or whatever.
+     */
+    private function updateWay():void {
+      for (var i:uint = 0; i < points.length; ++i) {
+       way.getNode(i).lon = points[i].x;
+       way.getNode(i).latp = points[i].y;
+      }
+    }
+  }
+}