Convex hull: Difference between revisions

Content added Content deleted

Inline

@@ Line 1,280: / Line 1,280: @@
 <pre>Convex Hull (7 points): [(-3, -9) (19, -8) (17, 5) (12, 17) (5, 19) (-3, 15) (-9, -3)]
 Convex Hull (9 points): [(-3, -9) (1, -9) (14, -9) (19, -8) (17, 5) (12, 17) (5, 19) (-3, 15) (-9, -3)]
+</pre>
+=={{header|Phix}}==
+{{trans|C}}
+<lang Phix>enum x, y
+function ccw(sequence a, b, c)
+    return (b[x] - a[x]) * (c[y] - a[y])
+         > (b[y] - a[y]) * (c[x] - a[x])
+end function
+function convex_hull(sequence points)
+    sequence h = {}
+    points = sort(points)
+    /* lower hull */
+    for i=1 to length(points) do
+        while length(h)>=2
+          and not ccw(h[$-1], h[$], points[i]) do
+            h = h[1..$-1]
+        end while
+        h = append(h, points[i])
+    end for
+    /* upper hull */
+    for i=length(points) to 1 by -1 do
+        while length(h)>=2
+          and not ccw(h[$-1],h[$],points[i]) do
+            h = h[1..$-1]
+        end while
+        h = append(h, points[i])
+    end for
+    h = h[1..$-1]
+    return h
+end function
+constant points = {{16,  3}, {12, 17}, { 0,  6}, {-4, -6}, {16,  6},
+                   {16, -7}, {16, -3}, {17, -4}, { 5, 19}, {19, -8},
+                   { 3, 16}, {12, 13}, { 3, -4}, {17,   5}, {-3, 15},
+                   {-3, -9}, { 0, 11}, {-9, -3}, {-4, -2}, {12, 10}}
+printf(1,"Convex Hull: %v\n",{convex_hull(points)})</lang>
+{{out}}
+<pre>
+Convex Hull: {{-9,-3},{-3,-9},{19,-8},{17,5},{12,17},{5,19},{-3,15}}
 </pre>