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
|