HR F#: Compute the Perimeter of a Polygon

The problem of computing perimeter of the polygon is one of the easy problems, but it requires a bit more programming.

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. Compute the perimeter of polygon.

That's the sample input for triangle with vertices in points (0, 0), (1, 0) and (0, 1):

3
0 0
0 1
1 0

Its perimeter is \(2 + \sqrt(2) \approx 3.414213\).

The straightforward method to compute the perimeter of the poligon is just iterate through the vertices and summing the edge lengths on the way. The only problem here is what to do with the edge connecting first and last vertices? In order to claculate its length, the first vertex is need to be carried over by the iterating function.

List of vertices can be iterated either by the recursive function or by one of the library functions. Seq.fold looks like a good candidate as it allows to carry state over. The state can be first item, calculated perimeter and the current item. When fold finishes, the result will contain first and last vertices and length of all edges except the polygon closing edge. The recursive approach looks a bit more functional, though.

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

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

The function calc can be called as follows:

let perimeter = calc None None 0.0 vertices

where vertices is of type seq<float*float>, generated by reading the pairs from the console. For example, in this way:

open System

...

[<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

Seq.cache is required because it will prevent the sequence from being evaluated multiple times.