HR F#: Compute the Area of a Polygon

This is the last from the introductional problems in the Functional Programming domain on Hackerrank. This also might be most complicated among the introductionary problems:

You are given the cartesian coordinates of a set of points in a 2D plane. When traversed sequentially, these points form a Polygon, P, which is not self-intersecting in nature. Can you compute the area of polygon P?

Although it looks very similar to Compute the Perimeter of a Polygon, it is much more complicated if the test polygons can be non-convex.

Assuming that the test set does not have non-convex polygons, let's adapt the solution for the perimeter problem for area.

let len p1 p2 =
  sqrt (((fst p1)-(fst p2))**2.0+((snd p1)-(snd p2))**2.0)

let area p1 p2 p3 =
    let p12 = len p1 p2
    let p23 = len p2 p3
    let p13 = len p1 p3
    let p = (p12 + p23 + p13) / 2.0
    sqrt (p * (p - p12) * (p - p23) * (p - p13))

// recursive approach
let rec calc (first : Option<float*float>)
             (previous : Option<float*float>)
             (sum : float)
             (vertices : seq<float*float>) =
  if Seq.isEmpty vertices then
    match first, previous with
    | Some f, Some p -> sum
    | _ -> 0.0 
  else
    let head = Seq.head vertices
    let tail = Seq.skip 1 vertices
    match first, previous with
    | None, None -> calc (Some head) (Some head) sum tail
    | Some f, Some p -> calc (Some f) (Some head) (sum + (area f p head)) tail
    | _ -> 0.0 // impossible

This solution passes some of the test cases, but not all of them. It looks like it should support non-convex polygons.

Partitioning non-convex polygon into convex is a well known problem and there are many solutions exist. Triangulation is quite simple one. It partitions the polygon into many triangles and then areas of this triangles can be easily calculated and summarised.

Alternatively, let's look on what breakes when the triangle gets added to the sum in the recursive function. It is easy to see that there are two types of the triangles, depending on whether the base point is on the "polygon" side or not. It also easy to check that size of the polygon is actually size of the triangles of the first kind minus the sum of triangles of the second type.

So in order to add the triangle correctly, it is required to check on which side of the line the base point is. It can be done by examining the sign of the vector multiplication.

let isPolygonSide p1 p2 bp =
    (((fst bp)-(fst p1))*((snd p2)-(snd p1))-
      ((snd bp)-(snd p1))*((fst p2)-(fst p1))) < 0.0

Rewrite the calc function, adding the area if isPolygonSide returns true and substracting otherwise:

let rec calc (first : Option<float*float>)
             (previous : Option<float*float>)
             (sum : float)
             (vertices : seq<float*float>) =
  if Seq.isEmpty vertices then
    match first, previous with
    | Some f, Some p -> sum
    | _ -> 0.0 
  else
    let head = Seq.head vertices
    let tail = Seq.skip 1 vertices
    match first, previous with
    | None, None -> calc (Some head) (Some head) sum tail
    | Some f, Some p ->
        let m = if isPolygonSide p head f then 1.0 else -1.0
        calc (Some f) (Some head) (sum + m * (area f p head)) tail
    | _ -> 0.0 // impossible

Finally, parse the input and run:

[<EntryPoint>]
let main argv =
  let n = Console.ReadLine () |> int
  let vertices =
    seq { for _ in 1..n do
            let line = Console.ReadLine ()
            let values = line.Split (' ')
                         |> Array.map (fun v -> float v)
            yield values.[0], values.[1] }
    |> Seq.cache
  let perimeter = calc None None 0.0 vertices
  printfn "%A" perimeter
  0 // return an integer exit code