Want more features on Pastebin? Sign Up, it's FREE!
Guest

Untitled

By: a guest on Dec 2nd, 2012  |  syntax: None  |  size: 4.78 KB  |  views: 35  |  expires: Never
download  |  raw  |  embed  |  report abuse  |  print
Text below is selected. Please press Ctrl+C to copy to your clipboard. (⌘+C on Mac)
  1. package;
  2.  
  3. typedef Point = { x:Float, y:Float };
  4. typedef Line = { a:Point, b:Point };
  5. typedef Vertex = { p:Point, diagonals:Array<Vertex> };
  6.  
  7. class Main {
  8.     static function main() {
  9.         // input =
  10.         //
  11.         //  o---o---o
  12.         //      |'o'|
  13.         //      o'-'o
  14.         //
  15.         var points = [ { x:0.0, y:0.0 },
  16.                        { x:1.0, y:0.0 },
  17.                        { x:1.0, y:1.0 },
  18.                        { x:0.0, y:1.0 },
  19.                        { x:0.5, y:0.5 },
  20.                        { x:-1.0, y:0.0 }
  21.         ];
  22.         var lines = [ { a:points[0], b:points[1] },
  23.                       { a:points[1], b:points[2] },
  24.                       { a:points[2], b:points[3] },
  25.                       { a:points[3], b:points[0] },
  26.                       { a:points[0], b:points[4] },
  27.                       { a:points[1], b:points[4] },
  28.                       { a:points[2], b:points[4] },
  29.                       { a:points[3], b:points[4] },
  30.                       { a:points[0], b:points[5] }
  31.         ];
  32.  
  33.         var exterior = exteriorPolygon(points, lines);
  34.         // result =
  35.         //
  36.         //   o---#---o
  37.         //       |   |
  38.         //       o---o
  39.         //
  40.         // with the # vertex correctly duplicated.
  41.  
  42.         trace(Std.string(points));
  43.         trace(Std.string(lines));
  44.         trace(Std.string(exterior));
  45.     }
  46.  
  47.     // return -1 if (a -> b -> c) is a left turn
  48.     //         0 if (a -> b -> c) collinear
  49.     //         1 if (a -> b -> c) is a right turn
  50.     //
  51.     // this presumes a y-axis pointing down for meanings
  52.     // of left and right turn.
  53.     static function orient(a:Point, b:Point, c:Point) {
  54.         var ux = a.x - b.x;
  55.         var uy = a.y - b.y;
  56.         var vx = c.x - b.x;
  57.         var vy = c.y - b.y;
  58.         var perpdot = (ux * vy) - (uy * vx);
  59.         return if (perpdot > 0) -1 else if (perpdot == 0) 0 else 1;
  60.     }
  61.  
  62.     static function exteriorPolygon(points:Array<Point>, lines:Array<Line>) {
  63.         // Transform points/lines to vertices.
  64.         var vertices = [];
  65.         for (p in points) {
  66.             vertices.push({ p:p, diagonals: [] });
  67.         }
  68.         for (i in 0...points.length) {
  69.             var p = points[i];
  70.             var v = vertices[i];
  71.             for (ab in lines) {
  72.                 function vertex(p:Point):Vertex {
  73.                     for (j in 0...points.length) {
  74.                         if (points[j] == p) return vertices[j];
  75.                     }
  76.                     return null;
  77.                 }
  78.                 if (ab.b == p) v.diagonals.push(vertex(ab.a));
  79.                 if (ab.a == p) v.diagonals.push(vertex(ab.b));
  80.             }
  81.         }
  82.  
  83.         // Find start point of exterior.
  84.         var minimum = vertices[0];
  85.         for (i in 1...vertices.length) {
  86.             var v = vertices[i];
  87.  
  88.             if (v.p.x < minimum.p.x || (v.p.x == minimum.p.x && v.p.y < minimum.p.y)) {
  89.                 minimum = v;
  90.             }
  91.         }
  92.  
  93.         // Traverse exterior.
  94.         var exterior = [];
  95.  
  96.         // Seed start-direction with a fake previous point.
  97.         var current = minimum;
  98.         var previous = { x:current.p.x - 1, y:current.p.y };
  99.         do {
  100.             exterior.push(current.p);
  101.  
  102.             // Find next point along exterior.
  103.             var next = current.diagonals[0];
  104.             var d1 = orient(previous, current.p, next.p);
  105.             for (i in 1...current.diagonals.length) {
  106.                 var q = current.diagonals[i];
  107.                 var d2 = orient(previous, current.p, q.p);
  108.  
  109.                 if (d1 * d2 == 1
  110.                 || (d1 * d2 == 0 && (d1 == 1 || d2 == 1))) {
  111.                     if (orient(next.p, current.p, q.p) == 1) {
  112.                         next = q;
  113.                         d1 = d2;
  114.                     }
  115.                 }
  116.                 else if (d1 == -1 || d2 == -1) {
  117.                     if (d2 == -1) {
  118.                         next = q;
  119.                         d1 = d2;
  120.                     }
  121.                 }
  122.                 else if (d1 == 0 && d2 == 0) {
  123.                     var ax = current.p.x - previous.x;
  124.                     var ay = current.p.y - previous.y;
  125.                     var ux = next.p.x - current.p.x;
  126.                     var uy = next.p.y - current.p.y;
  127.                     var vx = q.p.x - current.p.x;
  128.                     var vy = q.p.y - current.p.y;
  129.  
  130.                     var dot1 = (ax * ux) + (ay * uy);
  131.                     var dot2 = (ax * vx) + (ay * vy);
  132.  
  133.                     if (dot1 < 0 && dot2 > 0) {
  134.                         next = q;
  135.                         d1 = d2;
  136.                     }
  137.                 }
  138.             }
  139.  
  140.             previous = current.p;
  141.             current = next;
  142.         }
  143.         while (current != minimum);
  144.  
  145.         return exterior;
  146.     }
  147. }
clone this paste RAW Paste Data