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
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
|
package simplify
import (
"github.com/paulmach/orb"
"github.com/paulmach/orb/planar"
)
var _ orb.Simplifier = &DouglasPeuckerSimplifier{}
// A DouglasPeuckerSimplifier wraps the DouglasPeucker function.
type DouglasPeuckerSimplifier struct {
Threshold float64
}
// DouglasPeucker creates a new DouglasPeuckerSimplifier.
func DouglasPeucker(threshold float64) *DouglasPeuckerSimplifier {
return &DouglasPeuckerSimplifier{
Threshold: threshold,
}
}
func (s *DouglasPeuckerSimplifier) simplify(ls orb.LineString, wim bool) (orb.LineString, []int) {
mask := make([]byte, len(ls))
mask[0] = 1
mask[len(mask)-1] = 1
found := dpWorker(ls, s.Threshold, mask)
var indexMap []int
if wim {
indexMap = make([]int, 0, found)
}
count := 0
for i, v := range mask {
if v == 1 {
ls[count] = ls[i]
count++
if wim {
indexMap = append(indexMap, i)
}
}
}
return ls[:count], indexMap
}
// dpWorker does the recursive threshold checks.
// Using a stack array with a stackLength variable resulted in
// 4x speed improvement over calling the function recursively.
func dpWorker(ls orb.LineString, threshold float64, mask []byte) int {
found := 2
var stack []int
stack = append(stack, 0, len(ls)-1)
for len(stack) > 0 {
start := stack[len(stack)-2]
end := stack[len(stack)-1]
// modify the line in place
maxDist := 0.0
maxIndex := 0
for i := start + 1; i < end; i++ {
dist := planar.DistanceFromSegmentSquared(ls[start], ls[end], ls[i])
if dist > maxDist {
maxDist = dist
maxIndex = i
}
}
if maxDist > threshold*threshold {
found++
mask[maxIndex] = 1
stack[len(stack)-1] = maxIndex
stack = append(stack, maxIndex, end)
} else {
stack = stack[:len(stack)-2]
}
}
return found
}
// Simplify will run the simplification for any geometry type.
func (s *DouglasPeuckerSimplifier) Simplify(g orb.Geometry) orb.Geometry {
return simplify(s, g)
}
// LineString will simplify the linestring using this simplifier.
func (s *DouglasPeuckerSimplifier) LineString(ls orb.LineString) orb.LineString {
return lineString(s, ls)
}
// MultiLineString will simplify the multi-linestring using this simplifier.
func (s *DouglasPeuckerSimplifier) MultiLineString(mls orb.MultiLineString) orb.MultiLineString {
return multiLineString(s, mls)
}
// Ring will simplify the ring using this simplifier.
func (s *DouglasPeuckerSimplifier) Ring(r orb.Ring) orb.Ring {
return ring(s, r)
}
// Polygon will simplify the polygon using this simplifier.
func (s *DouglasPeuckerSimplifier) Polygon(p orb.Polygon) orb.Polygon {
return polygon(s, p)
}
// MultiPolygon will simplify the multi-polygon using this simplifier.
func (s *DouglasPeuckerSimplifier) MultiPolygon(mp orb.MultiPolygon) orb.MultiPolygon {
return multiPolygon(s, mp)
}
// Collection will simplify the collection using this simplifier.
func (s *DouglasPeuckerSimplifier) Collection(c orb.Collection) orb.Collection {
return collection(s, c)
}
|
