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
   6   public class Quadrilateralise {
   7     const NUM_STEPS:uint = 1000;
   8     const TOLERANCE:Number = 1.0e-8;
   9
  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       }
  20
  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       }
  35
  36       functor.updateWay();
  37       return true;
  38     }
  39
  40     private var way:Way;
  41     private var points:Array;
  42
  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     }
  50
  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     }
  67
  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[0], points[1]);
  76       var endScore:Number = scoreOf(points[points.length-2], points[points.length-1], points[0]);
  77       g += startScore;
  78       g += endScore;
  79       return g;
  80     }
  81
  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     }
 108
 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 }