-
Notifications
You must be signed in to change notification settings - Fork 20
/
bugs_test.go
192 lines (175 loc) · 13 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
package polyclip_test
import (
"fmt"
"sort"
. "testing"
"time"
"github.com/akavel/polyclip-go"
)
type sorter polyclip.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 polyclip.Polygon) polyclip.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 polyclip.Polygon) string {
return fmt.Sprintf("%v", normalize(poly))
}
func TestBug3(t *T) {
cases := []struct{ subject, clipping, result polyclip.Polygon }{
// original reported github issue #3
{
subject: polyclip.Polygon{{{1, 1}, {1, 2}, {2, 2}, {2, 1}}},
clipping: polyclip.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: polyclip.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: polyclip.Polygon{{{1, 2}, {2, 2}, {2, 1}}},
clipping: polyclip.Polygon{
{{2, 1}, {2, 2}, {3, 2}},
{{1, 2}, {2, 3}, {2, 2}},
{{2, 2}, {2, 3}, {3, 2}}},
result: polyclip.Polygon{{{1, 2}, {2, 3}, {3, 2}, {2, 1}}},
},
{
subject: polyclip.Polygon{{{1, 2}, {2, 2}, {2, 1}}},
clipping: polyclip.Polygon{
{{1, 2}, {2, 3}, {2, 2}},
{{2, 2}, {2, 3}, {3, 2}}},
result: polyclip.Polygon{{{1, 2}, {2, 3}, {3, 2}, {2, 2}, {2, 1}}},
},
// another variation, now with single degenerated curve
{
subject: polyclip.Polygon{{{1, 2}, {2, 2}, {2, 1}}},
clipping: polyclip.Polygon{
{{1, 2}, {2, 3}, {2, 2}, {2, 3}, {3, 2}}},
result: polyclip.Polygon{{{1, 2}, {2, 3}, {3, 2}, {2, 2}, {2, 1}}},
},
{
subject: polyclip.Polygon{{{1, 2}, {2, 2}, {2, 1}}},
clipping: polyclip.Polygon{
{{2, 1}, {2, 2}, {2, 3}, {3, 2}},
{{1, 2}, {2, 3}, {2, 2}}},
result: polyclip.Polygon{{{1, 2}, {2, 3}, {3, 2}, {2, 1}}},
},
// "union" with effectively empty polygon (wholly self-intersecting)
{
subject: polyclip.Polygon{{{1, 2}, {2, 2}, {2, 1}}},
clipping: polyclip.Polygon{{{1, 2}, {2, 2}, {2, 3}, {1, 2}, {2, 2}, {2, 3}}},
result: polyclip.Polygon{{{1, 2}, {2, 2}, {2, 1}}},
},
}
for _, c := range cases {
result := dump(c.subject.Construct(polyclip.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 polyclip.Polygon }{
// original reported github issue #4, resulting in infinite loop
{
subject: polyclip.Polygon{{
{1.427255375e+06, -2.3283064365386963e-10},
{1.4271285e+06, 134.7111358642578},
{1.427109e+06, 178.30108642578125}}},
clipping: polyclip.Polygon{{
{1.416e+06, -12000},
{1.428e+06, -12000},
{1.428e+06, 0},
{1.416e+06, 0},
{1.416e+06, -12000}}},
},
}
for _, c := range cases {
// check that we get a result in finite time
ch := make(chan polyclip.Polygon)
go func() {
ch <- c.subject.Construct(polyclip.UNION, c.clipping)
}()
select {
case <-ch:
case <-time.After(1 * time.Second):
// panicking in attempt to get full stacktrace
panic(fmt.Sprintf("case UNION:\nsubject: %v\nclipping: %v\ntimed out.", c.subject, c.clipping))
}
}
}
func TestBug5(t *T) {
rect := polyclip.Polygon{{{24, 7}, {36, 7}, {36, 23}, {24, 23}}}
circle := polyclip.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 polyclip.Op
result polyclip.Polygon
}{
{
polyclip.UNION,
polyclip.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}}},
},
{
polyclip.INTERSECTION,
polyclip.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}}},
},
{
polyclip.DIFFERENCE,
polyclip.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}}},
},
{
polyclip.XOR,
polyclip.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))
}
}
}