1 // Some tests for vgl_polygon
2 // Amitha Perera, Sep 2001.
3 #include <iostream>
4 #include <fstream>
5 #include "testlib/testlib_test.h"
6 #include "vgl/vgl_polygon.h"
7 #ifdef _MSC_VER
8 # include "vcl_msvc_warnings.h"
9 #endif
10
11 static void
test_simple_polygon()12 test_simple_polygon()
13 {
14 std::cout << "Simple polygon\n";
15
16 // Simple triangle
17 vgl_polygon<double> p;
18 p.new_sheet();
19 p.push_back(0.0, 0.0);
20 p.push_back(5.0, 0.0);
21 p.push_back(5.0, 1.0);
22 p.print(std::cout);
23
24 TEST("inside (1)", p.contains(0.0, 0.0), true);
25 TEST("inside (2)", p.contains(5.0, 0.0), true);
26 TEST("inside (3)", p.contains(5.0, 1.0), true);
27 TEST("inside (4)", p.contains(2.5, 0.0), true);
28 TEST("inside (5)", p.contains(2.5, 0.3), true);
29 TEST("inside (6)", p.contains(2.5, 0.5), true);
30 TEST("inside (7)", p.contains(5.0, 0.5), true);
31 TEST("outside (1)", p.contains(2.5, 0.6), false);
32 TEST("outside (2)", p.contains(5.1, 0.1), false);
33 TEST("outside (3)", p.contains(5.1, 0.0), false);
34 TEST("outside (4)", p.contains(5.0, 1.1), false);
35 TEST("outside (5)", p.contains(5.0, -0.1), false);
36 TEST("outside (6)", p.contains(2.0, -1.0), false);
37 TEST("outside (7)", p.contains(-2.5, -0.5), false);
38 }
39
40 static void
test_disjoint_polygon()41 test_disjoint_polygon()
42 {
43 std::cout << "Disjoint polygons\n";
44
45 // Simple triangle
46 vgl_polygon<float> p;
47 p.new_sheet();
48 p.push_back(0.0f, 0.0f);
49 p.push_back(5.0f, 0.0f);
50 p.push_back(5.0f, 1.0f);
51 // Another disjoint triangle
52 p.new_sheet();
53 p.push_back(10.0f, 10.0f);
54 p.push_back(15.0f, 10.0f);
55 p.push_back(15.0f, 11.0f);
56 p.print(std::cout);
57
58 TEST("inside poly1", p.contains(2.5f, 0.3f), true);
59 TEST("inside poly2", p.contains(12.5f, 10.3f), true);
60 TEST("outside (1)", p.contains(2.5f, 0.6f), false);
61 TEST("outside (2)", p.contains(5.0f, 1.1f), false);
62 TEST("outside (3)", p.contains(5.1f, 0.0f), false);
63 TEST("outside (4)", p.contains(2.0f, -1.0f), false);
64 TEST("outside (5)", p.contains(-2.5f, -0.5f), false);
65 TEST("oustide (6)", p.contains(12.5f, 10.6f), false);
66 TEST("outside (7)", p.contains(15.0f, 9.0f), false);
67 }
68
69 static void
test_holey_polygon()70 test_holey_polygon()
71 {
72 std::cout << "Polygon with holes\n";
73
74 // Simple triangle
75 vgl_polygon<double> p;
76 p.new_sheet();
77 p.push_back(0.0, 0.0);
78 p.push_back(5.0, 0.0);
79 p.push_back(5.0, 1.0);
80 // A hole
81 p.new_sheet();
82 p.push_back(3.0, 0.5);
83 p.push_back(4.0, 0.5);
84 p.push_back(4.0, 0.1);
85 p.print(std::cout);
86
87 TEST("inside", p.contains(2.5, 0.3), true);
88 TEST("outside (1)", p.contains(2.5, 0.6), false);
89 TEST("outside (2)", p.contains(5.0, 1.1), false);
90 TEST("outside (3)", p.contains(5.1, 0.0), false);
91 TEST("outside (4)", p.contains(2.0, -1.0), false);
92 TEST("outside (5)", p.contains(-2.5, -0.5), false);
93 TEST("outside (6)", p.contains(3.9, 0.4), false);
94 std::ofstream os("./temp");
95 p.print(os);
96 // read the poly
97 os.close();
98 std::ifstream is("./temp");
99 vgl_polygon<double> pr;
100 is >> pr;
101 pr.print(std::cout);
102 TEST("inside after read", pr.contains(2.5, 0.3), true);
103 }
104
105 static void
test_self_intersection()106 test_self_intersection()
107 {
108 std::cout << "compute polygon self intersections\n";
109 std::vector<std::pair<unsigned, unsigned>> e1, e2;
110 std::vector<vgl_point_2d<double>> ip;
111
112 {
113 vgl_polygon<double> p;
114 // non-self-intersecting quad
115 p.new_sheet();
116 p.push_back(0.0, 0.0);
117 p.push_back(1.0, 0.0);
118 p.push_back(1.0, 1.0);
119 p.push_back(0.0, 1.0);
120
121 vgl_selfintersections(p, e1, e2, ip);
122 TEST("non-self-intersecting quad", e1.empty() && e2.empty() && ip.empty(), true);
123 }
124
125 {
126 vgl_polygon<double> p;
127 // simple self intersecting quad
128 p.new_sheet();
129 p.push_back(0.0, 0.0);
130 p.push_back(1.0, 1.0);
131 p.push_back(0.0, 1.0);
132 p.push_back(1.0, 0.0);
133
134 vgl_selfintersections(p, e1, e2, ip);
135 TEST("simple self-intersecting quad",
136 e1.size() == 1 && e1[0].first == 0 && e1[0].second == 0 && e2[0].first == 0 && e2[0].second == 2 &&
137 ip[0] == vgl_point_2d<double>(0.5, 0.5),
138 true);
139 }
140 {
141 vgl_polygon<double> p;
142 // non-self-intersecting polygon with collinear segments
143 p.new_sheet();
144 p.push_back(0.0, 0.0);
145 p.push_back(1.0, 0.0);
146 p.push_back(1.0, 1.0);
147 p.push_back(2.0, 1.0);
148 p.push_back(2.0, 0.0);
149 p.push_back(3.0, 0.0);
150 p.push_back(3.0, 1.0);
151 p.push_back(4.0, 1.0);
152 p.push_back(4.0, 2.0);
153 p.push_back(0.0, 2.0);
154
155 vgl_selfintersections(p, e1, e2, ip);
156 TEST("collinear non-self-intersecting polygon ", e1.empty() && e2.empty() && ip.empty(), true);
157 }
158 {
159 vgl_polygon<double> p;
160 // multisheet self-intersecting polygon
161 p.new_sheet();
162 p.push_back(0.0, 0.0);
163 p.push_back(1.0, 1.0);
164 p.push_back(0.0, 1.0);
165 p.push_back(1.0, 0.0);
166 p.new_sheet();
167 p.push_back(-1.0, -1.0);
168 p.push_back(-1.0, 2.0);
169 p.push_back(2.0, 2.0);
170 p.push_back(2.0, -1.0);
171 p.new_sheet();
172 p.push_back(0.5, 0.75);
173 p.push_back(2.5, 0.75);
174 p.push_back(2.5, 2.5);
175 p.push_back(0.5, 2.5);
176
177 // the correct solutions, but order may be incorrect
178 typedef std::pair<unsigned, unsigned> upair;
179 std::vector<upair> e1s(5), e2s(5);
180 std::vector<vgl_point_2d<double>> ips(5);
181 e1s[0] = upair(0, 0);
182 e2s[0] = upair(0, 2);
183 ips[0] = vgl_point_2d<double>(.5, .5);
184 e1s[1] = upair(0, 0);
185 e2s[1] = upair(2, 0);
186 ips[1] = vgl_point_2d<double>(.75, .75);
187 e1s[2] = upair(0, 1);
188 e2s[2] = upair(2, 3);
189 ips[2] = vgl_point_2d<double>(.5, 1);
190 e1s[3] = upair(1, 1);
191 e2s[3] = upair(2, 3);
192 ips[3] = vgl_point_2d<double>(.5, 2);
193 e1s[4] = upair(1, 2);
194 e2s[4] = upair(2, 0);
195 ips[4] = vgl_point_2d<double>(2, .75);
196
197 vgl_selfintersections(p, e1, e2, ip);
198 bool valid = e1.size() == 5;
199 for (unsigned int i = 0; valid && i < 5; ++i)
200 {
201 bool match = false;
202 for (unsigned int j = 0; valid && j < e1s.size(); ++j)
203 {
204 if (e1[i] == e1s[j] && e2[i] == e2s[j] && ip[i] == ips[j])
205 {
206 e1s.erase(e1s.begin() + j);
207 e2s.erase(e2s.begin() + j);
208 ips.erase(ips.begin() + j);
209 match = true;
210 break;
211 }
212 }
213 if (!match)
214 valid = false;
215 }
216 TEST("multisheet self-intersecting polygon", valid, true);
217 }
218 {
219 vgl_polygon<double> p;
220 // self-intersections at points
221 p.new_sheet();
222 p.push_back(-1.0, 0.0);
223 p.push_back(0.0, 1.0);
224 p.push_back(2.0, 1.0);
225 p.push_back(2.0, 0.0);
226 p.push_back(0.0, 1.0);
227 p.push_back(-1.0, 3.0);
228 p.new_sheet();
229 p.push_back(-2.0, 3.0);
230 p.push_back(-2.0, 0.0);
231 p.push_back(0.0, 0.0);
232 p.push_back(0.0, 3.0);
233
234 // the correct solutions, but order may be incorrect
235 typedef std::pair<unsigned, unsigned> upair;
236 std::vector<upair> e1s(12), e2s(12);
237 std::vector<vgl_point_2d<double>> ips(12);
238 e1s[0] = upair(0, 0);
239 e2s[0] = upair(0, 3);
240 ips[0] = vgl_point_2d<double>(0, 1);
241 e1s[1] = upair(0, 1);
242 e2s[1] = upair(0, 3);
243 ips[1] = vgl_point_2d<double>(0, 1);
244 e1s[2] = upair(0, 0);
245 e2s[2] = upair(0, 4);
246 ips[2] = vgl_point_2d<double>(0, 1);
247 e1s[3] = upair(0, 1);
248 e2s[3] = upair(0, 4);
249 ips[3] = vgl_point_2d<double>(0, 1);
250 e1s[4] = upair(0, 0);
251 e2s[4] = upair(1, 2);
252 ips[4] = vgl_point_2d<double>(0, 1);
253 e1s[5] = upair(0, 1);
254 e2s[5] = upair(1, 2);
255 ips[5] = vgl_point_2d<double>(0, 1);
256 e1s[6] = upair(0, 3);
257 e2s[6] = upair(1, 2);
258 ips[6] = vgl_point_2d<double>(0, 1);
259 e1s[7] = upair(0, 4);
260 e2s[7] = upair(1, 2);
261 ips[7] = vgl_point_2d<double>(0, 1);
262 e1s[8] = upair(0, 0);
263 e2s[8] = upair(1, 1);
264 ips[8] = vgl_point_2d<double>(-1, 0);
265 e1s[9] = upair(0, 5);
266 e2s[9] = upair(1, 1);
267 ips[9] = vgl_point_2d<double>(-1, 0);
268 e1s[10] = upair(0, 4);
269 e2s[10] = upair(1, 3);
270 ips[10] = vgl_point_2d<double>(-1, 3);
271 e1s[11] = upair(0, 5);
272 e2s[11] = upair(1, 3);
273 ips[11] = vgl_point_2d<double>(-1, 3);
274
275 vgl_selfintersections(p, e1, e2, ip);
276 bool valid = e1.size() == 12;
277 for (unsigned int i = 0; valid && i < 12; ++i)
278 {
279 bool match = false;
280 for (unsigned int j = 0; valid && j < e1s.size(); ++j)
281 {
282 if (e1[i] == e1s[j] && e2[i] == e2s[j] && ip[i] == ips[j])
283 {
284 e1s.erase(e1s.begin() + j);
285 e2s.erase(e2s.begin() + j);
286 ips.erase(ips.begin() + j);
287 match = true;
288 break;
289 }
290 }
291 if (!match)
292 valid = false;
293 }
294 TEST("self-intersections at points", valid, true);
295 }
296 }
297
298 static void
test_polygon()299 test_polygon()
300 {
301 test_simple_polygon();
302 test_disjoint_polygon();
303 test_holey_polygon();
304 test_self_intersection();
305 }
306
307 TESTMAIN(test_polygon);
308