Skip to content

Commit 132b19c

Browse files
paulmachpaulmach
authored
Merge pull request #140 from paulmach/simplify-min
simplify: Visvalingam, by default, keeps 3 points for "areas"
2 parents 3ecd611 + 7b6e2a5 commit 132b19c

File tree

7 files changed

+91
-22
lines changed

7 files changed

+91
-22
lines changed

‎simplify/douglas_peucker.go‎

Lines changed: 1 addition & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -19,7 +19,7 @@ func DouglasPeucker(threshold float64) *DouglasPeuckerSimplifier {
1919
}
2020
}
2121

22-
func (s *DouglasPeuckerSimplifier) simplify(ls orb.LineString, wim bool) (orb.LineString, []int) {
22+
func (s *DouglasPeuckerSimplifier) simplify(ls orb.LineString, area, wim bool) (orb.LineString, []int) {
2323
mask := make([]byte, len(ls))
2424
mask[0] = 1
2525
mask[len(mask)-1] = 1

‎simplify/douglas_peucker_test.go‎

Lines changed: 1 addition & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -40,7 +40,7 @@ func TestDouglasPeucker(t *testing.T) {
4040

4141
for _, tc := range cases {
4242
t.Run(tc.name, func(t *testing.T) {
43-
v, im := DouglasPeucker(tc.threshold).simplify(tc.ls, true)
43+
v, im := DouglasPeucker(tc.threshold).simplify(tc.ls, false, true)
4444
if !v.Equal(tc.expected) {
4545
t.Log(v)
4646
t.Log(tc.expected)

‎simplify/helpers.go‎

Lines changed: 7 additions & 7 deletions
Original file line numberDiff line numberDiff line change
@@ -4,7 +4,7 @@ package simplify
44
import "github.com/paulmach/orb"
55

66
type simplifier interface {
7-
simplify(orb.LineString, bool) (orb.LineString, []int)
7+
simplify(l orb.LineString, area bool, withIndexMap bool) (orb.LineString, []int)
88
}
99

1010
func simplify(s simplifier, geom orb.Geometry) orb.Geometry {
@@ -64,24 +64,24 @@ func simplify(s simplifier, geom orb.Geometry) orb.Geometry {
6464
}
6565

6666
func lineString(s simplifier, ls orb.LineString) orb.LineString {
67-
return runSimplify(s, ls)
67+
return runSimplify(s, ls, false)
6868
}
6969

7070
func multiLineString(s simplifier, mls orb.MultiLineString) orb.MultiLineString {
7171
for i := range mls {
72-
mls[i] = runSimplify(s, mls[i])
72+
mls[i] = runSimplify(s, mls[i], false)
7373
}
7474
return mls
7575
}
7676

7777
func ring(s simplifier, r orb.Ring) orb.Ring {
78-
return orb.Ring(runSimplify(s, orb.LineString(r)))
78+
return orb.Ring(runSimplify(s, orb.LineString(r), true))
7979
}
8080

8181
func polygon(s simplifier, p orb.Polygon) orb.Polygon {
8282
count := 0
8383
for i := range p {
84-
r := orb.Ring(runSimplify(s, orb.LineString(p[i])))
84+
r := orb.Ring(runSimplify(s, orb.LineString(p[i]), true))
8585
if i != 0 && len(r) <= 2 {
8686
continue
8787
}
@@ -113,10 +113,10 @@ func collection(s simplifier, c orb.Collection) orb.Collection {
113113
return c
114114
}
115115

116-
func runSimplify(s simplifier, ls orb.LineString) orb.LineString {
116+
func runSimplify(s simplifier, ls orb.LineString, area bool) orb.LineString {
117117
if len(ls) <= 2 {
118118
return ls
119119
}
120-
ls, _ = s.simplify(ls, false)
120+
ls, _ = s.simplify(ls, area, false)
121121
return ls
122122
}

‎simplify/radial.go‎

Lines changed: 1 addition & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -20,7 +20,7 @@ func Radial(df orb.DistanceFunc, threshold float64) *RadialSimplifier {
2020
}
2121
}
2222

23-
func (s *RadialSimplifier) simplify(ls orb.LineString, wim bool) (orb.LineString, []int) {
23+
func (s *RadialSimplifier) simplify(ls orb.LineString, area, wim bool) (orb.LineString, []int) {
2424
var indexMap []int
2525
if wim {
2626
indexMap = append(indexMap, 0)

‎simplify/radial_test.go‎

Lines changed: 1 addition & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -41,7 +41,7 @@ func TestRadial(t *testing.T) {
4141

4242
for _, tc := range cases {
4343
t.Run(tc.name, func(t *testing.T) {
44-
v, im := Radial(planar.Distance, tc.threshold).simplify(tc.ls, true)
44+
v, im := Radial(planar.Distance, tc.threshold).simplify(tc.ls, false, true)
4545
if !v.Equal(tc.expected) {
4646
t.Log(v)
4747
t.Log(tc.expected)

‎simplify/visvalingam.go‎

Lines changed: 38 additions & 8 deletions
Original file line numberDiff line numberDiff line change
@@ -12,10 +12,17 @@ var _ orb.Simplifier = &VisvalingamSimplifier{}
1212
// performs the vivalingham algorithm.
1313
type VisvalingamSimplifier struct {
1414
Threshold float64
15-
ToKeep int
15+
16+
// If 0 defaults to 2 for line, 3 for non-closed rings and 4 for closed rings.
17+
// The intent is to maintain valid geometry after simplification, however it
18+
// is still possible for the simplification to create self-intersections.
19+
ToKeep int
1620
}
1721

1822
// Visvalingam creates a new VisvalingamSimplifier.
23+
// If minPointsToKeep is 0 the algorithm will keep at least 2 points for lines,
24+
// 3 for non-closed rings and 4 for closed rings. However it is still possible
25+
// for the simplification to create self-intersections.
1926
func Visvalingam(threshold float64, minPointsToKeep int) *VisvalingamSimplifier {
2027
return &VisvalingamSimplifier{
2128
Threshold: threshold,
@@ -25,19 +32,42 @@ func Visvalingam(threshold float64, minPointsToKeep int) *VisvalingamSimplifier
2532

2633
// VisvalingamThreshold runs the Visvalingam-Whyatt algorithm removing
2734
// triangles whose area is below the threshold.
35+
// Will keep at least 2 points for lines, 3 for non-closed rings and 4 for closed rings.
36+
// The intent is to maintain valid geometry after simplification, however it
37+
// is still possible for the simplification to create self-intersections.
2838
func VisvalingamThreshold(threshold float64) *VisvalingamSimplifier {
2939
return Visvalingam(threshold, 0)
3040
}
3141

3242
// VisvalingamKeep runs the Visvalingam-Whyatt algorithm removing
33-
// triangles of minimum area until we're down to `toKeep` number of points.
34-
func VisvalingamKeep(toKeep int) *VisvalingamSimplifier {
35-
return Visvalingam(math.MaxFloat64, toKeep)
43+
// triangles of minimum area until we're down to `minPointsToKeep` number of points.
44+
// If minPointsToKeep is 0 the algorithm will keep at least 2 points for lines,
45+
// 3 for non-closed rings and 4 for closed rings. However it is still possible
46+
// for the simplification to create self-intersections.
47+
func VisvalingamKeep(minPointsToKeep int) *VisvalingamSimplifier {
48+
return Visvalingam(math.MaxFloat64, minPointsToKeep)
3649
}
3750

38-
func (s *VisvalingamSimplifier) simplify(ls orb.LineString, wim bool) (orb.LineString, []int) {
51+
func (s *VisvalingamSimplifier) simplify(ls orb.LineString, area, wim bool) (orb.LineString, []int) {
52+
if len(ls) <= 1 {
53+
return ls, nil
54+
}
55+
56+
toKeep := s.ToKeep
57+
if toKeep == 0 {
58+
if area {
59+
if ls[0] == ls[len(ls)-1] {
60+
toKeep = 4
61+
} else {
62+
toKeep = 3
63+
}
64+
} else {
65+
toKeep = 2
66+
}
67+
}
68+
3969
var indexMap []int
40-
if len(ls) <= s.ToKeep {
70+
if len(ls) <= toKeep {
4171
if wim {
4272
// create identify map
4373
indexMap = make([]int, len(ls))
@@ -89,7 +119,7 @@ func (s *VisvalingamSimplifier) simplify(ls orb.LineString, wim bool) (orb.LineS
89119
// run through the reduction process
90120
for len(heap) > 0 {
91121
current := heap.Pop()
92-
if current.area > threshold || len(ls)-removed <= s.ToKeep {
122+
if current.area > threshold || len(ls)-removed <= toKeep {
93123
break
94124
}
95125

@@ -153,7 +183,7 @@ type visItem struct {
153183
next *visItem
154184
previous *visItem
155185

156-
index int // interal index in heap, for removal and update
186+
index int // internal index in heap, for removal and update
157187
}
158188

159189
func (h *minHeap) Push(item *visItem) {

‎simplify/visvalingam_test.go‎

Lines changed: 42 additions & 3 deletions
Original file line numberDiff line numberDiff line change
@@ -33,7 +33,7 @@ func TestVisvalingamThreshold(t *testing.T) {
3333

3434
for _, tc := range cases {
3535
t.Run(tc.name, func(t *testing.T) {
36-
v, im := VisvalingamThreshold(tc.threshold).simplify(tc.ls, true)
36+
v, im := VisvalingamThreshold(tc.threshold).simplify(tc.ls, false, true)
3737
if !v.Equal(tc.expected) {
3838
t.Log(v)
3939
t.Log(tc.expected)
@@ -49,6 +49,45 @@ func TestVisvalingamThreshold(t *testing.T) {
4949
}
5050
}
5151

52+
func TestVisvalingamThreshold_area(t *testing.T) {
53+
cases := []struct {
54+
name string
55+
r orb.Ring
56+
expected orb.Ring
57+
indexMap []int
58+
}{
59+
{
60+
name: "reduction",
61+
r: orb.Ring{{0, 0}, {1, 0}, {1, 0.5}, {1, 1}, {0.5, 1}, {0, 1}},
62+
expected: orb.Ring{{0, 0}, {1, 0}, {0, 1}},
63+
indexMap: []int{0, 1, 5},
64+
},
65+
{
66+
name: "reduction closed",
67+
r: orb.Ring{{0, 0}, {1, 0}, {1, 0.5}, {1, 1}, {0.5, 1}, {0, 1}, {0, 0}},
68+
expected: orb.Ring{{0, 0}, {1, 0}, {1, 1}, {0, 0}},
69+
indexMap: []int{0, 1, 3, 6},
70+
},
71+
}
72+
73+
for _, tc := range cases {
74+
t.Run(tc.name, func(t *testing.T) {
75+
v, im := VisvalingamThreshold(10).simplify(orb.LineString(tc.r), true, true)
76+
if !v.Equal(orb.LineString(tc.expected)) {
77+
t.Log(v)
78+
t.Log(tc.expected)
79+
t.Errorf("incorrect ring")
80+
}
81+
82+
if !reflect.DeepEqual(im, tc.indexMap) {
83+
t.Log(im)
84+
t.Log(tc.indexMap)
85+
t.Errorf("incorrect index map")
86+
}
87+
})
88+
}
89+
}
90+
5291
func TestVisvalingamKeep(t *testing.T) {
5392
cases := []struct {
5493
name string
@@ -96,7 +135,7 @@ func TestVisvalingamKeep(t *testing.T) {
96135

97136
for _, tc := range cases {
98137
t.Run(tc.name, func(t *testing.T) {
99-
v, im := VisvalingamKeep(tc.keep).simplify(tc.ls, true)
138+
v, im := VisvalingamKeep(tc.keep).simplify(tc.ls, false, true)
100139
if !v.Equal(tc.expected) {
101140
t.Log(v)
102141
t.Log(tc.expected)
@@ -181,7 +220,7 @@ func TestVisvalingam(t *testing.T) {
181220

182221
for _, tc := range cases {
183222
t.Run(tc.name, func(t *testing.T) {
184-
v, im := Visvalingam(tc.threshold, tc.keep).simplify(tc.ls, true)
223+
v, im := Visvalingam(tc.threshold, tc.keep).simplify(tc.ls, false, true)
185224
if !v.Equal(tc.expected) {
186225
t.Log(v)
187226
t.Log(tc.expected)

0 commit comments

Comments
 (0)