Convex hull: Difference between revisions

{{out}}

<pre>Convex Hull: [(-9,-3), (-3,-9), (19,-8), (17,5), (12,17), (5,19), (-3,15)]</pre>

=={{header|F#}}==

{{trans|C}}

<lang F#>open System

type Point =

struct

val X : int

val Y : int

new (x : int, y : int ) = {X = x; Y = y}

end

let (poly : Point list) = [ Point(16, 3); Point(12, 17); Point( 0, 6); Point(-4, -6); Point(16, 6);

Point(16, -7); Point(16, -3); Point(17, -4); Point( 5, 19); Point(19, -8);

Point( 3, 16); Point(12, 13); Point( 3, -4); Point(17, 5); Point(-3, 15);

Point(-3, -9); Point( 0, 11); Point(-9, -3); Point(-4, -2); Point(12, 10)]

let affiche (lst : Point list) =

let mutable (str : string) = List.fold (fun acc (p : Point) -> acc + sprintf "(%d, %d) " p.X p.Y) "Convex Hull: [" lst

printfn "%s" (str.[0.. str.Length - 2] + "]")

let ccw (p1 : Point) (p2 : Point) (p3 : Point) =

(p2.X - p1.X) * (p3.Y - p1.Y) > (p2.Y - p1.Y) * (p3.X - p1.X)

let convexHull (poly : Point list) =

let mutable (outHull : Point list) = List.Empty

let mutable (k : int) = 0

for p in poly do

while k >= 2 && not (ccw outHull.[k-2] outHull.[k-1] p) do

k <- k - 1

if k >= outHull.Length

then outHull <- outHull @ [p]

else outHull <- outHull.[0..k - 1] @ [p]

k <- k + 1

let (t : int) = k + 1

for p in List.rev poly do

while k >= t && not (ccw outHull.[k-2] outHull.[k-1] p) do

k <- k - 1

if k >= outHull.Length

then outHull <- outHull @ [p]

else outHull <- outHull.[0..k - 1] @ [p]

k <- k + 1

outHull.[0 .. k - 2]

affiche (convexHull (List.sortBy (fun (x : Point) -> x.X, x.Y) poly))

</lang>