1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95

 


module GrahamScan

open System
open System.Drawing

/// finds the points lying on the convex hull of the given set of points and 
/// returns those points in clockwise direction, starting at the point
/// with minimum y-value
/// Remarks: it's a more or less direct implementation of the algorithm named
/// after Ronald Graham that is explained on <A href="http://en.wikipedia.org/wiki/Graham_scan">http://en.wikipedia.org/wiki/Graham_scan</A>
let FindConvexHull (pts : Point seq) : Point seq =

    // it's nicer to work with lists so let's convert
    let ptl = List.ofSeq pts

    // to make something worthwhile we need at last two points
    if ptl.Length <= 2 then Seq.empty
    else

    // this is a helperfunction (explained in the wikipedia article) in which direction
    // 3 points "turn"
    let ccw (a : Point) (b : Point) (c : Point) =
        (b.X - a.X)*(c.Y - a.Y) - (b.Y - a.Y)*(c.X - a.X)

    // 1. Let's find the point with the minimum y-coordinate
    // I guess here is a bit of optimization left to be done
    // because I'm sorting the list where you only need to 
    // find the minimum point (O(n) VS O(n log n)
    // but as there is no List.minWith I stick with it for now
    // in order to keep the code shorter
    /// this is the comparision function for this
    let cmpPts (a : Point) (b : Point) =
        match a.Y.CompareTo(b.Y) with
        | 0 -> a.X.CompareTo(b.X)
        | _ as r -> r
    // and with it we can look for the mentioned point
    let sortedY = ptl |> List.sortWith cmpPts
    let org, rest = sortedY.Head, sortedY.Tail

    // 2. Sortiere nach Winkel X-Achse / [org -> Punkt]
    // 2. we have to sort the list in increasing order of the angle
    // that a point p makes with org and the x-axis
    // as mentioned in the wiki-article you only need to calculate the
    // cos of the angle and of course this is just "adjacent/hypotenuse" 
    // here is the function to get this value
    let winkelCos (p : Point) =
        let dx = float (p.X - org.X)
        let dy = float (p.Y - org.Y)
        let l = Math.Sqrt(dx*dx + dy*dy)
        dx / l
    // and here we sort the list (we only sort the remainder without
    // org and prepend it afterwards to ward of 
    // any issue with "division by zero"
    let sortedW = org::(rest |> List.sortBy winkelCos)

    // here is the actual algorithm
    // it uses two lists
    // lastPts: every visited point is put but might
    //          be removed if the "turn direction"
    //          'turns' out to be wrong
    // nextPts: the points left to be checked
    //          as the algorithm progresses those
    //          points are moved to lastPts
    // so lastPts will contain the found points
    // on the convex hull at every step, but in
    // clockwise orientation (as we push in front
    // of the list)
    let rec scan (lastPts : Point list) (nextPts : Point list) =
        // we are done if there are no points left to check
        if nextPts.IsEmpty then lastPts
        else

        // if there are points left take the first one
        let c = nextPts.Head

        // we need the last 3 points for the algorithm
        // so check the visited points
        match lastPts with
        // if there are at least 2 points b,a in the visited points
        // and a,b,c is NOT a counterclockwise turn
        // we have to remove b from lastPoints and continue checking
        // backwards ...
        | b::a::_ when ccw a b c >= 0 -> scan (lastPts.Tail) nextPts
        // in every other case we can push c onto the visited
        // stack and continue
        | _ -> scan (c::lastPts) nextPts.Tail

    // to run the algorithm we just take the
    // sorted List and call the algorithm with
    // empty "visited" stack
    sortedW |> scan [] |> Seq.ofList