Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- package;
- typedef Point = { x:Float, y:Float };
- typedef Line = { a:Point, b:Point };
- typedef Vertex = { p:Point, diagonals:Array<Vertex> };
- class Main {
- static function main() {
- // input =
- //
- // o---o---o
- // |'o'|
- // o'-'o
- //
- var points = [ { x:0.0, y:0.0 },
- { x:1.0, y:0.0 },
- { x:1.0, y:1.0 },
- { x:0.0, y:1.0 },
- { x:0.5, y:0.5 },
- { x:-1.0, y:0.0 }
- ];
- var lines = [ { a:points[0], b:points[1] },
- { a:points[1], b:points[2] },
- { a:points[2], b:points[3] },
- { a:points[3], b:points[0] },
- { a:points[0], b:points[4] },
- { a:points[1], b:points[4] },
- { a:points[2], b:points[4] },
- { a:points[3], b:points[4] },
- { a:points[0], b:points[5] }
- ];
- var exterior = exteriorPolygon(points, lines);
- // result =
- //
- // o---#---o
- // | |
- // o---o
- //
- // with the # vertex correctly duplicated.
- trace(Std.string(points));
- trace(Std.string(lines));
- trace(Std.string(exterior));
- }
- // return -1 if (a -> b -> c) is a left turn
- // 0 if (a -> b -> c) collinear
- // 1 if (a -> b -> c) is a right turn
- //
- // this presumes a y-axis pointing down for meanings
- // of left and right turn.
- static function orient(a:Point, b:Point, c:Point) {
- var ux = a.x - b.x;
- var uy = a.y - b.y;
- var vx = c.x - b.x;
- var vy = c.y - b.y;
- var perpdot = (ux * vy) - (uy * vx);
- return if (perpdot > 0) -1 else if (perpdot == 0) 0 else 1;
- }
- static function exteriorPolygon(points:Array<Point>, lines:Array<Line>) {
- // Transform points/lines to vertices.
- var vertices = [];
- for (p in points) {
- vertices.push({ p:p, diagonals: [] });
- }
- for (i in 0...points.length) {
- var p = points[i];
- var v = vertices[i];
- for (ab in lines) {
- function vertex(p:Point):Vertex {
- for (j in 0...points.length) {
- if (points[j] == p) return vertices[j];
- }
- return null;
- }
- if (ab.b == p) v.diagonals.push(vertex(ab.a));
- if (ab.a == p) v.diagonals.push(vertex(ab.b));
- }
- }
- // Find start point of exterior.
- var minimum = vertices[0];
- for (i in 1...vertices.length) {
- var v = vertices[i];
- if (v.p.x < minimum.p.x || (v.p.x == minimum.p.x && v.p.y < minimum.p.y)) {
- minimum = v;
- }
- }
- // Traverse exterior.
- var exterior = [];
- // Seed start-direction with a fake previous point.
- var current = minimum;
- var previous = { x:current.p.x - 1, y:current.p.y };
- do {
- exterior.push(current.p);
- // Find next point along exterior.
- var next = current.diagonals[0];
- var d1 = orient(previous, current.p, next.p);
- for (i in 1...current.diagonals.length) {
- var q = current.diagonals[i];
- var d2 = orient(previous, current.p, q.p);
- if (d1 * d2 == 1
- || (d1 * d2 == 0 && (d1 == 1 || d2 == 1))) {
- if (orient(next.p, current.p, q.p) == 1) {
- next = q;
- d1 = d2;
- }
- }
- else if (d1 == -1 || d2 == -1) {
- if (d2 == -1) {
- next = q;
- d1 = d2;
- }
- }
- else if (d1 == 0 && d2 == 0) {
- var ax = current.p.x - previous.x;
- var ay = current.p.y - previous.y;
- var ux = next.p.x - current.p.x;
- var uy = next.p.y - current.p.y;
- var vx = q.p.x - current.p.x;
- var vy = q.p.y - current.p.y;
- var dot1 = (ax * ux) + (ay * uy);
- var dot2 = (ax * vx) + (ay * vy);
- if (dot1 < 0 && dot2 > 0) {
- next = q;
- d1 = d2;
- }
- else {
- // Means we have two diagonals that are collinear and in same direction.
- break;
- }
- }
- }
- previous = current.p;
- current = next;
- }
- while (current != minimum);
- return exterior;
- }
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement