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

    [<TestFixture>]
    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:
        [<TestCase("1.0, 1.0", "1.0, 1.0", 0.5)>]
        [<TestCase("1.0, 1.0; 2.0, 2.0", "1.0, 1.0; 2.0, 2.0", 0.5)>]
        [<TestCase("1.0, 1.0; 2.0, 2.0; 3.0, 3.0", "1.0, 1.0; 3.0, 3.0", 0.5)>]

        // Effect of varying epsilon:
        [<TestCase("0.0, 2.0; 1.0, 1.0; 3.0, 0.0; 5.0, 1.0", "0.0, 2.0; 1.0, 1.0; 3.0, 0.0; 5.0, 1.0", 0.1)>]
        [<TestCase("0.0, 2.0; 1.0, 1.0; 3.0, 0.0; 5.0, 1.0", "0.0, 2.0; 3.0, 0.0; 5.0, 1.0", 0.5)>]

        // Tests with vertical segments:
        [<TestCase("10.0, 35.0; 15.0, 34.0; 15.0, 30.0; 20.0, 29.0", "10.0, 35.0; 20.0, 29.0", 10.0)>]
        [<TestCase("10.0, 35.0; 15.0, 34.0; 15.0, 30.0; 20.0, 29.0", "10.0, 35.0; 15.0, 34.0; 15.0, 30.0; 20.0, 29.0", 1.0)>]

        // Tests with horizontal segments:
        [<TestCase("10.0, 35.0; 15.0, 35.0; 16.0, 30.0; 21.0, 30.0", "10.0, 35.0; 21.0, 30.0", 10.0)>]
        [<TestCase("10.0, 35.0; 15.0, 35.0; 16.0, 30.0; 21.0, 30.0", "10.0, 35.0; 15.0, 35.0; 16.0, 30.0; 21.0, 30.0", 1.0)>]

        // Tests with vertical and horizontal segments:
        [<TestCase("10.0, 30.0; 30.0, 30.0; 30.0, 10.0; 50.0, 10.0", "10.0, 30.0; 50.0, 10.0", 15.0)>]
        // Different epsilon:
        [<TestCase("10.0, 30.0; 30.0, 30.0; 30.0, 10.0; 50.0, 10.0", "10.0, 30.0; 50.0, 10.0", 10.0)>]

        // A more complex curve:
        [<TestCase("3.5, 21.25; 7.3, 12.0; 23.2, 3.1; 37.2, 12.07; 54.6, 18.15; 62.2, 16.45; 71.5, 9.7; 101.3, 21.1", "3.5, 21.25; 23.2, 3.1; 54.6, 18.15; 71.5, 9.7; 101.3, 21.1", 5.0)>]

        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

More information

Link:http://fssnip.net/kY
Posted:11 years ago
Author:Kit Eason
Tags: curves

This web site is created using F# and Suave web server. It is hosted on Azure and the source code is on GitHub. Contributions are welcome!

The first version of fssnip.net has been created by @tomaspetricek back in 2010. This web site is a new, open-source and contribution-friendly version.