open System;;
open System.Windows.Forms;;
open Microsoft.FSharp.Collections;;

type Point = {
    x :double;
    y :double;
    } with
    
    static member ( = ) a b = 
        a.x = b.x && a.y = b.y;
      
    static member ( <> ) a b = 
        not(a = b);
    
end;;
    

type Edge = {
    orig:Point;
    dest:Point;
    } with

    static member ( = ) a b = 
        a.orig = b.orig && a.dest = b.dest;
      
    static member ( <> ) a b = 
        not(a = b);
        
end;;
    

let sort point_list =
    List.sort( fun p1 p2 ->
               match Pervasives.compare p1.y p2.y with
               | 0 -> Pervasives.compare p1.x p2.x;
               | _ as v -> v;
               
    ) point_list;;


//    Input:  three points P0, P1, and P2
//    Return: >0 for P2 left of the line through P0 and P1
//            =0 for P2 on the line
//            <0 for P2 right of the line
let testSide p0 p1 p2 =
    (p1.x - p0.x) * (p2.y - p0.y) - (p2.x - p0.x) * (p1.y - p0.y);;


let isLeft p0 p1 p2 =
    (testSide p0 p1 p2) > 0.;;


let isRight p0 p1 p2 =
    (testSide p0 p1 p2) < 0.;;
    

let rec _jarvis cmp max_point (hull_list:Point list) (input_list:Point list) =       
    match input_list with
    | p::tl -> 
    
        let last = List.hd hull_list in
        if last = max_point then hull_list
        else (
        
          let best = List.fold_left(fun p1 p2 ->
                                       if (cmp last p1 p2) then p2 
                                       else p1;   
                                    ) p input_list in
                                    
          _jarvis cmp max_point (best::hull_list) tl
          
        )
        
    | [] -> hull_list;;


let jarvis point_list =
    if List.length point_list < 3 then failwith "3 points are required for a polygon";
    
    let point_list = sort point_list in
    let miny = point_list |> List.hd in        
    let maxy = point_list |> List.rev |> List.hd in
        
    let left = _jarvis (isLeft) maxy [miny] point_list in
    let right = _jarvis (isRight) maxy [miny] point_list in
    right @ left |> List.rev;;


let points_to_edges pl =
    let p1::p2::tl = pl in
    List.fold_left(fun (el:Edge list) p ->
                      let e = List.hd el in
                      {orig = e.dest; dest = p}::el) [{orig = p1; dest = p2}] pl;;
    

let generate_plist count =
    let r = new Random(DateTime.Now.GetHashCode()) in

    let rand_float max =
        Convert.ToDouble(r.Next max) + r.NextDouble() in
    
    [for i in 1 .. count -> {x  = rand_float 600;
                             y  = rand_float 600}] |> sort;;


type ConvexHullControl = class
    inherit UserControl as base

    val mutable point_list: Point list;
    
    new() as this = {                                               
        point_list = [];
    } then this.init();
    
    member this.init() = 
        base.BackColor <- Drawing.Color.White;
        base.SetStyle (ControlStyles.UserPaint, true);
        base.SetStyle (ControlStyles.DoubleBuffer, true);
        base.SetStyle (ControlStyles.AllPaintingInWmPaint, true);
        base.Click.Add(fun e -> this.reset());
        this.reset();

    
    member this.reset() = 
        this.point_list <- generate_plist 30 |> sort;
        this.Invalidate();
        
    
    override this.OnPaint e =
        let g = e.Graphics in
        
        let graph_elist p l = 
            List.iter(fun e -> 
                let x1 = Convert.ToInt32(e.orig.x) in
                let y1 = Convert.ToInt32(e.orig.y) in
                let x2 = Convert.ToInt32(e.dest.x) in
                let y2 = Convert.ToInt32(e.dest.y) in                  
                g.DrawLine(p, x1, y1, x2, y2);
            ) l in        

        let miny = this.point_list |> List.hd in        
        let maxy = this.point_list |> List.rev |> List.hd in
        
        let left = _jarvis (isLeft) maxy [miny] this.point_list in
        let right = _jarvis (isRight) maxy [miny] this.point_list in
        
        let left = left |> List.rev in
        let right = right |> List.rev in
        
        left  |> points_to_edges |> graph_elist Drawing.Pens.Green;
        right |> points_to_edges |> graph_elist Drawing.Pens.Blue;
            
        List.iter(fun p -> 
            let x = Convert.ToInt32(p.x) in
            let y = Convert.ToInt32(p.y) in
            g.DrawEllipse(Drawing.Pens.Red, x - 1, y - 1, 2, 2);
                  
        ) this.point_list;
    
end;;



[<STAThread()>]
do

    let size = new Drawing.Size(700, 700) in

    let mw = new Form() in
    let cc = new ConvexHullControl() in
    mw.Controls.Add(cc);
    
    cc.Dock <- DockStyle.Fill;    
    cc.Size <- size;
    mw.ClientSize <- size;
    mw.MaximumSize <- mw.Size;
    mw.MinimumSize <- mw.Size;
    mw.Text <- "Convex Hull";
    mw.Show();
    Application.Run(mw);;