5 people like it.

# The Ramer-Douglas-Peucker path reduction algorithm

A simple implementation of the Douglas-Peucker path reduction algorithm. Use for simplifying curves, for instance in plotting coastlines. Loosely based on this implementation: http://karthaus.nl/rdp/

 ``` 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: ``` ``````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 ``````
namespace System
type Point =
{X: double;
Y: double;}

Full name: DouglasPeuker.Point
Point.X: double
Multiple items
val double : value:'T -> float (requires member op_Explicit)

Full name: Microsoft.FSharp.Core.ExtraTopLevelOperators.double

--------------------
type double = Double

Full name: Microsoft.FSharp.Core.double
Point.Y: double
val private findPerpendicularDistance : p:Point -> p1:Point -> p2:Point -> float

Full name: DouglasPeuker.Reduce.findPerpendicularDistance
val p : Point
val p1 : Point
val p2 : Point
type Math =
static val PI : float
static val E : float
static member Abs : value:sbyte -> sbyte + 6 overloads
static member Acos : d:float -> float
static member Asin : d:float -> float
static member Atan : d:float -> float
static member Atan2 : y:float * x:float -> float
static member BigMul : a:int * b:int -> int64
static member Ceiling : d:decimal -> decimal + 1 overload
static member Cos : d:float -> float
...

Full name: System.Math
Math.Abs(value: decimal) : decimal
Math.Abs(value: float) : float
Math.Abs(value: float32) : float32
Math.Abs(value: int64) : int64
Math.Abs(value: int) : int
Math.Abs(value: int16) : int16
Math.Abs(value: sbyte) : sbyte
val slope : double
val intercept : double
Math.Sqrt(d: float) : float
Math.Pow(x: float, y: float) : float
val Reduce : epsilon:float -> points:Point [] -> Point []

Full name: DouglasPeuker.Reduce.Reduce
val epsilon : float
val points : Point []
property Array.Length: int
val firstPoint : Point
val lastPoint : Point
val mutable index : int
val mutable dist : float
val i : int32
val cDist : float
val l1 : Point []
val l2 : Point []
val r1 : Point []
val r2 : Point []
type Array =
member Clone : unit -> obj
member CopyTo : array:Array * index:int -> unit + 1 overload
member GetEnumerator : unit -> IEnumerator
member GetLength : dimension:int -> int
member GetLongLength : dimension:int -> int64
member GetLowerBound : dimension:int -> int
member GetUpperBound : dimension:int -> int
member GetValue : [<ParamArray>] indices:int[] -> obj + 7 overloads
member Initialize : unit -> unit
member IsFixedSize : bool
...

Full name: System.Array
val append : array1:'T [] -> array2:'T [] -> 'T []

Full name: Microsoft.FSharp.Collections.Array.append
module Tests

from DouglasPeuker
namespace FsUnit
namespace NUnit
namespace NUnit.Framework
module Reduce

from DouglasPeuker
Multiple items
type TestFixtureAttribute =
inherit Attribute
new : unit -> TestFixtureAttribute + 1 overload
member Arguments : obj[]
member Categories : IList
member Category : string with get, set
member Description : string with get, set
member Ignore : bool with get, set
member IgnoreReason : string with get, set
member TypeArgs : Type[] with get, set

Full name: NUnit.Framework.TestFixtureAttribute

--------------------
TestFixtureAttribute() : unit
TestFixtureAttribute([<ParamArray>] arguments: obj []) : unit
val StrToPoints : (string -> Point [])
val s : string
Multiple items
val string : value:'T -> string

Full name: Microsoft.FSharp.Core.Operators.string

--------------------
type string = String

Full name: Microsoft.FSharp.Core.string
String.Split([<ParamArray>] separator: char []) : string []
String.Split(separator: string [], options: StringSplitOptions) : string []
String.Split(separator: char [], options: StringSplitOptions) : string []
String.Split(separator: char [], count: int) : string []
String.Split(separator: string [], count: int, options: StringSplitOptions) : string []
String.Split(separator: char [], count: int, options: StringSplitOptions) : string []
val map : mapping:('T -> 'U) -> array:'T [] -> 'U []

Full name: Microsoft.FSharp.Collections.Array.map
val p : string
val xy : string []
type Double =
struct
member CompareTo : value:obj -> int + 1 overload
member Equals : obj:obj -> bool + 1 overload
member GetHashCode : unit -> int
member GetTypeCode : unit -> TypeCode
member ToString : unit -> string + 3 overloads
static val MinValue : float
static val MaxValue : float
static val Epsilon : float
static val NegativeInfinity : float
static val PositiveInfinity : float
...
end

Full name: System.Double
Double.Parse(s: string) : float
Double.Parse(s: string, provider: IFormatProvider) : float
Double.Parse(s: string, style: Globalization.NumberStyles) : float
Double.Parse(s: string, style: Globalization.NumberStyles, provider: IFormatProvider) : float
Multiple items
type TestCaseAttribute =
inherit Attribute
new : [<ParamArray>] arguments:obj[] -> TestCaseAttribute + 3 overloads
member Arguments : obj[]
member Categories : IList
member Category : string with get, set
member Description : string with get, set
member ExpectedException : Type with get, set
member ExpectedExceptionName : string with get, set
member ExpectedMessage : string with get, set
member ExpectedResult : obj with get, set
member Explicit : bool with get, set
...

Full name: NUnit.Framework.TestCaseAttribute

--------------------
TestCaseAttribute([<ParamArray>] arguments: obj []) : unit
TestCaseAttribute(arg: obj) : unit
TestCaseAttribute(arg1: obj, arg2: obj) : unit
TestCaseAttribute(arg1: obj, arg2: obj, arg3: obj) : unit
val this : Given the DouglasPeuker Simplify function
member Given the DouglasPeuker Simplify function.( inputs are correctly simplified ) : items:string * expected:string * epsilon:float -> unit

Full name: DouglasPeuker.Tests.Given the DouglasPeuker Simplify function.( inputs are correctly simplified )
val items : string
val expected : string
val actual : Point []
Multiple items
val Reduce : epsilon:float -> points:Point [] -> Point []

Full name: DouglasPeuker.Reduce.Reduce

--------------------
module Reduce

from DouglasPeuker
val expected : Point []
val should : f:('a -> #Constraints.Constraint) -> x:'a -> y:obj -> unit

Full name: FsUnit.TopLevelOperators.should
val equal : x:'a -> EqualsConstraint

Full name: FsUnit.TopLevelOperators.equal