-
Notifications
You must be signed in to change notification settings - Fork 127
/
line_simplifier.go
206 lines (177 loc) · 5.75 KB
/
line_simplifier.go
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
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
package buffer
import (
"math"
"math/big"
"github.com/spatial-go/geoos/algorithm/calc"
"github.com/spatial-go/geoos/algorithm/matrix"
"github.com/spatial-go/geoos/algorithm/measure"
)
// const Defined constant variable
const (
Deleted = 1
NumPtsCheck = 10
SafeEpsilon = 1e-15
)
// LineSimplifier Simplifies a buffer input line to
// remove concavities with shallow depth.
type LineSimplifier struct {
inputLine matrix.LineMatrix
distanceTol float64
isDeleted []byte
angleOrientation int
}
// Simplify the input coordinate list.
// If the distance tolerance is positive,
// concavities on the LEFT side of the line are simplified.
// If the supplied distance tolerance is negative,
// concavities on the RIGHT side of the line are simplified.
func (l *LineSimplifier) Simplify(distanceTol float64) matrix.LineMatrix {
l.distanceTol = math.Abs(distanceTol)
if distanceTol < 0 {
l.angleOrientation = calc.ClockWise
}
// rely on fact that boolean array is filled with false value
l.isDeleted = make([]byte, len(l.inputLine))
for isChanged := false; isChanged; isChanged = l.deleteShallowConcavities() {
}
return l.collapseLine()
}
// Uses a sliding window containing 3 vertices to detect shallow angles
// in which the middle vertex can be deleted, since it does not
// affect the shape of the resulting buffer in a significant way.
func (l *LineSimplifier) deleteShallowConcavities() bool {
// Do not simplify end line segments of the line string.
// This ensures that end caps are generated consistently.
index := 1
midIndex := l.findNextNonDeletedIndex(index)
lastIndex := l.findNextNonDeletedIndex(midIndex)
isChanged := false
for lastIndex < len(l.inputLine) {
// test triple for shallow concavity
isMiddleVertexDeleted := false
if l.isDeletable(index, midIndex, lastIndex,
l.distanceTol) {
l.isDeleted[midIndex] = Deleted
isMiddleVertexDeleted = true
isChanged = true
}
// move simplification window forward
if isMiddleVertexDeleted {
index = lastIndex
} else {
index = midIndex
}
midIndex = l.findNextNonDeletedIndex(index)
lastIndex = l.findNextNonDeletedIndex(midIndex)
}
return isChanged
}
// Finds the next non-deleted index, or the end of the point array if none
func (l *LineSimplifier) findNextNonDeletedIndex(index int) int {
next := index + 1
for next < len(l.inputLine) && l.isDeleted[next] == Deleted {
next++
}
return next
}
func (l *LineSimplifier) collapseLine() matrix.LineMatrix {
coordList := matrix.LineMatrix{}
for i := 0; i < len(l.inputLine); i++ {
if l.isDeleted[i] != Deleted {
coordList = append(coordList, l.inputLine[i])
}
}
return coordList
}
func (l *LineSimplifier) isDeletable(i0, i1, i2 int, distanceTol float64) bool {
p0 := l.inputLine[i0]
p1 := l.inputLine[i1]
p2 := l.inputLine[i2]
if !l.isConcave(p0, p1, p2) {
return false
}
if !l.isShallow(p0, p1, p2, distanceTol) {
return false
}
return l.isShallowSampled(p0, p1, i0, i2, distanceTol)
}
// IsShallowConcavity ...
func (l *LineSimplifier) IsShallowConcavity(p0, p1, p2 matrix.Matrix, distanceTol float64) bool {
orientation := l.orientationIndex(p0[0], p0[1], p1[0], p1[1], p2[0], p2[1])
isAngleToSimplify := (orientation == l.angleOrientation)
if !isAngleToSimplify {
return false
}
dist := measure.PlanarDistance(p2, matrix.LineMatrix{p1, p0})
return dist < distanceTol
}
// Checks for shallowness over a sample of points in the given section.
// This helps prevents the simplification from incrementally
// "skipping" over points which are in fact non-shallow.
func (l *LineSimplifier) isShallowSampled(p0, p2 matrix.Matrix, i0, i2 int, distanceTol float64) bool {
// check every point to see if it is within tolerance
inc := (i2 - i0) / NumPtsCheck
if inc <= 0 {
inc = 1
}
for i := i0; i < i2; i += inc {
if !l.isShallow(p0, p2, l.inputLine[i], distanceTol) {
return false
}
}
return true
}
func (l *LineSimplifier) isShallow(p0, p1, p2 matrix.Matrix, distanceTol float64) bool {
dist := measure.PlanarDistance(p2, matrix.LineMatrix{p1, p0})
return dist < distanceTol
}
func (l *LineSimplifier) isConcave(p0, p1, p2 matrix.Matrix) bool {
orientation := l.orientationIndex(p0[0], p0[1], p1[0], p1[1], p2[0], p2[1])
isConcave := (orientation == l.angleOrientation)
return isConcave
}
func (l *LineSimplifier) orientationIndex(p1x, p1y,
p2x, p2y,
qx, qy float64) int {
// fast filter for orientation index
// avoids use of slow extended-precision arithmetic in many cases
index := l.orientationIndexFilter(p1x, p1y, p2x, p2y, qx, qy)
if index <= 1 {
return index
}
// // normalize coordinates
// dx1 := (&calc.PairFloat{Hi: p2x, Lo: 0.0}).SelfAdd(-p1x, 0.0)
// dy1 := (&calc.PairFloat{Hi: p2y, Lo: 0.0}).SelfAdd(-p1y, 0.0)
// dx2 := (&calc.PairFloat{Hi: qx, Lo: 0.0}).SelfAdd(-p2x, 0.0)
// dy2 := (&calc.PairFloat{Hi: qy, Lo: 0.0}).SelfAdd(-p2y, 0.0)
// dy11 := dy1.SelfMultiply(dx2.Hi, dx2.Lo)
// // sign of determinant - unrolled for performance
// return dx1.SelfMultiply(dy2.Hi, dy2.Lo).SelfSubtract(dy11.Hi, dy11.Lo).Signum()
return new(big.Float).SetFloat64((p2x-p1x)*(qy-p2y) - (p2y-p1y)*(qx-p2x)).Sign()
}
// orientationIndexFilter A filter for computing the orientation index of three coordinates.
func (l *LineSimplifier) orientationIndexFilter(pax, pay,
pbx, pby, pcx, pcy float64) int {
detSum := 0.0
detLeft := (pax - pcx) * (pby - pcy)
detRight := (pay - pcy) * (pbx - pcx)
det := detLeft - detRight
if detLeft > 0.0 {
if detRight <= 0.0 {
return calc.Signum(det)
}
detSum = detLeft + detRight
} else if detLeft < 0.0 {
if detRight >= 0.0 {
return calc.Signum(det)
}
detSum = -detLeft - detRight
} else {
return calc.Signum(det)
}
errbound := SafeEpsilon * detSum
if (det >= errbound) || (-det >= errbound) {
return calc.Signum(det)
}
return 2
}