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