forked from preng69/polyclip-go
-
Notifications
You must be signed in to change notification settings - Fork 0
/
bugs_test.go
318 lines (303 loc) · 16.9 KB
/
bugs_test.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
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
package polyclip
import (
"fmt"
"sort"
. "testing"
"time"
)
type sorter Polygon
func (s sorter) Len() int { return len(s) }
func (s sorter) Swap(i, j int) { s[i], s[j] = s[j], s[i] }
func (s sorter) Less(i, j int) bool {
if len(s[i]) != len(s[j]) {
return len(s[i]) < len(s[j])
}
for k := range s[i] {
pi, pj := s[i][k], s[j][k]
if pi.X != pj.X {
return pi.X < pj.X
}
if pi.Y != pj.Y {
return pi.Y < pj.Y
}
}
return false
}
// basic normalization just for tests; to be improved if needed
func normalize(poly Polygon) Polygon {
for i, c := range poly {
if len(c) == 0 {
continue
}
// find bottom-most of leftmost points, to have fixed anchor
min := 0
for j, p := range c {
if p.X < c[min].X || p.X == c[min].X && p.Y < c[min].Y {
min = j
}
}
// rotate points to make sure min is first
poly[i] = append(c[min:], c[:min]...)
}
sort.Sort(sorter(poly))
return poly
}
func dump(poly Polygon) string {
return fmt.Sprintf("%v", normalize(poly))
}
func TestBug3(t *T) {
cases := []struct{ subject, clipping, result Polygon }{
// original reported github issue #3
{
subject: Polygon{{{1, 1}, {1, 2}, {2, 2}, {2, 1}}},
clipping: Polygon{
{{2, 1}, {2, 2}, {3, 2}, {3, 1}},
{{1, 2}, {1, 3}, {2, 3}, {2, 2}},
{{2, 2}, {2, 3}, {3, 3}, {3, 2}}},
result: Polygon{{
{1, 1}, {2, 1}, {3, 1},
{3, 2}, {3, 3},
{2, 3}, {1, 3},
{1, 2}}},
},
// simplified variant of issue #3, for easier debugging
{
subject: Polygon{{{1, 2}, {2, 2}, {2, 1}}},
clipping: Polygon{
{{2, 1}, {2, 2}, {3, 2}},
{{1, 2}, {2, 3}, {2, 2}},
{{2, 2}, {2, 3}, {3, 2}}},
result: Polygon{{{1, 2}, {2, 3}, {3, 2}, {2, 1}}},
},
{
subject: Polygon{{{1, 2}, {2, 2}, {2, 1}}},
clipping: Polygon{
{{1, 2}, {2, 3}, {2, 2}},
{{2, 2}, {2, 3}, {3, 2}}},
result: Polygon{{{1, 2}, {2, 3}, {3, 2}, {2, 2}, {2, 1}}},
},
// another variation, now with single degenerated curve
{
subject: Polygon{{{1, 2}, {2, 2}, {2, 1}}},
clipping: Polygon{
{{1, 2}, {2, 3}, {2, 2}, {2, 3}, {3, 2}}},
result: Polygon{{{1, 2}, {2, 3}, {3, 2}, {2, 2}, {2, 1}}},
},
{
subject: Polygon{{{1, 2}, {2, 2}, {2, 1}}},
clipping: Polygon{
{{2, 1}, {2, 2}, {2, 3}, {3, 2}},
{{1, 2}, {2, 3}, {2, 2}}},
result: Polygon{{{1, 2}, {2, 3}, {3, 2}, {2, 1}}},
},
// "union" wholly self-intersecting polygon
{
subject: Polygon{{{1, 2}, {2, 2}, {2, 1}}},
clipping: Polygon{{{1, 2}, {2, 2}, {2, 3}, {1, 2}, {2, 2}, {2, 3}}},
result: Polygon{{{1, 2}, {2, 3}, {2, 2}, {2, 1}}},
},
}
for i, c := range cases {
if i != 5 {
continue
}
result := dump(c.subject.Construct(UNION, c.clipping))
if result != dump(c.result) {
t.Errorf("case UNION:\nsubject: %v\nclipping: %v\nexpected: %v\ngot: %v",
c.subject, c.clipping, c.result, result)
}
}
}
func TestBug4(t *T) {
if Short() {
return
}
cases := []struct{ subject, clipping, result Polygon }{
// original reported github issue #4, resulting in infinite loop
{
subject: Polygon{{
{1.427255375e+06, -2.3283064365386963e-10},
{1.4271285e+06, 134.7111358642578},
{1.427109e+06, 178.30108642578125}}},
clipping: Polygon{{
{1.416e+06, -12000},
{1.428e+06, -12000},
{1.428e+06, 0},
{1.416e+06, 0},
{1.416e+06, -12000}}},
},
{
subject: Polygon{{
{1.427255375e+06, -2.3283064365386963e-10},
{1.4271285e+06, 134.7111358642578}, {1.427109e+06, 178.30108642578125}}},
clipping: Polygon{{
{1.416e+06, -12000}, {1.428e+06, -12000}, {1.428e+06, 0},
{1.416e+06, 0}, {1.416e+06, -12000}}},
},
{
subject: Polygon{
{Point{X: 1.7714672107465276e+06, Y: -102506.68254093888},
Point{X: 1.7713768917571804e+06, Y: -102000.75485953009},
Point{X: 1.7717109214841307e+06, Y: -101912.19625031832}}},
clipping: Polygon{
{Point{X: 1.7714593229229522e+06, Y: -102470.35230830211},
Point{X: 1.7714672107465276e+06, Y: -102506.68254093867},
Point{X: 1.771439738086082e+06, Y: -102512.92027456204}}},
},
{
subject: Polygon{{
Point{X: -1.8280000000000012e+06, Y: -492999.99999999953},
Point{X: -1.8289999999999995e+06, Y: -494000.0000000006},
Point{X: -1.828e+06, Y: -493999.9999999991},
Point{X: -1.8280000000000012e+06, Y: -492999.99999999953}}},
clipping: Polygon{{
Point{X: -1.8280000000000005e+06, Y: -495999.99999999977},
Point{X: -1.8280000000000007e+06, Y: -492000.0000000014},
Point{X: -1.8240000000000007e+06, Y: -492000.0000000014},
Point{X: -1.8280000000000005e+06, Y: -495999.99999999977}}},
},
{
subject: Polygon{{
Point{X: -2.0199999999999988e+06, Y: -394999.99999999825},
Point{X: -2.0199999999999988e+06, Y: -392000.0000000009},
Point{X: -2.0240000000000012e+06, Y: -395999.9999999993},
Point{X: -2.0199999999999988e+06, Y: -394999.99999999825}}},
clipping: Polygon{{
Point{X: -2.0199999999999988e+06, Y: -394999.99999999825},
Point{X: -2.020000000000001e+06, Y: -394000.0000000001},
Point{X: -2.0190000000000005e+06, Y: -394999.9999999997},
Point{X: -2.0199999999999988e+06, Y: -394999.99999999825}}},
},
{
subject: Polygon{{
Point{X: -47999.99999999992, Y: -23999.999999998756},
Point{X: 0, Y: -24000.00000000017},
Point{X: 0, Y: 24000.00000000017},
Point{X: -48000.00000000014, Y: 24000.00000000017},
Point{X: -47999.99999999992, Y: -23999.999999998756}}},
clipping: Polygon{{
Point{X: -48000, Y: -24000},
Point{X: 0, Y: -24000},
Point{X: 0, Y: 24000},
Point{X: -48000, Y: 24000},
Point{X: -48000, Y: -24000}}},
},
{
subject: Polygon{
Contour{
Point{X: -2.137000000000001e+06, Y: -122000.00000000093},
Point{X: -2.1360000000000005e+06, Y: -121999.99999999907},
Point{X: -2.1360000000000014e+06, Y: -121000.00000000186}},
},
clipping: Polygon{
Contour{
Point{X: -2.1120000000000005e+06, Y: -120000},
Point{X: -2.136000000000001e+06, Y: -120000.00000000093},
Point{X: -2.1360000000000005e+06, Y: -144000}}},
},
{
subject: Polygon{
Contour{
Point{X: 1.556e+06, Y: -1.139999999999999e+06},
Point{X: 1.5600000000000002e+06, Y: -1.140000000000001e+06},
Point{X: 1.56e+06, Y: -1.136000000000001e+06}}},
clipping: Polygon{
Contour{
Point{X: 1.56e+06, Y: -1.127999999999999e+06},
Point{X: 1.5600000000000002e+06, Y: -1.151999999999999e+06}}},
},
{
subject: Polygon{
Contour{
Point{X: 1.0958876176594219e+06, Y: -567467.5197556159},
Point{X: 1.0956330600760083e+06, Y: -567223.72588934},
Point{X: 1.0958876176594219e+06, Y: -567467.5197556159},
},
},
clipping: Polygon{
Contour{
Point{X: 1.0953516248896217e+06, Y: -564135.1861293605},
Point{X: 1.0959085007300845e+06, Y: -568241.1879245406},
Point{X: 1.0955136237022132e+06, Y: -581389.3748769956},
},
},
},
{
subject: Polygon{
[]Point{
Point{X: 608000, Y: -113151.36476426799},
Point{X: 608000, Y: -114660.04962779157},
Point{X: 612000, Y: -115414.39205955336},
Point{X: 1.616e+06, Y: -300000},
Point{X: 1.608e+06, Y: -303245.6575682382},
Point{X: 0, Y: 0},
},
},
clipping: Polygon{
[]Point{
Point{X: 1.612e+06, Y: -296000},
},
},
},
{
subject: Polygon{
Contour{
Point{X: 1.1458356382266793e+06, Y: -251939.4635597784},
Point{X: 1.1460824662209095e+06, Y: -251687.86194535438},
Point{X: 1.1458356382266793e+06, Y: -251939.4635597784},
}},
clipping: Polygon{
Contour{
Point{X: 1.1486683769211173e+06, Y: -251759.06331944838},
Point{X: 1.1468807511323579e+06, Y: -251379.90576799586},
Point{X: 1.1457914974731328e+06, Y: -251816.31287551578},
}},
},
}
for i, c := range cases {
// check that we get a result in finite time
ch := make(chan Polygon)
go func() {
ch <- c.subject.Construct(UNION, c.clipping)
}()
select {
case <-ch:
case <-time.After(1 * time.Second):
t.Errorf("case %d UNION:\nsubject: %v\nclipping: %v\ntimed out.", i, c.subject, c.clipping)
}
}
}
func TestBug5(t *T) {
rect := Polygon{{{24, 7}, {36, 7}, {36, 23}, {24, 23}}}
circle := Polygon{{{24, 7}, {24.83622770614123, 7.043824837053814}, {25.66329352654208, 7.174819194129555}, {26.472135954999587, 7.391547869638773}, {27.253893144606412, 7.691636338859195}, {28.00000000000001, 8.071796769724493}, {28.702282018339798, 8.527864045000424}, {29.35304485087088, 9.054841396180851}, {29.94515860381917, 9.646955149129141}, {30.472135954999597, 10.297717981660224}, {30.92820323027553, 11.00000000000001}, {31.308363661140827, 11.746106855393611}, {31.60845213036125, 12.527864045000435}, {31.825180805870467, 13.33670647345794}, {31.95617516294621, 14.16377229385879}, {32.00000000000002, 15.00000000000002}, {31.95617516294621, 15.83622770614125}, {31.825180805870467, 16.6632935265421}, {31.60845213036125, 17.472135954999604}, {31.308363661140827, 18.25389314460643}, {30.92820323027553, 19.00000000000003}, {30.472135954999597, 19.702282018339815}, {29.94515860381917, 20.353044850870898}, {29.35304485087088, 20.945158603819188}, {28.702282018339798, 21.472135954999615}, {28.00000000000001, 21.928203230275546}, {27.253893144606412, 22.308363661140845}, {26.472135954999587, 22.608452130361268}, {25.66329352654208, 22.825180805870485}, {24.83622770614123, 22.956175162946227}, {24, 23.00000000000004}, {23.16377229385877, 22.956175162946227}, {22.33670647345792, 22.825180805870485}, {21.527864045000413, 22.608452130361268}, {20.746106855393588, 22.308363661140845}, {19.99999999999999, 21.928203230275546}, {19.297717981660202, 21.472135954999615}, {18.64695514912912, 20.945158603819188}, {18.05484139618083, 20.353044850870898}, {17.527864045000403, 19.702282018339815}, {17.07179676972447, 19.00000000000003}, {16.691636338859173, 18.25389314460643}, {16.39154786963875, 17.472135954999604}, {16.174819194129533, 16.6632935265421}, {16.04382483705379, 15.83622770614125}, {15.999999999999977, 15.00000000000002}, {16.04382483705379, 14.16377229385879}, {16.174819194129533, 13.33670647345794}, {16.39154786963875, 12.527864045000435}, {16.691636338859173, 11.746106855393611}, {17.07179676972447, 11.00000000000001}, {17.527864045000403, 10.297717981660224}, {18.05484139618083, 9.646955149129141}, {18.64695514912912, 9.054841396180851}, {19.297717981660202, 8.527864045000424}, {19.99999999999999, 8.071796769724493}, {20.746106855393588, 7.691636338859194}, {21.527864045000413, 7.391547869638772}, {22.33670647345792, 7.1748191941295545}, {23.16377229385877, 7.043824837053813}}}
expected := []struct {
op Op
result Polygon
}{
{
UNION,
Polygon{{{36, 23}, {36, 7}, {24, 7}, {23.16377229385877, 7.043824837053813}, {22.33670647345792, 7.1748191941295545}, {21.527864045000413, 7.391547869638772}, {20.746106855393588, 7.691636338859194}, {19.99999999999999, 8.071796769724493}, {19.297717981660202, 8.527864045000424}, {18.64695514912912, 9.054841396180851}, {18.05484139618083, 9.646955149129141}, {17.527864045000403, 10.297717981660224}, {17.07179676972447, 11.00000000000001}, {16.691636338859173, 11.746106855393611}, {16.39154786963875, 12.527864045000435}, {16.174819194129533, 13.33670647345794}, {16.04382483705379, 14.16377229385879}, {15.999999999999977, 15.00000000000002}, {16.04382483705379, 15.83622770614125}, {16.174819194129533, 16.6632935265421}, {16.39154786963875, 17.472135954999604}, {16.691636338859173, 18.25389314460643}, {17.07179676972447, 19.00000000000003}, {17.527864045000403, 19.702282018339815}, {18.05484139618083, 20.353044850870898}, {18.64695514912912, 20.945158603819188}, {19.297717981660202, 21.472135954999615}, {19.99999999999999, 21.928203230275546}, {20.746106855393588, 22.308363661140845}, {21.527864045000413, 22.608452130361268}, {22.33670647345792, 22.825180805870485}, {23.16377229385877, 22.956175162946227}, {24, 23.00000000000004}, {24.000000000000746, 23}}},
},
{
INTERSECTION,
Polygon{{{31.95617516294621, 15.83622770614125}, {31.825180805870467, 16.6632935265421}, {31.60845213036125, 17.472135954999604}, {31.308363661140827, 18.25389314460643}, {30.92820323027553, 19.00000000000003}, {30.472135954999597, 19.702282018339815}, {29.94515860381917, 20.353044850870898}, {29.35304485087088, 20.945158603819188}, {28.702282018339798, 21.472135954999615}, {28.00000000000001, 21.928203230275546}, {27.253893144606412, 22.308363661140845}, {26.472135954999587, 22.608452130361268}, {25.66329352654208, 22.825180805870485}, {24.83622770614123, 22.956175162946227}, {24.000000000000746, 23}, {24, 23}, {24, 7}, {24.83622770614123, 7.043824837053814}, {25.66329352654208, 7.174819194129555}, {26.472135954999587, 7.391547869638773}, {27.253893144606412, 7.691636338859195}, {28.00000000000001, 8.071796769724493}, {28.702282018339798, 8.527864045000424}, {29.35304485087088, 9.054841396180851}, {29.94515860381917, 9.646955149129141}, {30.472135954999597, 10.297717981660224}, {30.92820323027553, 11.00000000000001}, {31.308363661140827, 11.746106855393611}, {31.60845213036125, 12.527864045000435}, {31.825180805870467, 13.33670647345794}, {31.95617516294621, 14.16377229385879}, {32.00000000000002, 15.00000000000002}}},
},
{
DIFFERENCE,
Polygon{{{24.000000000000746, 23}, {24.83622770614123, 22.956175162946227}, {25.66329352654208, 22.825180805870485}, {26.472135954999587, 22.608452130361268}, {27.253893144606412, 22.308363661140845}, {28.00000000000001, 21.928203230275546}, {28.702282018339798, 21.472135954999615}, {29.35304485087088, 20.945158603819188}, {29.94515860381917, 20.353044850870898}, {30.472135954999597, 19.702282018339815}, {30.92820323027553, 19.00000000000003}, {31.308363661140827, 18.25389314460643}, {31.60845213036125, 17.472135954999604}, {31.825180805870467, 16.6632935265421}, {31.95617516294621, 15.83622770614125}, {32.00000000000002, 15.00000000000002}, {31.95617516294621, 14.16377229385879}, {31.825180805870467, 13.33670647345794}, {31.60845213036125, 12.527864045000435}, {31.308363661140827, 11.746106855393611}, {30.92820323027553, 11.00000000000001}, {30.472135954999597, 10.297717981660224}, {29.94515860381917, 9.646955149129141}, {29.35304485087088, 9.054841396180851}, {28.702282018339798, 8.527864045000424}, {28.00000000000001, 8.071796769724493}, {27.253893144606412, 7.691636338859195}, {26.472135954999587, 7.391547869638773}, {25.66329352654208, 7.174819194129555}, {24.83622770614123, 7.043824837053814}, {24, 7}, {36, 7}, {36, 23}}},
},
{
XOR,
Polygon{
{{24.000000000000746, 23}, {24, 23}, {24, 7}, {23.16377229385877, 7.043824837053813}, {22.33670647345792, 7.1748191941295545}, {21.527864045000413, 7.391547869638772}, {20.746106855393588, 7.691636338859194}, {19.99999999999999, 8.071796769724493}, {19.297717981660202, 8.527864045000424}, {18.64695514912912, 9.054841396180851}, {18.05484139618083, 9.646955149129141}, {17.527864045000403, 10.297717981660224}, {17.07179676972447, 11.00000000000001}, {16.691636338859173, 11.746106855393611}, {16.39154786963875, 12.527864045000435}, {16.174819194129533, 13.33670647345794}, {16.04382483705379, 14.16377229385879}, {15.999999999999977, 15.00000000000002}, {16.04382483705379, 15.83622770614125}, {16.174819194129533, 16.6632935265421}, {16.39154786963875, 17.472135954999604}, {16.691636338859173, 18.25389314460643}, {17.07179676972447, 19.00000000000003}, {17.527864045000403, 19.702282018339815}, {18.05484139618083, 20.353044850870898}, {18.64695514912912, 20.945158603819188}, {19.297717981660202, 21.472135954999615}, {19.99999999999999, 21.928203230275546}, {20.746106855393588, 22.308363661140845}, {21.527864045000413, 22.608452130361268}, {22.33670647345792, 22.825180805870485}, {23.16377229385877, 22.956175162946227}, {24, 23.00000000000004}},
{{24.000000000000746, 23}, {24.83622770614123, 22.956175162946227}, {25.66329352654208, 22.825180805870485}, {26.472135954999587, 22.608452130361268}, {27.253893144606412, 22.308363661140845}, {28.00000000000001, 21.928203230275546}, {28.702282018339798, 21.472135954999615}, {29.35304485087088, 20.945158603819188}, {29.94515860381917, 20.353044850870898}, {30.472135954999597, 19.702282018339815}, {30.92820323027553, 19.00000000000003}, {31.308363661140827, 18.25389314460643}, {31.60845213036125, 17.472135954999604}, {31.825180805870467, 16.6632935265421}, {31.95617516294621, 15.83622770614125}, {32.00000000000002, 15.00000000000002}, {31.95617516294621, 14.16377229385879}, {31.825180805870467, 13.33670647345794}, {31.60845213036125, 12.527864045000435}, {31.308363661140827, 11.746106855393611}, {30.92820323027553, 11.00000000000001}, {30.472135954999597, 10.297717981660224}, {29.94515860381917, 9.646955149129141}, {29.35304485087088, 9.054841396180851}, {28.702282018339798, 8.527864045000424}, {28.00000000000001, 8.071796769724493}, {27.253893144606412, 7.691636338859195}, {26.472135954999587, 7.391547869638773}, {25.66329352654208, 7.174819194129555}, {24.83622770614123, 7.043824837053814}, {24, 7}, {36, 7}, {36, 23}},
},
},
}
for _, e := range expected {
result := rect.Construct(e.op, circle)
if dump(result) != dump(e.result) {
t.Errorf("case %d expected:\n%v\ngot:\n%v", e.op, dump(e.result), dump(result))
}
}
}