namespace DouglasPeuker open System type Point = { X: double; Y : double} module Reduce = let private findPerpendicularDistance p p1 p2 = if (p1.X = p2.X) then Math.Abs(p.X - p1.X) else let slope = (p2.Y - p1.Y) / (p2.X - p1.X) let intercept = p1.Y - (slope * p1.X) Math.Abs(slope * p.X - p.Y + intercept) / Math.Sqrt(Math.Pow(slope, 2.) + 1.) let rec Reduce epsilon (points : Point[]) = if points.Length < 3 || epsilon = 0. then points else let firstPoint = points.[0] let lastPoint = points.[points.Length - 1] let mutable index = -1 let mutable dist = 0.0 for i in 1..points.Length-1 do let cDist = findPerpendicularDistance points.[i] firstPoint lastPoint if (cDist > dist) then dist <- cDist index <- i if (dist > epsilon) then let l1 = points.[0..index] let l2 = points.[index..] let r1 = Reduce epsilon l1 let r2 = Reduce epsilon l2 Array.append (r1.[0..r1.Length-2]) r2 else [|firstPoint; lastPoint|] module Tests = open FsUnit open NUnit.Framework open Reduce [] type ``Given the DouglasPeuker Simplify function``() = let StrToPoints (s : string) = s.Split([|';'|]) |> Array.map (fun p -> let xy = p.Split([|','|]) {X = Double.Parse(xy.[0]); Y = Double.Parse(xy.[1])}) // Minimal cases: [] [] [] // Effect of varying epsilon: [] [] // Tests with vertical segments: [] [] // Tests with horizontal segments: [] [] // Tests with vertical and horizontal segments: [] // Different epsilon: [] // A more complex curve: [] member public this.``inputs are correctly simplified``(items : string, expected : string, epsilon) = let actual = Reduce epsilon (items |> StrToPoints) let expected = expected |> StrToPoints actual |> should equal expected