1 /*
2 Copyright 2008 Intel Corporation
3
4 Use, modification and distribution are subject to the Boost Software License,
5 Version 1.0. (See accompanying file LICENSE_1_0.txt or copy at
6 http://www.boost.org/LICENSE_1_0.txt).
7 */
8 #include <iostream>
9 #define BOOST_POLYGON_NO_DEPS
10 #include <boost/polygon/polygon.hpp>
11
12 namespace gtl = boost::polygon;
13 using namespace boost::polygon::operators;
14 #include <time.h>
15 #include <stdlib.h>
16
assert_s(bool c,std::string msg)17 void assert_s(bool c, std::string msg) {
18 if(!c) {
19 std::cout << msg << std::endl;
20 exit( 1);
21 }
22 }
23
24 namespace boost { namespace polygon{
addpoly(polygon_45_set_data<int> & pset,int * pts,unsigned int numpts)25 void addpoly(polygon_45_set_data<int>& pset,
26 int* pts, unsigned int numpts) {
27 std::vector<point_data<int> > mppts;
28 for(unsigned int i = 0; i < numpts*2; i += 2) {
29 point_data<int> pt(pts[i], pts[i+1]);
30 mppts.push_back(pt);
31 }
32 polygon_45_data<int> poly;
33 poly.set(mppts.begin(), mppts.end());
34 pset += poly;
35 }
36
37 template <class T>
operator <<(std::ostream & o,const interval_data<T> & i)38 std::ostream& operator << (std::ostream& o, const interval_data<T>& i)
39 {
40 return o << i.get(LOW) << ' ' << i.get(HIGH);
41 }
42 template <class T>
operator <<(std::ostream & o,const point_data<T> & r)43 std::ostream& operator << (std::ostream& o, const point_data<T>& r)
44 {
45 return o << r.get(HORIZONTAL) << ' ' << r.get(VERTICAL);
46 }
47 template <typename T>
operator <<(std::ostream & o,const polygon_45_data<T> & poly)48 std::ostream& operator<<(std::ostream& o, const polygon_45_data<T>& poly) {
49 o << "Polygon { ";
50 for(typename polygon_45_data<T>::iterator_type itr = poly.begin();
51 itr != poly.end(); ++itr) {
52 if(itr != poly.begin()) o << ", ";
53 o << (*itr).get(HORIZONTAL) << " " << (*itr).get(VERTICAL);
54 }
55 o << " } ";
56 return o;
57 }
58 template <typename Unit>
operator <<(std::ostream & o,const polygon_45_set_data<Unit> & p)59 inline std::ostream& operator<< (std::ostream& o, const polygon_45_set_data<Unit>& p) {
60 o << "Polygon45Set ";
61 o << " " << !p.sorted() << " " << p.dirty() << " { ";
62 for(typename polygon_45_set_data<Unit>::iterator_type itr = p.begin();
63 itr != p.end(); ++itr) {
64 o << (*itr).pt << ":";
65 for(unsigned int i = 0; i < 4; ++i) {
66 o << (*itr).count[i] << ",";
67 } o << " ";
68 //o << (*itr).first << ":" << (*itr).second << "; ";
69 }
70 o << "} ";
71 return o;
72 }
73
74 template <typename Unit>
operator >>(std::istream & i,polygon_45_set_data<Unit> & p)75 inline std::istream& operator>> (std::istream& i, polygon_45_set_data<Unit>& p) {
76 //TODO
77 return i;
78 }
79 template <typename T>
operator <<(std::ostream & o,const polygon_90_data<T> & r)80 std::ostream& operator << (std::ostream& o, const polygon_90_data<T>& r)
81 {
82 o << "Polygon { ";
83 for(typename polygon_90_data<T>::iterator_type itr = r.begin(); itr != r.end(); ++itr) {
84 o << *itr << ", ";
85 }
86 return o << "} ";
87 }
88
89 template <typename T>
operator >>(std::istream & i,polygon_90_data<T> & r)90 std::istream& operator >> (std::istream& i, polygon_90_data<T>& r)
91 {
92 std::size_t size;
93 i >> size;
94 std::vector<T> vec;
95 vec.reserve(size);
96 for(std::size_t ii = 0; ii < size; ++ii) {
97 T coord;
98 i >> coord;
99 vec.push_back(coord);
100 }
101 r.set_compact(vec.begin(), vec.end());
102 return i;
103 }
104
105 template <typename T>
operator <<(std::ostream & o,const std::vector<polygon_90_data<T>> & r)106 std::ostream& operator << (std::ostream& o, const std::vector<polygon_90_data<T> >& r) {
107 o << r.size() << ' ';
108 for(std::size_t ii = 0; ii < r.size(); ++ii) {
109 o << (r[ii]);
110 }
111 return o;
112 }
113 template <typename T>
operator >>(std::istream & i,std::vector<polygon_90_data<T>> & r)114 std::istream& operator >> (std::istream& i, std::vector<polygon_90_data<T> >& r) {
115 std::size_t size;
116 i >> size;
117 r.clear();
118 r.reserve(size);
119 for(std::size_t ii = 0; ii < size; ++ii) {
120 polygon_90_data<T> tmp;
121 i >> tmp;
122 r.push_back(tmp);
123 }
124 return i;
125 }
126 template <typename T>
operator <<(std::ostream & o,const polygon_data<T> & poly)127 std::ostream& operator<<(std::ostream& o, const polygon_data<T>& poly) {
128 o << "Polygon { ";
129 for(typename polygon_data<T>::iterator_type itr = poly.begin();
130 itr != poly.end(); ++itr) {
131 if(itr != poly.begin()) o << ", ";
132 o << (*itr).get(HORIZONTAL) << " " << (*itr).get(VERTICAL);
133 }
134 o << " } ";
135 return o;
136 }
137 template <typename T>
operator <<(std::ostream & o,const polygon_set_data<T> & r)138 std::ostream& operator << (std::ostream& o, const polygon_set_data<T>& r)
139 {
140 o << "Polygon Set Data { ";
141 for(typename polygon_set_data<T>::iterator_type itr = r.begin(); itr != r.end(); ++itr) {
142 o << "<" << (*itr).first.first << ", " << (*itr).first.second << ">:" << (*itr).second << " ";
143 }
144 o << "} ";
145 return o;
146 }
147 template <typename T>
operator <<(std::ostream & o,const polygon_90_with_holes_data<T> & poly)148 std::ostream& operator<<(std::ostream& o, const polygon_90_with_holes_data<T>& poly) {
149 o << "Polygon With Holes { ";
150 for(typename polygon_90_with_holes_data<T>::iterator_type itr = poly.begin();
151 itr != poly.end(); ++itr) {
152 if(itr != poly.begin()) o << ", ";
153 o << (*itr).get(HORIZONTAL) << " " << (*itr).get(VERTICAL);
154 } o << " { ";
155 for(typename polygon_90_with_holes_data<T>::iterator_holes_type itr = poly.begin_holes();
156 itr != poly.end_holes(); ++itr) {
157 o << (*itr);
158 }
159 o << " } } ";
160 return o;
161 }
162 template <typename T>
operator <<(std::ostream & o,const polygon_45_with_holes_data<T> & poly)163 std::ostream& operator<<(std::ostream& o, const polygon_45_with_holes_data<T>& poly) {
164 o << "Polygon With Holes { ";
165 for(typename polygon_45_with_holes_data<T>::iterator_type itr = poly.begin();
166 itr != poly.end(); ++itr) {
167 if(itr != poly.begin()) o << ", ";
168 o << (*itr).get(HORIZONTAL) << " " << (*itr).get(VERTICAL);
169 } o << " { ";
170 for(typename polygon_45_with_holes_data<T>::iterator_holes_type itr = poly.begin_holes();
171 itr != poly.end_holes(); ++itr) {
172 o << (*itr);
173 }
174 o << " } } ";
175 return o;
176 }
177 template <typename T>
operator <<(std::ostream & o,const polygon_with_holes_data<T> & poly)178 std::ostream& operator<<(std::ostream& o, const polygon_with_holes_data<T>& poly) {
179 o << "Polygon With Holes { ";
180 for(typename polygon_with_holes_data<T>::iterator_type itr = poly.begin();
181 itr != poly.end(); ++itr) {
182 if(itr != poly.begin()) o << ", ";
183 o << (*itr).get(HORIZONTAL) << " " << (*itr).get(VERTICAL);
184 } o << " { ";
185 for(typename polygon_with_holes_data<T>::iterator_holes_type itr = poly.begin_holes();
186 itr != poly.end_holes(); ++itr) {
187 o << (*itr);
188 }
189 o << " } } ";
190 return o;
191 }
192 template <class T>
operator <<(std::ostream & o,const rectangle_data<T> & r)193 std::ostream& operator << (std::ostream& o, const rectangle_data<T>& r)
194 {
195 return o << r.get(HORIZONTAL) << ' ' << r.get(VERTICAL);
196 }
197 template <class T>
operator <<(std::ostream & o,const segment_data<T> & r)198 std::ostream& operator << (std::ostream& o, const segment_data<T>& r)
199 {
200 return o << r.get(LOW) << ' ' << r.get(HIGH);
201 }
202
203
204 template <typename T>
205 typename enable_if<typename is_polygon_90_set_type<T>::type, void>::type
print_is_polygon_90_set_concept(const T &)206 print_is_polygon_90_set_concept(const T& ) { std::cout << "is polygon 90 set concept\n"; }
207 template <typename T>
208 typename enable_if<typename is_mutable_polygon_90_set_type<T>::type, void>::type
print_is_mutable_polygon_90_set_concept(const T &)209 print_is_mutable_polygon_90_set_concept(const T& ) { std::cout << "is mutable polygon 90 set concept\n"; }
210 namespace boolean_op {
211 //self contained unit test for BooleanOr algorithm
212 template <typename Unit>
testBooleanOr()213 inline bool testBooleanOr() {
214 BooleanOp<int, Unit> booleanOr;
215 //test one rectangle
216 std::vector<std::pair<interval_data<Unit>, int> > container;
217 booleanOr.processInterval(container, interval_data<Unit>(0, 10), 1);
218 booleanOr.advanceScan();
219 booleanOr.processInterval(container, interval_data<Unit>(0, 10), -1);
220 if(container.size() != 2) {
221 std::cout << "Test one rectangle, wrong output size\n";
222 return false;
223 }
224 if(container[0] != std::pair<interval_data<Unit>, int>(interval_data<Unit>(0, 10), 1)) {
225 std::cout << "Test one rectangle, first output wrong: Interval(" <<
226 container[0].first << "), " << container[0].second << std::endl;
227 }
228 if(container[1] != std::pair<interval_data<Unit>, int>(interval_data<Unit>(0, 10), -1)) {
229 std::cout << "Test one rectangle, second output wrong: Interval(" <<
230 container[1].first << "), " << container[1].second << std::endl;
231 }
232
233 //test two rectangles
234 container.clear();
235 booleanOr = BooleanOp<int, Unit>();
236 booleanOr.processInterval(container, interval_data<Unit>(0, 10), 1);
237 booleanOr.advanceScan();
238 booleanOr.processInterval(container, interval_data<Unit>(5, 15), 1);
239 booleanOr.advanceScan();
240 booleanOr.processInterval(container, interval_data<Unit>(0, 10), -1);
241 booleanOr.advanceScan();
242 booleanOr.processInterval(container, interval_data<Unit>(5, 15), -1);
243 if(container.size() != 4) {
244 std::cout << "Test two rectangles, wrong output size\n";
245 for(std::size_t i = 0; i < container.size(); ++i){
246 std::cout << container[i].first << "), " << container[i].second << std::endl;
247 }
248 return false;
249 }
250 if(container[0] != std::pair<interval_data<Unit>, int>(interval_data<Unit>(0, 10), 1)) {
251 std::cout << "Test two rectangles, first output wrong: Interval(" <<
252 container[0].first << "), " << container[0].second << std::endl;
253 }
254 if(container[1] != std::pair<interval_data<Unit>, int>(interval_data<Unit>(10, 15), 1)) {
255 std::cout << "Test two rectangles, second output wrong: Interval(" <<
256 container[1].first << "), " << container[1].second << std::endl;
257 }
258 if(container[2] != std::pair<interval_data<Unit>, int>(interval_data<Unit>(0, 5), -1)) {
259 std::cout << "Test two rectangles, third output wrong: Interval(" <<
260 container[2].first << "), " << container[2].second << std::endl;
261 }
262 if(container[3] != std::pair<interval_data<Unit>, int>(interval_data<Unit>(5, 15), -1)) {
263 std::cout << "Test two rectangles, fourth output wrong: Interval(" <<
264 container[3].first << "), " << container[3].second << std::endl;
265 }
266
267 //test two rectangles
268 container.clear();
269 booleanOr = BooleanOp<int, Unit>();
270 booleanOr.processInterval(container, interval_data<Unit>(5, 15), 1);
271 booleanOr.advanceScan();
272 booleanOr.processInterval(container, interval_data<Unit>(0, 10), 1);
273 booleanOr.advanceScan();
274 booleanOr.processInterval(container, interval_data<Unit>(5, 15), -1);
275 booleanOr.advanceScan();
276 booleanOr.processInterval(container, interval_data<Unit>(0, 10), -1);
277 if(container.size() != 4) {
278 std::cout << "Test other two rectangles, wrong output size\n";
279 for(std::size_t i = 0; i < container.size(); ++i){
280 std::cout << container[i].first << "), " << container[i].second << std::endl;
281 }
282 return false;
283 }
284 if(container[0] != std::pair<interval_data<Unit>, int>(interval_data<Unit>(5, 15), 1)) {
285 std::cout << "Test other two rectangles, first output wrong: Interval(" <<
286 container[0].first << "), " << container[0].second << std::endl;
287 }
288 if(container[1] != std::pair<interval_data<Unit>, int>(interval_data<Unit>(0, 5), 1)) {
289 std::cout << "Test other two rectangles, second output wrong: Interval(" <<
290 container[1].first << "), " << container[1].second << std::endl;
291 }
292 if(container[2] != std::pair<interval_data<Unit>, int>(interval_data<Unit>(10, 15), -1)) {
293 std::cout << "Test other two rectangles, third output wrong: Interval(" <<
294 container[2].first << "), " << container[2].second << std::endl;
295 }
296 if(container[3] != std::pair<interval_data<Unit>, int>(interval_data<Unit>(0, 10), -1)) {
297 std::cout << "Test other two rectangles, fourth output wrong: Interval(" <<
298 container[3].first << "), " << container[3].second << std::endl;
299 }
300
301 //test two nonoverlapping rectangles
302 container.clear();
303 booleanOr = BooleanOp<int, Unit>();
304 booleanOr.processInterval(container, interval_data<Unit>(0, 10), 1);
305 booleanOr.advanceScan();
306 booleanOr.processInterval(container, interval_data<Unit>(15, 25), 1);
307 booleanOr.advanceScan();
308 booleanOr.processInterval(container, interval_data<Unit>(0, 10), -1);
309 booleanOr.advanceScan();
310 booleanOr.processInterval(container, interval_data<Unit>(15, 25), -1);
311 if(container.size() != 4) {
312 std::cout << "Test two nonoverlapping rectangles, wrong output size\n";
313 return false;
314 }
315 if(container[0] != std::pair<interval_data<Unit>, int>(interval_data<Unit>(0, 10), 1)) {
316 std::cout << "Test two nonoverlapping rectangles, first output wrong: Interval(" <<
317 container[0].first << "), " << container[0].second << std::endl;
318 }
319 if(container[1] != std::pair<interval_data<Unit>, int>(interval_data<Unit>(15, 25), 1)) {
320 std::cout << "Test two nonoverlapping rectangles, second output wrong: Interval(" <<
321 container[1].first << "), " << container[1].second << std::endl;
322 }
323 if(container[2] != std::pair<interval_data<Unit>, int>(interval_data<Unit>(0, 10), -1)) {
324 std::cout << "Test two nonoverlapping rectangles, third output wrong: Interval(" <<
325 container[2].first << "), " << container[2].second << std::endl;
326 }
327 if(container[3] != std::pair<interval_data<Unit>, int>(interval_data<Unit>(15, 25), -1)) {
328 std::cout << "Test two nonoverlapping rectangles, fourth output wrong: Interval(" <<
329 container[3].first << "), " << container[3].second << std::endl;
330 }
331 return true;
332 }
333 }
334
test_assign()335 void test_assign() {
336 using namespace gtl;
337 std::vector<polygon_data<int> > ps;
338 polygon_90_set_data<int> ps90;
339 assign(ps, ps90);
340 }
341
342 //this is a compile time test, if it compiles it passes
test_view_as()343 void test_view_as() {
344 using namespace gtl;
345 polygon_data<int> p;
346 polygon_45_data<int> p45;
347 polygon_90_data<int> p90;
348 polygon_with_holes_data<int> pwh;
349 polygon_45_with_holes_data<int> p45wh;
350 polygon_90_with_holes_data<int> p90wh;
351 rectangle_data<int> rect(0, 1, 10, 11);
352 polygon_90_set_data<int> ps90;
353 polygon_45_set_data<int> ps45;
354 polygon_set_data<int> ps;
355
356 assign(p, rect);
357 assign(p90, view_as<polygon_90_concept>(p));
358 if(!equivalence(p90, rect))
359 std::cout << "fail 1\n";
360 assign(p45, view_as<polygon_45_concept>(p));
361 if(!equivalence(p45, rect))
362 std::cout << "fail 2\n";
363 assign(p90, view_as<polygon_90_concept>(p45));
364 if(!equivalence(p90, rect))
365 std::cout << "fail 3\n";
366 if(!equivalence(rect, view_as<rectangle_concept>(p)))
367 std::cout << "fail 4\n";
368 if(!equivalence(rect, view_as<rectangle_concept>(p45)))
369 std::cout << "fail 5\n";
370 if(!equivalence(rect, view_as<rectangle_concept>(p90)))
371 std::cout << "fail 6\n";
372 assign(pwh, rect);
373 assign(p90wh, rect);
374 assign(p45wh, rect);
375 if(!equivalence(rect, view_as<rectangle_concept>(pwh)))
376 std::cout << "fail 7\n";
377 if(!equivalence(rect, view_as<rectangle_concept>(p45wh)))
378 std::cout << "fail 8\n";
379 if(!equivalence(rect, view_as<rectangle_concept>(p90wh)))
380 std::cout << "fail 9\n";
381 assign(p90wh, view_as<polygon_90_with_holes_concept>(pwh));
382 if(!equivalence(p90wh, rect))
383 std::cout << "fail 10\n";
384 assign(p45wh, view_as<polygon_45_with_holes_concept>(pwh));
385 if(!equivalence(p45wh, rect))
386 std::cout << "fail 11\n";
387 assign(p90wh, view_as<polygon_90_with_holes_concept>(p45wh));
388 if(!equivalence(p90wh, rect))
389 std::cout << "fail 12\n";
390 assign(p90, view_as<polygon_90_concept>(pwh));
391 if(!equivalence(p90, rect))
392 std::cout << "fail 13\n";
393 assign(p45, view_as<polygon_45_concept>(pwh));
394 if(!equivalence(p45, rect))
395 std::cout << "fail 14\n";
396 assign(p90, view_as<polygon_90_concept>(p45wh));
397 if(!equivalence(p90, rect))
398 std::cout << "fail 15\n";
399 assign(ps, rect);
400 assign(ps90, view_as<polygon_90_set_concept>(ps));
401 if(!equivalence(ps90, rect))
402 std::cout << "fail 16\n";
403 assign(ps45, view_as<polygon_45_set_concept>(ps));
404 if(!equivalence(ps45, rect))
405 std::cout << "fail 17\n";
406 assign(ps90, view_as<polygon_90_set_concept>(ps45));
407 if(!equivalence(ps90, rect))
408 std::cout << "fail 18\n";
409 }
410
testPolygon45SetRect()411 inline bool testPolygon45SetRect() {
412 std::vector<point_data<int> > points;
413 points.push_back(point_data<int>(0,0));
414 points.push_back(point_data<int>(0,10));
415 points.push_back(point_data<int>(10,10));
416 points.push_back(point_data<int>(10,0));
417 polygon_45_data<int> poly;
418 poly.set(points.begin(), points.end());
419 polygon_45_set_data<int> ps;
420 ps.insert(poly);
421 std::vector<polygon_45_data<int> > polys;
422 ps.get_polygons(polys);
423 std::cout << polys.size() << std::endl;
424 for(unsigned int i = 0; i < polys.size(); ++i) {
425 std::cout << polys[i] << std::endl;
426 }
427 return true;
428 }
429
testPolygon45Set()430 inline bool testPolygon45Set() {
431 polygon_45_formation<int>::Polygon45Formation pf(true);
432 typedef boolean_op_45<int>::Vertex45 Vertex45;
433 std::vector<Vertex45> data;
434 // result == 0 8 -1 1
435 data.push_back(Vertex45(point_data<int>(0, 8), -1, 1));
436 // result == 0 8 1 -1
437 data.push_back(Vertex45(point_data<int>(0, 8), 1, -1));
438 // result == 4 0 1 1
439 data.push_back(Vertex45(point_data<int>(4, 0), 1, 1));
440 // result == 4 0 2 1
441 data.push_back(Vertex45(point_data<int>(4, 0), 2, 1));
442 // result == 4 4 2 -1
443 data.push_back(Vertex45(point_data<int>(4, 4), 2, -1));
444 // result == 4 4 -1 -1
445 data.push_back(Vertex45(point_data<int>(4, 4), -1, -1));
446 // result == 4 12 1 1
447 data.push_back(Vertex45(point_data<int>(4, 12), 1, 1));
448 // result == 4 12 2 1
449 data.push_back(Vertex45(point_data<int>(4, 12), 2, 1));
450 // result == 4 16 2 -1
451 data.push_back(Vertex45(point_data<int>(4, 16), 2, 1));
452 // result == 4 16 -1 -1
453 data.push_back(Vertex45(point_data<int>(4, 16), -1, -1));
454 // result == 6 2 1 -1
455 data.push_back(Vertex45(point_data<int>(6, 2), 1, -1));
456 // result == 6 14 -1 1
457 data.push_back(Vertex45(point_data<int>(6, 14), -1, 1));
458 // result == 6 2 -1 1
459 data.push_back(Vertex45(point_data<int>(6, 2), -1, 1));
460 // result == 6 14 1 -1
461 data.push_back(Vertex45(point_data<int>(6, 14), 1, -1));
462 // result == 8 0 -1 -1
463 data.push_back(Vertex45(point_data<int>(8, 0), -1, -1));
464 // result == 8 0 2 -1
465 data.push_back(Vertex45(point_data<int>(8, 0), 2, -1));
466 // result == 8 4 2 1
467 data.push_back(Vertex45(point_data<int>(8, 4), 2, 1));
468 // result == 8 4 1 1
469 data.push_back(Vertex45(point_data<int>(8, 4), 1, 1));
470 // result == 8 12 -1 -1
471 data.push_back(Vertex45(point_data<int>(8, 12), -1, -1));
472 // result == 8 12 2 -1
473 data.push_back(Vertex45(point_data<int>(8, 12), 2, -1));
474 // result == 8 16 2 1
475 data.push_back(Vertex45(point_data<int>(8, 16), 2, 1));
476 // result == 8 16 1 1
477 data.push_back(Vertex45(point_data<int>(8, 16), 1, 1));
478 // result == 12 8 1 -1
479 data.push_back(Vertex45(point_data<int>(12, 8), 1, -1));
480 // result == 12 8 -1 1
481 data.push_back(Vertex45(point_data<int>(12, 8), -1, 1));
482
483 data.push_back(Vertex45(point_data<int>(6, 4), 1, -1));
484 data.push_back(Vertex45(point_data<int>(6, 4), 2, -1));
485 data.push_back(Vertex45(point_data<int>(6, 12), -1, 1));
486 data.push_back(Vertex45(point_data<int>(6, 12), 2, 1));
487 data.push_back(Vertex45(point_data<int>(10, 8), -1, -1));
488 data.push_back(Vertex45(point_data<int>(10, 8), 1, 1));
489
490 std::sort(data.begin(), data.end());
491 std::vector<polygon_45_data<int> > polys;
492 pf.scan(polys, data.begin(), data.end());
493 polygon_45_set_data<int> ps;
494 std::cout << "inserting1\n";
495 //std::vector<point_data<int> > points;
496 //points.push_back(point_data<int>(0,0));
497 //points.push_back(point_data<int>(0,10));
498 //points.push_back(point_data<int>(10,10));
499 //points.push_back(point_data<int>(10,0));
500 //Polygon45 poly;
501 //poly.set(points.begin(), points.end());
502 //ps.insert(poly);
503 ps.insert(polys[0]);
504
505 polygon_45_set_data<int> ps2;
506 std::cout << "inserting2\n";
507 ps2.insert(polys[0]);
508 std::cout << "applying boolean\n";
509 ps |= ps2;
510 std::vector<polygon_45_data<int> > polys2;
511 std::cout << "getting result\n";
512 ps.get_polygons(polys2);
513 std::cout << ps2 << std::endl;
514 std::cout << ps << std::endl;
515 std::cout << polys[0] << std::endl;
516 std::cout << polys2[0] << std::endl;
517 if(polys != polys2) std::cout << "test Polygon45Set failed\n";
518 return polys == polys2;
519 }
520
testPolygon45SetPerterbation()521 inline bool testPolygon45SetPerterbation() {
522 polygon_45_formation<int>::Polygon45Formation pf(true);
523 typedef boolean_op_45<int>::Vertex45 Vertex45;
524 std::vector<Vertex45> data;
525 // result == 0 8 -1 1
526 data.push_back(Vertex45(point_data<int>(0, 80), -1, 1));
527 // result == 0 8 1 -1
528 data.push_back(Vertex45(point_data<int>(0, 80), 1, -1));
529 // result == 4 0 1 1
530 data.push_back(Vertex45(point_data<int>(40, 0), 1, 1));
531 // result == 4 0 2 1
532 data.push_back(Vertex45(point_data<int>(40, 0), 2, 1));
533 // result == 4 4 2 -1
534 data.push_back(Vertex45(point_data<int>(40, 40), 2, -1));
535 // result == 4 4 -1 -1
536 data.push_back(Vertex45(point_data<int>(40, 40), -1, -1));
537 // result == 4 12 1 1
538 data.push_back(Vertex45(point_data<int>(40, 120), 1, 1));
539 // result == 4 12 2 1
540 data.push_back(Vertex45(point_data<int>(40, 120), 2, 1));
541 // result == 4 16 2 -1
542 data.push_back(Vertex45(point_data<int>(40, 160), 2, 1));
543 // result == 4 16 -1 -1
544 data.push_back(Vertex45(point_data<int>(40, 160), -1, -1));
545 // result == 6 2 1 -1
546 data.push_back(Vertex45(point_data<int>(60, 20), 1, -1));
547 // result == 6 14 -1 1
548 data.push_back(Vertex45(point_data<int>(60, 140), -1, 1));
549 // result == 6 2 -1 1
550 data.push_back(Vertex45(point_data<int>(60, 20), -1, 1));
551 // result == 6 14 1 -1
552 data.push_back(Vertex45(point_data<int>(60, 140), 1, -1));
553 // result == 8 0 -1 -1
554 data.push_back(Vertex45(point_data<int>(80, 0), -1, -1));
555 // result == 8 0 2 -1
556 data.push_back(Vertex45(point_data<int>(80, 0), 2, -1));
557 // result == 8 4 2 1
558 data.push_back(Vertex45(point_data<int>(80, 40), 2, 1));
559 // result == 8 4 1 1
560 data.push_back(Vertex45(point_data<int>(80, 40), 1, 1));
561 // result == 8 12 -1 -1
562 data.push_back(Vertex45(point_data<int>(80, 120), -1, -1));
563 // result == 8 12 2 -1
564 data.push_back(Vertex45(point_data<int>(80, 120), 2, -1));
565 // result == 8 16 2 1
566 data.push_back(Vertex45(point_data<int>(80, 160), 2, 1));
567 // result == 8 16 1 1
568 data.push_back(Vertex45(point_data<int>(80, 160), 1, 1));
569 // result == 12 8 1 -1
570 data.push_back(Vertex45(point_data<int>(120, 80), 1, -1));
571 // result == 12 8 -1 1
572 data.push_back(Vertex45(point_data<int>(120, 80), -1, 1));
573
574 data.push_back(Vertex45(point_data<int>(60, 40), 1, -1));
575 data.push_back(Vertex45(point_data<int>(60, 40), 2, -1));
576 data.push_back(Vertex45(point_data<int>(60, 120), -1, 1));
577 data.push_back(Vertex45(point_data<int>(60, 120), 2, 1));
578 data.push_back(Vertex45(point_data<int>(100, 80), -1, -1));
579 data.push_back(Vertex45(point_data<int>(100, 80), 1, 1));
580
581 std::sort(data.begin(), data.end());
582 std::vector<polygon_45_data<int> > polys;
583 pf.scan(polys, data.begin(), data.end());
584 polygon_45_set_data<int> ps;
585 std::cout << "inserting1\n";
586 //std::vector<point_data<int> > points;
587 //points.push_back(point_data<int>(0,0));
588 //points.push_back(point_data<int>(0,10));
589 //points.push_back(point_data<int>(10,10));
590 //points.push_back(point_data<int>(10,0));
591 //Polygon45 poly;
592 //poly.set(points.begin(), points.end());
593 //ps.insert(poly);
594 polygon_45_set_data<int> preps(polys[0]);
595
596 ps.insert(polys[0]);
597 convolve(polys[0], point_data<int>(0, 1) );
598
599 polygon_45_set_data<int> ps2;
600 std::cout << "inserting2\n";
601 ps2.insert(polys[0]);
602 std::cout << "applying boolean\n";
603 ps |= ps2;
604 std::vector<polygon_45_data<int> > polys2;
605 std::cout << "getting result\n";
606 ps.get_polygons(polys2);
607 std::cout << preps << std::endl;
608 std::cout << ps2 << std::endl;
609 std::cout << ps << std::endl;
610 std::cout << polys[0] << std::endl;
611 std::cout << polys2[0] << std::endl;
612 if(polys != polys2) std::cout << "test Polygon45Set failed\n";
613 return polys == polys2;
614 //return true;
615 }
616
testPolygon45SetDORA()617 inline int testPolygon45SetDORA() {
618 std::cout << "testPolygon45SetDORA" << std::endl;
619 std::vector<point_data<int> > pts;
620 pts.push_back(point_data<int>(0, 0));
621 pts.push_back(point_data<int>(10, 0));
622 pts.push_back(point_data<int>(10, 10));
623 pts.push_back(point_data<int>(0, 10));
624 polygon_45_data<int> apoly;
625 apoly.set(pts.begin(), pts.end());
626 polygon_45_set_data<int> ps(apoly);
627 polygon_45_set_data<int> ps2(ps);
628 ps2 = apoly;
629 std::vector<polygon_45_data<int> > apolys;
630 apolys.push_back(apoly);
631 ps2.insert(apolys.begin(), apolys.end());
632 apolys.clear();
633 ps2.get(apolys);
634 std::cout << apolys.size() << std::endl;
635 std::cout << (ps == ps2) << std::endl;
636 std::cout << !(ps != ps2) << std::endl;
637 ps2.clear();
638 std::cout << (ps2.value().empty()) << std::endl;
639 ps2.set(apolys.begin(), apolys.end());
640 ps2.set(ps.value());
641 ps.clean();
642 ps2.set_clean(ps.value());
643 ps2.insert(ps.value().begin(), ps.value().end());
644 ps2.clear();
645 for(polygon_45_set_data<int>::iterator_type itr = ps.begin();
646 itr != ps.end(); ++itr) {
647 ps2.insert(*itr);
648 }
649 std::vector<polygon_45_with_holes_data<int> > apolywhs;
650 ps2.get_polygons_with_holes(apolywhs);
651 std::cout << apolywhs.size() << std::endl;
652 ps2 += 1;
653 apolywhs.clear();
654 ps2.get_polygons_with_holes(apolywhs);
655 if(apolywhs.size()) std::cout << apolywhs[0] << std::endl;
656 ps2 -= 1;
657 apolywhs.clear();
658 ps2.get_polygons_with_holes(apolywhs);
659 if(apolywhs.size()) std::cout << apolywhs[0] << std::endl;
660 else {
661 std::cout << "test failed\n";
662 return 1;
663 }
664 rectangle_data<int> rect;
665 extents(rect, apolywhs[0]);
666 ps2.clear();
667 ps2.insert(rect);
668 ps2.extents(rect);
669 ps2.clear();
670 ps2.insert(rect);
671 ps2.clear();
672 ps2.insert(apolywhs[0]);
673 apolywhs.clear();
674 ps2.get_trapezoids(apolywhs);
675 if(apolywhs.size()) std::cout << apolywhs[0] << std::endl;
676 else {
677 std::cout << "test failed\n";
678 return 1;
679 }
680 ps2 *= ps;
681 std::cout << (ps2 == ps) << std::endl;
682 ps2 ^= ps;
683 std::cout << ps2.empty() << std::endl;
684 axis_transformation atr(axis_transformation::WEST_SOUTH);
685 ps2 = ps;
686 ps.transform(atr);
687 transformation<int> tr(atr);
688 tr.invert();
689 ps.transform(tr);
690 ps.scale_up(2);
691 ps.scale_down(2);
692 std::cout << (ps2 == ps) << std::endl;
693 pts.clear();
694 pts.push_back(point_data<int>(0,0));
695 pts.push_back(point_data<int>(10,10));
696 pts.push_back(point_data<int>(10,11));
697 pts.push_back(point_data<int>(0,21));
698 apoly.set(pts.begin(), pts.end());
699 ps2.clear();
700 ps2.insert(apoly);
701 ps2 -= 1;
702 apolywhs.clear();
703 ps2.get_polygons_with_holes(apolywhs);
704 if(apolywhs.size()) std::cout << apolywhs[0] << std::endl;
705 else {
706 std::cout << "test failed\n";
707 return 1;
708 }
709 pts.clear();
710 pts.push_back(point_data<int>(0, 0));
711 pts.push_back(point_data<int>(10, 10));
712 pts.push_back(point_data<int>(0, 20));
713 apoly.set(pts.begin(), pts.end());
714 ps2.clear();
715 ps2.insert(apoly);
716 pts.clear();
717 pts.push_back(point_data<int>(0, 5));
718 pts.push_back(point_data<int>(10, 15));
719 pts.push_back(point_data<int>(0, 25));
720 apoly.set(pts.begin(), pts.end());
721 ps2.insert(apoly);
722 apolywhs.clear();
723 ps2.get_polygons_with_holes(apolywhs);
724 if(apolywhs.size()) std::cout << apolywhs[0] << std::endl;
725 else {
726 std::cout << "test failed\n";
727 return 1;
728 }
729 return 0;
730
731 }
732 }
733 }
734 using namespace gtl;
735
testRectangle()736 bool testRectangle() {
737 rectangle_data<int> rect, rect2;
738 #ifdef BOOST_POLYGON_MSVC
739 horizontal(rect, interval_data<int>(0, 10));
740 vertical(rect, interval_data<int>(20, 30));
741 #else
742 horizontal(rect, interval_data<polygon_long_long_type>(0, 10));
743 vertical(rect, interval_data<polygon_long_long_type>(20, 30));
744 #endif
745 xl(rect2, 0);
746 xh(rect2, 10);
747 yl(rect2, 20);
748 yh(rect2, 30);
749 if(euclidean_distance(rect, rect2) != 0) return false;
750 if(euclidean_distance(rect2, rect) != 0) return false;
751 #ifdef BOOST_POLYGON_MSVC
752 set(rect, HORIZONTAL, interval_data<int>(0, 10));
753 if(!equivalence(horizontal(rect), interval_data<int>(0, 10))) return false;
754 if(!equivalence(vertical(rect2), interval_data<int>(20, 30))) return false;
755 #else
756 set(rect, HORIZONTAL, interval_data<polygon_long_long_type>(0, 10));
757 if(!equivalence(horizontal(rect), interval_data<polygon_long_long_type>(0, 10))) return false;
758 if(!equivalence(vertical(rect2), interval_data<polygon_long_long_type>(20, 30))) return false;
759 #endif
760 if(xl(rect) != 0) return false;
761 if(xh(rect) != 10) return false;
762 if(yl(rect) != 20) return false;
763 if(yh(rect) != 30) return false;
764 move(rect, HORIZONTAL, 10);
765 if(xl(rect) != 10) return false;
766 #ifdef BOOST_POLYGON_MSVC
767 set_points(rect, point_data<int>(0, 20), point_data<int>(10, 30));
768 #else
769 set_points(rect, point_data<int>(0, 20), point_data<polygon_long_long_type>(10, 30));
770 #endif
771 if(xl(rect) != 0) return false;
772 convolve(rect, rect2);
773 if(xh(rect) != 20) return false;
774 deconvolve(rect, rect2);
775 if(xh(rect) != 10) return false;
776 reflected_convolve(rect, rect2);
777 reflected_deconvolve(rect, rect2);
778 if(!equivalence(rect, rect2)) return false;
779 #ifdef BOOST_POLYGON_MSVC
780 convolve(rect, point_data<int>(100, 200));
781 #else
782 convolve(rect, point_data<polygon_long_long_type>(100, 200));
783 #endif
784 if(xh(rect) != 110) return false;
785 deconvolve(rect, point_data<int>(100, 200));
786 if(!equivalence(rect, rect2)) return false;
787 xh(rect, 100);
788 if(delta(rect, HORIZONTAL) != 100) return false;
789 if(area(rect) != 1000) return false;
790 if(half_perimeter(rect) != 110) return false;
791 if(perimeter(rect) != 220) return false;
792 if(guess_orientation(rect) != HORIZONTAL) return false;
793 return true;
794 }
795
796
testPolygon()797 bool testPolygon() {
798 int rect[4] = {0, 10, 20, 30};
799 iterator_compact_to_points<int*, point_data<int> > itr(rect, rect+4);
800 iterator_compact_to_points<int*, point_data<int> > itr_end(rect, rect+4);
801 std::vector<point_data<int> > points;
802 points.insert(points.end(), itr, itr_end);
803 polygon_90_data<int> p90;
804 assign(p90, rectangle_data<int>(interval_data<int>(0, 10), interval_data<int>(20, 30)));
805 if(winding(p90) != COUNTERCLOCKWISE) return false;
806 polygon_45_data<int> p45;
807 assign(p45, rectangle_data<int>(interval_data<int>(0, 10), interval_data<int>(20, 30)));
808 if(winding(p45) != COUNTERCLOCKWISE) return false;
809 polygon_data<int> p;
810 assign(p, rectangle_data<int>(interval_data<int>(0, 10), interval_data<int>(20, 30)));
811 if(winding(p) != COUNTERCLOCKWISE) return false;
812 set_compact(p90, rect, rect+4);
813 if(winding(p90) != COUNTERCLOCKWISE) return false;
814 points.clear();
815 points.push_back(point_data<int>(0, 0));
816 points.push_back(point_data<int>(10, 10));
817 points.push_back(point_data<int>(0, 20));
818 points.push_back(point_data<int>(-10, 10));
819 set_points(p45, points.begin(), points.end());
820 if(winding(p45) != COUNTERCLOCKWISE) return false;
821 std::swap(points[1], points[3]);
822 set_points(p, points.begin(), points.end());
823 if(winding(p) == COUNTERCLOCKWISE) return false;
824 point_data<int> cp;
825 center(cp, p);
826 if(cp != point_data<int>(0, 10)) return false;
827 move(p, HORIZONTAL, 3);
828 rectangle_data<int> bounding_box;
829 extents(bounding_box, p);
830 if(bounding_box != rectangle_data<int>(interval_data<int>(-7, 13), interval_data<int>(0, 20))) return false;
831 if(area(p90) != 400) return false;
832 if(area(p45) != 200) return false;
833 if(perimeter(p90) != 80) return false;
834 return true;
835 }
836
testPolygonAssign()837 bool testPolygonAssign() {
838 polygon_data<int> p;
839 polygon_data<int> p1;
840 polygon_45_data<int> p_45;
841 polygon_45_data<int> p_451;
842 polygon_90_data<int> p_90;
843 polygon_90_data<int> p_901;
844 polygon_with_holes_data<int> p_wh;
845 polygon_with_holes_data<int> p_wh1;
846 polygon_45_with_holes_data<int> p_45_wh;
847 polygon_45_with_holes_data<int> p_45_wh1;
848 polygon_90_with_holes_data<int> p_90_wh;
849 polygon_90_with_holes_data<int> p_90_wh1;
850 assign(p, p1);
851 assign(p, p_45);
852 assign(p, p_90);
853 //assign(p, p_wh);
854 //assign(p, p_45_wh);
855 //assign(p, p_90_wh);
856 //assign(p_45, p);
857 assign(p_451, p_45);
858 assign(p_45, p_90);
859 //assign(p_45, p_wh);
860 //assign(p_45, p_45_wh);
861 //assign(p_45, p_90_wh);
862 //assign(p_90, p);
863 //assign(p_90, p_45);
864 assign(p_901, p_90);
865 //assign(p_90, p_wh);
866 //assign(p_90, p_45_wh);
867 //assign(p_90, p_90_wh);
868 assign(p_wh, p);
869 assign(p_wh, p_45);
870 assign(p_wh, p_90);
871 assign(p_wh1, p_wh);
872 assign(p_wh, p_45_wh);
873 assign(p_wh, p_90_wh);
874 //assign(p_45_wh, p);
875 assign(p_45_wh, p_45);
876 assign(p_45_wh, p_90);
877 //assign(p_45_wh, p_wh);
878 assign(p_45_wh1, p_45_wh);
879 //assign(p_90_wh, p);
880 //assign(p_90_wh, p_45);
881 assign(p_90_wh, p_90);
882 assign(p_90_wh1, p_90_wh);
883 return true;
884 }
885
testPropertyMerge()886 int testPropertyMerge() {
887 rectangle_data<int> rect1 = construct<rectangle_data<int> >(0, 1, 10, 11);
888 rectangle_data<int> rect2 = construct<rectangle_data<int> >(5, 6, 17, 18);
889 property_merge_90<int, int> pm;
890 pm.insert(rect1, 0);
891 pm.insert(rect2, 1);
892 std::map<std::set<int>, polygon_90_set_data<int> > result;
893 pm.merge(result);
894 std::vector<rectangle_data<int> > rects;
895 std::set<int> key;
896 key.insert(0);
897 result[key].get(rects);
898 std::cout << rects.size() << std::endl;
899 std::vector<polygon_data<int> > polys;
900 result[key].get(polys);
901 std::cout << polys.size() << std::endl;
902 std::vector<polygon_90_with_holes_data<int> > polywhs;
903 result[key].get(polywhs);
904 std::cout << polys.size() << std::endl;
905 return result.size();
906 }
907
testPolygonWithHoles()908 bool testPolygonWithHoles() {
909 int rect[4] = {0, 10, 20, 30};
910 iterator_compact_to_points<int*, point_data<int> > itr(rect, rect+4);
911 iterator_compact_to_points<int*, point_data<int> > itr_end(rect, rect+4);
912 std::vector<point_data<int> > points;
913 points.insert(points.end(), itr, itr_end);
914 polygon_45_with_holes_data<int> p45wh;
915 assign(p45wh, rectangle_data<int>(interval_data<int>(0, 10), interval_data<int>(20, 30)));
916 if(winding(p45wh) != COUNTERCLOCKWISE) return false;
917 polygon_45_with_holes_data<int> p45;
918 assign(p45, rectangle_data<int>(interval_data<int>(0, 10), interval_data<int>(20, 30)));
919 if(winding(p45) != COUNTERCLOCKWISE) return false;
920 polygon_45_with_holes_data<int> p;
921 assign(p, rectangle_data<int>(interval_data<int>(0, 10), interval_data<int>(20, 30)));
922 if(winding(p) != COUNTERCLOCKWISE) return false;
923 set_compact(p45wh, rect, rect+4);
924 if(winding(p45wh) != COUNTERCLOCKWISE) return false;
925 points.clear();
926 points.push_back(point_data<int>(0, 0));
927 points.push_back(point_data<int>(10, 10));
928 points.push_back(point_data<int>(0, 20));
929 points.push_back(point_data<int>(-10, 10));
930 set_points(p45, points.begin(), points.end());
931 if(winding(p45) != COUNTERCLOCKWISE) return false;
932 std::swap(points[1], points[3]);
933 set_points(p, points.begin(), points.end());
934 if(winding(p) == COUNTERCLOCKWISE) return false;
935 point_data<int> cp;
936 center(cp, p);
937 if(cp != point_data<int>(0, 10)) return false;
938 move(p, HORIZONTAL, 3);
939 rectangle_data<int> bounding_box;
940 extents(bounding_box, p);
941 if(bounding_box != rectangle_data<int>(interval_data<int>(-7, 13), interval_data<int>(0, 20))) return false;
942 if(area(p45wh) != 400) return false;
943 if(area(p45) != 200) return false;
944 if(perimeter(p45wh) != 80) return false;
945 return true;
946 }
947
948 using namespace gtl;
949
950 typedef int Unit;
951 typedef point_data<int> Point;
952 typedef interval_data<int> Interval;
953 typedef rectangle_data<int> Rectangle;
954 typedef polygon_90_data<int> Polygon;
955 typedef polygon_90_with_holes_data<int> PolygonWithHoles;
956 typedef polygon_45_data<int> Polygon45;
957 typedef polygon_45_with_holes_data<int> Polygon45WithHoles;
958 typedef polygon_90_set_data<int> PolygonSet;
959 typedef polygon_45_set_data<int> Polygon45Set;
960 typedef axis_transformation AxisTransform;
961 typedef transformation<int> Transform;
962
getRandomBool()963 bool getRandomBool() {
964 return rand()%2 != 0;
965 }
getRandomInt()966 int getRandomInt() {
967 return rand()%6-2;
968 }
getRandomPoint()969 Point getRandomPoint() {
970 int x = rand()%8;
971 int y = rand()%8;
972 return Point(x, y);
973 }
getRandomTriangle()974 Polygon45 getRandomTriangle() {
975 Point pts[3];
976 pts[0] = getRandomPoint();
977 pts[1] = pts[2] = pts[0];
978 int disp = getRandomInt();
979 bool dir = getRandomBool();
980 x(pts[2], x(pts[2]) + disp);
981 x(pts[1], x(pts[1]) + disp);
982 if(dir)
983 y(pts[1], y(pts[1]) + disp);
984 else
985 y(pts[1], y(pts[1]) - disp);
986 return Polygon45(pts, pts+3);
987 }
988
nonInteger45StessTest()989 bool nonInteger45StessTest() {
990 for(unsigned int tests = 0; tests < 10; ++tests) {
991 Polygon45Set ps1, ps2;
992 std::vector<Polygon45> p45s;
993 for(unsigned int i = 0; i < 10; ++i) {
994 Polygon45 p45 = getRandomTriangle();
995 p45s.push_back(p45);
996 ps1.insert(p45);
997 scale_up(p45, 2);
998 ps2.insert(p45);
999 }
1000 std::vector<Polygon45> polys;
1001 ps1.get(polys);
1002 Polygon45Set ps3;
1003 for(unsigned int i = 0; i < polys.size(); ++i) {
1004 scale_up(polys[i], 2);
1005 ps3.insert(polys[i]);
1006 }
1007 Polygon45Set ps4 = ps3 ^ ps2;
1008 std::vector<Polygon45> polys_error;
1009 ps4.get(polys_error);
1010 for(unsigned int i = 0; i < polys_error.size(); ++i) {
1011 //if(polys_error[i].size() > 3) return false;
1012 if(area(polys_error[i]) != 1) {
1013 if(area(polys_error[i]) == 2) {
1014 //if two area 1 errors merge it will have area 2
1015 continue;
1016 }
1017 std::cout << "test failed\n";
1018 for(unsigned int j =0; j < p45s.size(); ++j) {
1019 std::cout << p45s[j] << std::endl;
1020 }
1021 return false;
1022 }
1023 }
1024 }
1025 return true;
1026 }
1027
validate_polygon_set_op(Polygon45Set & ps45_o,const Polygon45Set & ps45_1,const Polygon45Set & ps45_2,int op_type)1028 bool validate_polygon_set_op(Polygon45Set& ps45_o,
1029 const Polygon45Set& ps45_1,
1030 const Polygon45Set& ps45_2,
1031 int op_type) {
1032 Polygon45Set s_ps_45_o(ps45_o);
1033 Polygon45Set s_ps_45_1(ps45_1);
1034 Polygon45Set s_ps_45_2(ps45_2);
1035 s_ps_45_o.scale_up(2);
1036 s_ps_45_1.scale_up(2);
1037 s_ps_45_2.scale_up(2);
1038 Polygon45Set s_ps_45_validate;
1039 if(op_type == 0) {
1040 s_ps_45_validate = s_ps_45_1 + s_ps_45_2;
1041 s_ps_45_validate += Rectangle(4, 4, 6, 6);
1042 } else if(op_type == 1) {
1043 s_ps_45_validate = s_ps_45_1 * s_ps_45_2;
1044 s_ps_45_validate -= Rectangle(4, 4, 6, 6);
1045 } else if(op_type == 2) {
1046 s_ps_45_validate = s_ps_45_1 ^ s_ps_45_2;
1047 s_ps_45_validate -= Rectangle(4, 4, 6, 6);
1048 } else {
1049 s_ps_45_validate = s_ps_45_1 - s_ps_45_2;
1050 s_ps_45_validate -= Rectangle(4, 4, 6, 6);
1051 }
1052 if(s_ps_45_validate != s_ps_45_o) {
1053 std::cout << "TEST FAILED\n";
1054 std::vector<Polygon45> polys;
1055 s_ps_45_o.get(polys);
1056 std::cout << "Result:\n";
1057 for(unsigned int i = 0; i < polys.size(); ++i) {
1058 std::cout << polys[i] << std::endl;
1059 }
1060 polys.clear();
1061 s_ps_45_validate.get(polys);
1062 std::cout << "Expected Result:\n";
1063 for(unsigned int i = 0; i < polys.size(); ++i) {
1064 std::cout << polys[i] << std::endl;
1065 }
1066 //redo the operation, set breakpoints here
1067 switch (op_type) {
1068 case 0:
1069 ps45_o = ps45_1 + ps45_2;
1070 ps45_o.get(polys);//needed to force clean
1071 break;
1072 case 1:
1073 ps45_o = ps45_1 * ps45_2;
1074 break;
1075 case 2:
1076 ps45_o = ps45_1 ^ ps45_2;
1077 break;
1078 default:
1079 ps45_o = ps45_1 - ps45_2;
1080 };
1081 //redo the check, set breakpoints here
1082 if(op_type == 0) {
1083 s_ps_45_validate = s_ps_45_1 + s_ps_45_2;
1084 s_ps_45_validate += Rectangle(4, 4, 6, 6);
1085 s_ps_45_validate.get(polys);
1086 } else if(op_type == 1) {
1087 s_ps_45_validate = s_ps_45_1 * s_ps_45_2;
1088 s_ps_45_validate -= Rectangle(4, 4, 6, 6);
1089 } else if(op_type == 2) {
1090 s_ps_45_validate = s_ps_45_1 ^ s_ps_45_2;
1091 s_ps_45_validate -= Rectangle(4, 4, 6, 6);
1092 } else {
1093 s_ps_45_validate = s_ps_45_1 - s_ps_45_2;
1094 s_ps_45_validate -= Rectangle(4, 4, 6, 6);
1095 }
1096 return false;
1097 }
1098 return true;
1099 }
1100
test_two_polygon_sets(const Polygon45Set & ps45_1,const Polygon45Set & ps45_2)1101 bool test_two_polygon_sets(const Polygon45Set& ps45_1,
1102 const Polygon45Set& ps45_2) {
1103 std::cout << "test two polygon sets \n";
1104 std::vector<Polygon45> polys;
1105 ps45_1.get(polys);
1106 std::cout << "LVALUE:\n";
1107 for(unsigned int i = 0; i < polys.size(); ++i) {
1108 std::cout << polys[i] << std::endl;
1109 }
1110 polys.clear();
1111 ps45_2.get(polys);
1112 std::cout << "RVALUE:\n";
1113 for(unsigned int i = 0; i < polys.size(); ++i) {
1114 std::cout << polys[i] << std::endl;
1115 }
1116 Polygon45Set ps45_o;
1117 std::cout << "OR\n";
1118 ps45_o = ps45_1 + ps45_2;
1119 polys.clear();
1120 ps45_o.get(polys);
1121 for(unsigned int i = 0; i < polys.size(); ++i) {
1122 std::cout << polys[i] << std::endl;
1123 }
1124 if(!validate_polygon_set_op(ps45_o, ps45_1, ps45_2, 0)) return false;
1125 std::cout << "AND\n";
1126 ps45_o = ps45_1 * ps45_2;
1127 polys.clear();
1128 ps45_o.get(polys);
1129 for(unsigned int i = 0; i < polys.size(); ++i) {
1130 std::cout << polys[i] << std::endl;
1131 }
1132 if(!validate_polygon_set_op(ps45_o, ps45_1, ps45_2, 1)) return false;
1133 std::cout << "XOR\n";
1134 ps45_o = ps45_1 ^ ps45_2;
1135 polys.clear();
1136 ps45_o.get(polys);
1137 for(unsigned int i = 0; i < polys.size(); ++i) {
1138 std::cout << polys[i] << std::endl;
1139 }
1140 if(!validate_polygon_set_op(ps45_o, ps45_1, ps45_2, 2)) return false;
1141 std::cout << "SUBTRACT\n";
1142 ps45_o = ps45_1 - ps45_2;
1143 polys.clear();
1144 ps45_o.get(polys);
1145 for(unsigned int i = 0; i < polys.size(); ++i) {
1146 std::cout << polys[i] << std::endl;
1147 }
1148 if(!validate_polygon_set_op(ps45_o, ps45_1, ps45_2, 3)) return false;
1149 return true;
1150 }
1151
test_two_polygons(const Polygon45 & p45_1,const Polygon45 & p45_2)1152 bool test_two_polygons(const Polygon45& p45_1,
1153 const Polygon45& p45_2) {
1154 Polygon45Set ps45_1, ps45_2;
1155 ps45_1.insert(p45_1);
1156 ps45_2.insert(p45_2);
1157 ps45_1.insert(rectangle_data<int>(10, -100, 20, 100));
1158 ps45_2.insert(rectangle_data<int>(0, 10, 100, 20));
1159 if(!test_two_polygon_sets(ps45_1, ps45_2)) return false;
1160 Polygon45Set ps45_1_c = ps45_1 - Rectangle(0, 0, 2, 5);
1161 Polygon45Set ps45_2_c = ps45_2 - Rectangle(0, 0, 2, 5);
1162 if(!test_two_polygon_sets(ps45_1_c, ps45_2_c)) return false;
1163 if(!test_two_polygon_sets(ps45_1_c, ps45_2)) return false;
1164 if(!test_two_polygon_sets(ps45_1, ps45_2_c)) return false;
1165 return true;
1166 }
1167
test_45_touch()1168 bool test_45_touch() {
1169 using namespace gtl;
1170 connectivity_extraction_45<int> ce;
1171 rectangle_data<int> rect1(0, 0, 10, 10);
1172 rectangle_data<int> rect2(5, 5, 15, 15);
1173 rectangle_data<int> rect3(5, 20, 15, 25);
1174 ce.insert(rect1);
1175 ce.insert(rect2);
1176 ce.insert(rect3);
1177 std::vector<std::set<int> > graph(3);
1178 ce.extract(graph);
1179 if(graph[0].size() == 1 && graph[1].size() == 1 && graph[2].size() == 0) {
1180 std::set<int>::iterator itr = graph[0].begin();
1181 std::cout << *itr << std::endl;
1182 std::set<int>::iterator itr1 = graph[1].begin();
1183 std::cout << *itr1 << std::endl;
1184 return true;
1185 }
1186 std::cout << "test failed\n";
1187 return false;
1188 }
1189
test_45_touch_ur()1190 bool test_45_touch_ur() {
1191 using namespace gtl;
1192 connectivity_extraction_45<int> ce;
1193 rectangle_data<int> rect1(0, 0, 5, 5);
1194 rectangle_data<int> rect2(5, 5, 10, 10);
1195 ce.insert(rect1);
1196 ce.insert(rect2);
1197 std::vector<std::set<int> > graph(2);
1198 ce.extract(graph);
1199 if(graph[0].size() == 1 && graph[1].size() == 1) {
1200 std::set<int>::iterator itr = graph[0].begin();
1201 std::cout << *itr << std::endl;
1202 std::set<int>::iterator itr1 = graph[1].begin();
1203 std::cout << *itr1 << std::endl;
1204 return true;
1205 }
1206 std::cout << "test failed\n";
1207 return false;
1208 }
1209
test_45_touch_r()1210 bool test_45_touch_r() {
1211 using namespace gtl;
1212 connectivity_extraction_45<int> ce;
1213 rectangle_data<int> rect1(0, 0, 5, 5);
1214 rectangle_data<int> rect2(5, 0, 10, 5);
1215 ce.insert(rect1);
1216 ce.insert(rect2);
1217 std::vector<std::set<int> > graph(2);
1218 ce.extract(graph);
1219 if(graph[0].size() == 1 && graph[1].size() == 1) {
1220 std::set<int>::iterator itr = graph[0].begin();
1221 std::cout << *itr << std::endl;
1222 std::set<int>::iterator itr1 = graph[1].begin();
1223 std::cout << *itr1 << std::endl;
1224 return true;
1225 }
1226 std::cout << "test failed\n";
1227 return false;
1228 }
1229
test_45_touch_boundaries()1230 bool test_45_touch_boundaries() {
1231 using namespace gtl;
1232 connectivity_extraction_45<int> ce;
1233 rectangle_data<int> rect1(0, 0, 10, 10);
1234 rectangle_data<int> rect2(10, 0, 20, 10);
1235 rectangle_data<int> rect3(20, 0, 30, 10);
1236 rectangle_data<int> rect4(0, 10, 10, 20);
1237 rectangle_data<int> rect5(10, 10, 20, 20);
1238 rectangle_data<int> rect6(20, 10, 30, 20);
1239 rectangle_data<int> rect7(0, 20, 10, 30);
1240 rectangle_data<int> rect8(10, 20, 20, 30);
1241 rectangle_data<int> rect9(20, 20, 30, 30);
1242 ce.insert(rect1);
1243 ce.insert(rect2);
1244 ce.insert(rect3);
1245 ce.insert(rect4);
1246 ce.insert(rect5);
1247 ce.insert(rect6);
1248 ce.insert(rect7);
1249 ce.insert(rect8);
1250 ce.insert(rect9);
1251 std::vector<std::set<int> > graph(9);
1252 ce.extract(graph);
1253 for(unsigned int i = 0; i < 9; ++i) {
1254 std::cout << i << ": ";
1255 for(std::set<int>::iterator itr = graph[i].begin(); itr != graph[i].end(); ++itr) {
1256 std::cout << *itr << " ";
1257 } std::cout << std::endl;
1258 }
1259 if(graph[0].size() == 3 && graph[1].size() == 5 && graph[2].size() == 3 &&
1260 graph[3].size() == 5 && graph[4].size() == 8 && graph[5].size() == 5 &&
1261 graph[6].size() == 3 && graph[7].size() == 5 && graph[8].size() == 3) {
1262 return true;
1263 }
1264 std::cout << "test failed\n";
1265 return false;
1266 }
1267
test_45_concept_interact()1268 bool test_45_concept_interact() {
1269 using namespace gtl;
1270 std::vector<polygon_45_data<int> > polys;
1271 polys += rectangle_data<int>(10, 10, 20, 20);
1272 polys += rectangle_data<int>(15, 15, 25, 25);
1273 polys += rectangle_data<int>(5, 25, 10, 35);
1274 interact(polys, rectangle_data<int>(0, 0, 13, 13));
1275 if(polys.size() != 1) return false;
1276 return true;
1277 }
1278
test_aa_touch()1279 bool test_aa_touch() {
1280 using namespace gtl;
1281 connectivity_extraction<int> ce;
1282 rectangle_data<int> rect1(0, 0, 10, 10);
1283 rectangle_data<int> rect2(5, 5, 15, 15);
1284 rectangle_data<int> rect3(5, 20, 15, 25);
1285 ce.insert(rect1);
1286 ce.insert(rect2);
1287 ce.insert(rect3);
1288 std::vector<std::set<int> > graph(3);
1289 ce.extract(graph);
1290 if(graph[0].size() == 1 && graph[1].size() == 1 && graph[2].size() == 0) {
1291 std::set<int>::iterator itr = graph[0].begin();
1292 std::cout << *itr << std::endl;
1293 std::set<int>::iterator itr1 = graph[1].begin();
1294 std::cout << *itr1 << std::endl;
1295 return true;
1296 }
1297 std::cout << "test failed\n";
1298 return false;
1299 }
1300
test_aa_touch_ur()1301 bool test_aa_touch_ur() {
1302 using namespace gtl;
1303 connectivity_extraction<int> ce;
1304 rectangle_data<int> rect1(0, 0, 5, 5);
1305 rectangle_data<int> rect2(5, 5, 10, 10);
1306 ce.insert(rect1);
1307 ce.insert(rect2);
1308 std::vector<std::set<int> > graph(2);
1309 ce.extract(graph);
1310 if(graph[0].size() == 1 && graph[1].size() == 1) {
1311 std::set<int>::iterator itr = graph[0].begin();
1312 std::cout << *itr << std::endl;
1313 std::set<int>::iterator itr1 = graph[1].begin();
1314 std::cout << *itr1 << std::endl;
1315 return true;
1316 }
1317 std::cout << "test failed\n";
1318 return false;
1319 }
1320
test_aa_touch_ur2()1321 bool test_aa_touch_ur2() {
1322 using namespace gtl;
1323 connectivity_extraction<int> ce;
1324 rectangle_data<int> rect2(5, 5, 10, 10);
1325 point_data<int> pts[3] = {
1326 point_data<int>(0, 0),
1327 point_data<int>(5, 5),
1328 point_data<int>(0, 5)
1329 };
1330 polygon_data<int> poly;
1331 poly.set(pts, pts+3);
1332 ce.insert(poly);
1333 ce.insert(rect2);
1334 std::vector<std::set<int> > graph(2);
1335 ce.extract(graph);
1336 if(graph[0].size() == 1 && graph[1].size() == 1) {
1337 std::set<int>::iterator itr = graph[0].begin();
1338 std::cout << *itr << std::endl;
1339 std::set<int>::iterator itr1 = graph[1].begin();
1340 std::cout << *itr1 << std::endl;
1341 return true;
1342 }
1343 std::cout << "test failed\n";
1344 return false;
1345 }
1346
test_aa_touch_r()1347 bool test_aa_touch_r() {
1348 using namespace gtl;
1349 connectivity_extraction<int> ce;
1350 rectangle_data<int> rect1(0, 0, 5, 5);
1351 rectangle_data<int> rect2(5, 0, 10, 5);
1352 ce.insert(rect1);
1353 ce.insert(rect2);
1354 std::vector<std::set<int> > graph(2);
1355 ce.extract(graph);
1356 if(graph[0].size() == 1 && graph[1].size() == 1) {
1357 std::set<int>::iterator itr = graph[0].begin();
1358 std::cout << *itr << std::endl;
1359 std::set<int>::iterator itr1 = graph[1].begin();
1360 std::cout << *itr1 << std::endl;
1361 return true;
1362 }
1363 std::cout << "test failed\n";
1364 return false;
1365 }
1366
test_aa_touch_boundaries()1367 bool test_aa_touch_boundaries() {
1368 using namespace gtl;
1369 connectivity_extraction<int> ce;
1370 rectangle_data<int> rect1(0, 0, 10, 10);
1371 rectangle_data<int> rect2(10, 0, 20, 10);
1372 rectangle_data<int> rect3(20, 0, 30, 10);
1373 rectangle_data<int> rect4(0, 10, 10, 20);
1374 rectangle_data<int> rect5(10, 10, 20, 20);
1375 rectangle_data<int> rect6(20, 10, 30, 20);
1376 rectangle_data<int> rect7(0, 20, 10, 30);
1377 rectangle_data<int> rect8(10, 20, 20, 30);
1378 rectangle_data<int> rect9(20, 20, 30, 30);
1379 ce.insert(rect1);
1380 ce.insert(rect2);
1381 ce.insert(rect3);
1382 ce.insert(rect4);
1383 ce.insert(rect5);
1384 ce.insert(rect6);
1385 ce.insert(rect7);
1386 ce.insert(rect8);
1387 ce.insert(rect9);
1388 std::vector<std::set<int> > graph(9);
1389 ce.extract(graph);
1390 for(unsigned int i = 0; i < 9; ++i) {
1391 std::cout << i << ": ";
1392 for(std::set<int>::iterator itr = graph[i].begin(); itr != graph[i].end(); ++itr) {
1393 std::cout << *itr << " ";
1394 } std::cout << std::endl;
1395 }
1396 if(graph[0].size() == 3 && graph[1].size() == 5 && graph[2].size() == 3 &&
1397 graph[3].size() == 5 && graph[4].size() == 8 && graph[5].size() == 5 &&
1398 graph[6].size() == 3 && graph[7].size() == 5 && graph[8].size() == 3) {
1399 return true;
1400 }
1401 std::cout << "test failed\n";
1402 return false;
1403 }
1404
test_aa_concept_interact()1405 bool test_aa_concept_interact() {
1406 using namespace gtl;
1407 std::vector<polygon_data<int> > polys;
1408 polys += rectangle_data<int>(10, 10, 20, 20);
1409 polys += rectangle_data<int>(15, 15, 25, 25);
1410 polys += rectangle_data<int>(5, 25, 10, 35);
1411 interact(polys, rectangle_data<int>(0, 0, 13, 13));
1412 if(polys.size() != 1) return false;
1413 return true;
1414 }
1415
test_get_rectangles()1416 bool test_get_rectangles() {
1417 using namespace gtl;
1418 polygon_90_set_data<int> ps(VERTICAL);
1419 ps += rectangle_data<int>(0, 0, 10, 10);
1420 ps += rectangle_data<int>(5, 5, 15, 15);
1421 std::vector<polygon_90_data<int> > polys;
1422 ps.get_rectangles(polys, HORIZONTAL);
1423 for(unsigned int i = 0; i < polys.size(); ++i) {
1424 std::cout << polys[i] << std::endl;
1425 }
1426 if(polys.size() != 3) return false;
1427 std::vector<rectangle_data<int> > rects;
1428 ps.get_rectangles(rects, HORIZONTAL);
1429 for(unsigned int i = 0; i < rects.size(); ++i) {
1430 std::cout << rects[i] << std::endl;
1431 }
1432 if(rects.size() != 3) return false;
1433 if(!equivalence(rects[2], rectangle_data<int>(5,10,15,15))) return false;
1434
1435 get_rectangles(polys, rects, VERTICAL);
1436 get_rectangles(rects, polys, HORIZONTAL);
1437 return equivalence(rects, polys);
1438 }
1439
test_get_trapezoids()1440 bool test_get_trapezoids() {
1441 using namespace gtl;
1442 polygon_45_set_data<int> ps;
1443 ps += rectangle_data<int>(0, 0, 10, 10);
1444 ps += rectangle_data<int>(5, 5, 15, 15);
1445 std::vector<polygon_45_data<int> > polys;
1446 ps.get_trapezoids(polys, HORIZONTAL);
1447 for(unsigned int i = 0; i < polys.size(); ++i) {
1448 std::cout << polys[i] << std::endl;
1449 }
1450 if(polys.size() != 3) return false;
1451 std::vector<polygon_45_data<int> > rects;
1452 ps.get_trapezoids(rects, HORIZONTAL);
1453 for(unsigned int i = 0; i < rects.size(); ++i) {
1454 std::cout << rects[i] << std::endl;
1455 }
1456 if(rects.size() != 3) return false;
1457 if(!equivalence(rects[2], rectangle_data<int>(5,10,15,15))) return false;
1458 get_trapezoids(polys, rects, VERTICAL);
1459 get_trapezoids(rects, polys, HORIZONTAL);
1460 return equivalence(rects, polys);
1461 }
1462
test_SQRT1OVER2()1463 bool test_SQRT1OVER2() {
1464 Point pts[] = {
1465 Point(100, 100),
1466 Point(0, 100),
1467 Point(100, 200),
1468 Point(0, 300),
1469 Point(100, 400),
1470 Point(0, 500),
1471 Point(100, 500),
1472 Point(100, 600),
1473 Point(200, 500),
1474 Point(300, 600),
1475 Point(400, 500),
1476 Point(500, 600),
1477 Point(500, 500),
1478 Point(600, 500),
1479 Point(500, 400),
1480 Point(600, 300),
1481 Point(500, 200),
1482 Point(600, 100),
1483 Point(500, 100),
1484 Point(500, 0),
1485 Point(400, 100),
1486 Point(300, 0),
1487 Point(200, 100),
1488 Point(100, 0),
1489 Point(100, 100)
1490 };
1491 Polygon45 p45(pts, pts+25);
1492 std::cout << is_45(p45) << std::endl;
1493 std::cout << p45 << std::endl;
1494 Polygon45Set ps45;
1495 ps45 += p45;
1496 ps45.resize(10, SQRT1OVER2, ORTHOGONAL);
1497 std::vector<Polygon45> polys;
1498 ps45.get(polys);
1499 if(polys.size() != 1) return false;
1500 Point pts2[] = {
1501 Point(90, 90),
1502 Point(-10, 90),
1503 Point(-10, 100),
1504 Point(90, 200),
1505 Point(-10, 300),
1506 Point(90, 400),
1507 Point(-10, 500),
1508 Point(-10, 510),
1509 Point(90, 510),
1510 Point(90, 610),
1511 Point(100, 610),
1512 Point(200, 510),
1513 Point(300, 610),
1514 Point(400, 510),
1515 Point(500, 610),
1516 Point(510, 610),
1517 Point(510, 510),
1518 Point(610, 510),
1519 Point(610, 500),
1520 Point(510, 400),
1521 Point(610, 300),
1522 Point(510, 200),
1523 Point(610, 100),
1524 Point(610, 90),
1525 Point(510, 90),
1526 Point(510, -10),
1527 Point(500, -10),
1528 Point(400, 90),
1529 Point(300, -10),
1530 Point(200, 90),
1531 Point(100, -10),
1532 Point(90, -10),
1533 Point(90, 90)
1534 };
1535 Polygon45 p45reference(pts2, pts2+33);
1536 std::cout << is_45(polys[0]) << std::endl;
1537 std::cout << polys[0] << std::endl;
1538 std::cout << p45reference << std::endl;
1539 std::cout << is_45(p45reference) << std::endl;
1540 if(!equivalence(polys[0], p45reference)) {
1541 std::cout << "polys don't match\n";
1542 return false;
1543 }
1544 ps45.resize(-10, SQRT1OVER2, ORTHOGONAL);
1545 polys.clear();
1546 ps45.get(polys);
1547 if(polys.size() != 1) return false;
1548 std::cout << is_45(polys[0]) << std::endl;
1549 std::cout << polys[0] << std::endl;
1550 if(!equivalence(polys[0], p45)) {
1551 std::cout << "polys don't match\n";
1552 return false;
1553 }
1554 ps45.resize(11, SQRT1OVER2, UNFILLED);
1555 polys.clear();
1556 ps45.get(polys);
1557 if(polys.size() != 1) return false;
1558 std::cout << is_45(polys[0]) << std::endl;
1559 std::cout << polys[0] << std::endl;
1560 return true;
1561 }
1562
test_scaling_by_floating()1563 bool test_scaling_by_floating(){
1564 Point pts[] = {
1565 Point(1, 1),
1566 Point(10, 1),
1567 Point(1, 10)
1568 };
1569 Polygon45 poly(pts, pts+3);
1570 Polygon45Set ps45;
1571 ps45 += poly;
1572 ps45.scale(double(2.5));
1573 std::vector<Polygon45> polys;
1574 ps45.get(polys);
1575 for(unsigned int i = 0; i < polys.size(); ++i) {
1576 std::cout << polys[i] << std::endl;
1577 std::cout << area(polys[i]) << std::endl;
1578 }
1579 if(polys.size() != 1) return false;
1580 if(area(polys[0]) != 242) return false;
1581 scale(ps45, double(1)/double(2.5));
1582 polys.clear();
1583 ps45.get(polys);
1584 for(unsigned int i = 0; i < polys.size(); ++i) {
1585 std::cout << polys[i] << std::endl;
1586 }
1587 return equivalence(polys, poly);
1588 }
1589
test_directional_resize()1590 bool test_directional_resize() {
1591 std::vector<Rectangle> rects;
1592 rects.push_back(Rectangle(0, 0, 100, 100));
1593 resize(rects, -10, 10, -10, 10);
1594 for(unsigned int i = 0; i < rects.size(); ++i) {
1595 std::cout << rects[i] << std::endl;
1596 }
1597 if(rects.size() != 1) return false;
1598 if(rects[0] != Rectangle(10, 10, 110, 110)) return false;
1599
1600 return true;
1601 }
1602
test_self_xor()1603 bool test_self_xor() {
1604 std::vector<Rectangle> rects;
1605 rects.push_back(Rectangle(0, 0, 10, 10));
1606 rects.push_back(Rectangle(5, 5, 15, 15));
1607 self_xor(rects);
1608 for(unsigned int i = 0; i < rects.size(); ++i) {
1609 std::cout << rects[i] << std::endl;
1610 }
1611 if(rects.size() == 4) return true;
1612 else return false;
1613 }
1614
test_grow_and_45()1615 bool test_grow_and_45() {
1616 polygon_45_set_data<int> ps;
1617 ps.insert(Rectangle(0, 0, 5, 5));
1618 ps.insert(Rectangle(5, 5, 15, 15));
1619 grow_and(ps, 2);
1620 std::vector<polygon_45_data<int> > rects;
1621 ps.get_trapezoids(rects);
1622 for(unsigned int i = 0; i < rects.size(); ++i) {
1623 std::cout << rects[i] << std::endl;
1624 }
1625 if(rects.size() != 1) return false;
1626 return equivalence(rects, Rectangle(3, 3, 7, 7));
1627 }
1628
test_self_xor_45()1629 bool test_self_xor_45() {
1630 polygon_45_set_data<int> ps;
1631 ps.insert(Rectangle(0, 0, 10, 10));
1632 ps.insert(Rectangle(5, 5, 15, 15));
1633 self_xor(ps);
1634 std::vector<polygon_45_data<int> > rects;
1635 ps.get_trapezoids(rects);
1636 for(unsigned int i = 0; i < rects.size(); ++i) {
1637 std::cout << rects[i] << std::endl;
1638 }
1639 if(rects.size() == 4) return true;
1640 else return false;
1641 }
1642
testViewCopyConstruct()1643 bool testViewCopyConstruct() {
1644 PolygonSet ps1, ps2;
1645 ps1.insert(Rectangle(0, 0, 10, 10));
1646 ps2.insert(Rectangle(5, 5, 15, 15));
1647 PolygonSet psr = ps1 - ps2;
1648 std::vector<Rectangle> rects;
1649 rects += psr;
1650 for(unsigned int i = 0; i < rects.size(); ++i)
1651 std::cout << rects[i] << std::endl;
1652 if( rects.size() != 2) return false;
1653 Polygon45Set ps45_1, ps45_2;
1654 ps45_1.insert(Rectangle(0, 0, 10, 10));
1655 ps45_2.insert(Rectangle(5, 5, 15, 15));
1656 Polygon45Set ps45_r = ps45_1 - ps45_2;
1657 std::vector<Polygon45> polys;
1658 ps45_r.get_trapezoids(polys);
1659 for(unsigned int i = 0; i < polys.size(); ++i)
1660 std::cout << polys[i] << std::endl;
1661 if( polys.size() != 2) return false;
1662 return true;
1663 }
1664
testpip()1665 bool testpip() {
1666 std::vector<Point> pts;
1667 pts.push_back(Point(0, 0));
1668 pts.push_back(Point(10, 0));
1669 pts.push_back(Point(20, 10));
1670 pts.push_back(Point(0, 20));
1671 pts.push_back(Point(30, 40));
1672 pts.push_back(Point(-10, 50));
1673 pts.push_back(Point(-20, -20));
1674 pts.push_back(Point(0, 0));
1675 polygon_data<int> poly;
1676 polygon_with_holes_data<int> poly2;
1677 polygon_45_data<int> poly45;
1678 polygon_45_with_holes_data<int> poly245;
1679 polygon_90_data<int> poly90;
1680 polygon_90_with_holes_data<int> poly290;
1681 poly.set(pts.begin(), pts.end());
1682 poly2.set(pts.begin(), pts.end());
1683 assign(poly45, Rectangle(0, 0, 100, 100));
1684 assign(poly245, Rectangle(0, 0, 100, 100));
1685 assign(poly90, Rectangle(0, 0, 100, 100));
1686 assign(poly290, Rectangle(0, 0, 100, 100));
1687 for(unsigned int i = 0; i < pts.size(); ++i) {
1688 if(!contains(poly, pts[i], true)) return false;
1689 if(contains(poly, pts[i], false)) return false;
1690 if(!contains(poly2, pts[i], true)) return false;
1691 if(contains(poly2, pts[i], false)) return false;
1692 }
1693 if(!contains(poly45, pts[0], true)) return false;
1694 if(contains(poly245, pts[0], false)) return false;
1695 if(!contains(poly90, pts[0], true)) return false;
1696 if(contains(poly290, pts[0], false)) return false;
1697 Point pt(0, -10);
1698 if(contains(poly, pt)) return false;
1699 Point p2(0, 1);
1700 if(!contains(poly, p2)) return false;
1701 return true;
1702 }
1703
testHand()1704 void testHand() {
1705 using namespace gtl;
1706 int handcoords[] = {
1707 12375, 11050, 13175, 10200, 15825, 9275, 18750, 8525, 24150, 8300, 27575, 8400, 31775, 7800,
1708 35975, 7200, 41375, 4800, 42575, 4200, 43175, 4200, 47375, 2400, 49175, 1800, 51150, 2200,
1709 52275, 2825, 52625, 4150, 52375, 4975, 51575, 6000, 49275, 6850, 45700, 7950, 43175, 9600,
1710 39575, 10800, 37775, 12000, 37775, 12600, 37775, 13800, 38975, 14400, 41375, 14400, 45575, 13200,
1711 48600, 13000, 51575, 13200, 55175, 12600, 58775, 12600, 61175, 13200, 62375, 14400, 62550, 15700,
1712 61975, 16875, 60775, 17600, 60100, 17675, 58525, 17675, 56150, 17575, 52175, 18000, 47975, 18600,
1713 45575, 19200, 44375, 19200, 42675, 19325, 41600, 19775, 41600, 20500, 42100, 20825, 44975, 20400,
1714 48575, 20400, 52775, 21000, 53975, 21000, 57575, 21000, 62375, 21000, 65450, 22000, 66300, 23100,
1715 66100, 24550, 64750, 25925, 62975, 26400, 61175, 26400, 58775, 26400, 56025, 26050, 53450, 26025,
1716 50975, 26400, 48575, 26400, 46775, 26400, 43650, 26075, 41375, 26400, 40775, 27000, 40775, 27600,
1717 42225, 28650, 44375, 29400, 48575, 30000, 50975, 31200, 53975, 31800, 58775, 33000, 61200, 34300,
1718 62375, 35400, 62375, 37200, 61175, 38400, 60000, 38700, 57575, 38400, 54550, 37575, 50975, 36600,
1719 49075, 36125, 47750, 36125, 45700, 35425, 42350, 34350, 38900, 33775, 30575, 33000, 26975, 33600,
1720 25975, 34900, 26375, 36600, 28175, 38400, 30575, 40800, 32375, 43800, 33200, 46200, 33200, 48000,
1721 32650, 49300, 31425, 50000, 29950, 50125, 28825, 49375, 27575, 48000, 25825, 46000, 23975, 44100,
1722 22175, 42600, 19775, 39600, 17325, 37300, 14975, 34800, 13175, 31800, 10775, 29400, 9600, 27400,
1723 10175, 27000, 11375, 27600, 12575, 28800, 14375, 31800, 16175, 34800, 18575, 37200, 21575, 39000,
1724 22775, 40200, 23975, 41400, 24575, 42600, 26375, 44400, 28325, 46000, 29850, 46775, 31175, 46200,
1725 31550, 44575, 30575, 43200, 28775, 40800, 25775, 38400, 24575, 34800, 24750, 33175, 26975, 31800,
1726 29975, 31800, 33575, 31800, 37775, 32400, 39575, 33000, 41975, 33600, 45150, 34175, 46975, 34750,
1727 48575, 35400, 50975, 35400, 51575, 34800, 51875, 33725, 50775, 32575, 48575, 31800, 45750, 30875,
1728 43775, 30600, 41375, 29400, 38975, 28800, 35975, 28200, 34775, 27600, 34175, 27000, 34775, 25800,
1729 37175, 25200, 40175, 25200, 43175, 25200, 46775, 25200, 50975, 25425, 53375, 25200, 55175, 24600,
1730 55525, 23450, 53975, 22200, 52775, 22200, 49075, 21850, 45950, 21925, 40775, 21600, 37775, 21600,
1731 35150, 21350, 34325, 20950, 34175, 19800, 35975, 19200, 38375, 19200, 40750, 18900, 42575, 18600,
1732 44375, 18000, 47975, 17400, 50375, 17125, 52025, 16625, 52775, 15600, 52100, 14625, 49675, 14125,
1733 48625, 14125, 46775, 14400, 44375, 15000, 41375, 15150, 37700, 15275, 34775, 15600, 32850, 15925,
1734 31775, 15600, 31425, 14875, 32375, 13800, 36575, 11400, 38975, 10200, 41375, 9000, 43075, 8150,
1735 43650, 7200, 43325, 6250, 42225, 5825, 40800, 6275, 38900, 6925, 35375, 8400, 32375, 10200,
1736 27575, 11400, 22775, 12600, 19775, 13225, 16775, 13800, 14975, 14400, 13050, 14000, 11975, 12600,
1737 0, 0 };
1738 std::vector<Point> handpoints;
1739 for(unsigned int i = 0; i < 100000; i += 2) {
1740 Point pt(handcoords[i], handcoords[i+1]);
1741 if(pt == Point(0, 0)) break;
1742 handpoints.push_back(pt);
1743 }
1744 polygon_data<int> handpoly;
1745 handpoly.set(handpoints.begin(), handpoints.end());
1746 int spiralcoords [] = {
1747 37200, 3600, 42075, 4025, 47475, 5875, 51000, 7800, 55800, 12300, 59000, 17075, 60000, 20400,
1748 61200, 25800, 61200, 29400, 60600, 33600, 58800, 38400, 55800, 42600, 53200, 45625,
1749 49200, 48600, 43200, 51000, 35400, 51600, 29400, 50400, 23400, 47400, 19200, 43800,
1750 16200, 39600, 14400, 35400, 13200, 29400, 13200, 24000, 15000, 18600, 17400, 13800,
1751 20525, 10300, 24600, 7200, 29400, 4800, 32450, 4000, 34825, 3675, 35625, 3625,
1752 35825, 7275, 39600, 7200, 43800, 8400, 46800, 9600, 50400, 12000, 53400, 15000,
1753 55800, 18600, 57000, 23400, 57600, 27000, 57000, 32400, 55200, 37200, 52200, 41400,
1754 48000, 45000, 42000, 47400, 35400, 48000, 30000, 46800, 24600, 43800, 20325, 39100,
1755 17850, 34275, 16800, 27600, 17400, 22200, 20400, 16200, 24600, 11400, 28800, 9000,
1756 32400, 7800, 33200, 7575, 33925, 11050, 35400, 10800, 37200, 10800, 41400, 11400,
1757 46200, 13200, 49800, 16200, 51600, 19200, 53400, 23400, 54000, 29400, 52800, 33600,
1758 49800, 39000, 45000, 42600, 39000, 44400, 33600, 43800, 28200, 42000, 24000, 37800,
1759 21000, 33000, 20400, 26400, 21600, 21000, 24600, 16200, 28200, 13200, 31875, 11625,
1760 33200, 15625, 36000, 15000, 39000, 15000, 43800, 16800, 46800, 19200, 49200, 23400,
1761 49800, 27600, 48750, 32700, 46350, 36275, 42600, 39000, 38400, 40200, 31800, 39000,
1762 28200, 36600, 25200, 31200, 24600, 26400, 26025, 21800, 28200, 18600, 30600, 16800,
1763 32575, 19875, 34200, 19200, 36000, 18600, 37200, 18600, 40375, 19125, 43200, 21000,
1764 45600, 24000, 46200, 27600, 45600, 30600, 43800, 33600, 41475, 35625, 37800, 36600,
1765 33600, 36000, 30000, 33600, 28200, 28800, 28800, 24600, 30000, 22200, 31200, 23400,
1766 30600, 25200, 30000, 27000, 30600, 30000, 31800, 32400, 34200, 34200, 38400, 34800,
1767 41400, 33000, 44025, 30225, 44400, 26400, 43200, 23400, 40900, 21200, 37800, 20400,
1768 34950, 20675, 32400, 22200, 30175, 19475, 28425, 21300, 27000, 24000, 26400, 27600,
1769 27000, 31800, 31200, 36600, 36600, 38400, 42600, 37200, 46200, 33600, 48000, 30000,
1770 47650, 24425, 45600, 20400, 42650, 18200, 39000, 16800, 35400, 16800, 33600, 17400,
1771 32875, 17675, 31100, 13850, 28200, 15600, 25200, 18600, 22800, 22800, 22200, 27000,
1772 23400, 33600, 26400, 38400, 31675, 41575, 37800, 42600, 40850, 42150, 42800, 41550,
1773 47050, 39025, 50100, 35375, 52200, 29400, 51675, 23950, 49800, 19200, 46200, 15600,
1774 41400, 13200, 37800, 12600, 35025, 12750, 33350, 13050, 32400, 9600, 30025, 10325,
1775 25925, 12725, 22200, 16800, 19800, 21000, 18600, 25800, 18600, 30000, 20400, 35400,
1776 22575, 39250, 25225, 41825, 28200, 43800, 33600, 46200, 39000, 46200, 44400, 45000,
1777 48650, 42350, 52800, 37800, 55200, 32400, 55800, 26400, 54600, 21000, 53400, 18000,
1778 50400, 14400, 47400, 12000, 42600, 9600, 39000, 9000, 36000, 9000, 34775, 9125,
1779 34300, 5600, 30000, 6600, 25800, 8400, 22025, 11350, 18725, 15125, 16200, 20400,
1780 15000, 24600, 15000, 30600, 16800, 36600, 20400, 42600, 25800, 46800, 31200, 49200,
1781 38400, 49800, 45000, 48600, 51000, 45000, 55475, 40225, 58200, 34800, 59400, 30000,
1782 59400, 25200, 58200, 19800, 55200, 14400, 52225, 11150, 47400, 7800, 44175, 6500,
1783 40200, 5400, 38400, 5400, 37200, 5400, 0, 0 };
1784 std::vector<Point> spiralpoints;
1785 for(unsigned int i = 0; i < 100000; i += 2) {
1786 Point pt(spiralcoords[i], spiralcoords[i+1]);
1787 if(pt == Point(0, 0)) break;
1788 spiralpoints.push_back(pt);
1789 }
1790 polygon_data<int> spiralpoly;
1791 spiralpoly.set(spiralpoints.begin(), spiralpoints.end());
1792 polygon_set_data<int> handset;
1793 handset += handpoly;
1794 polygon_set_data<int> spiralset;
1795 spiralset += spiralpoly;
1796 polygon_set_data<int> xorset = handset ^ spiralset;
1797 std::vector<polygon_data<int> > polys;
1798 polys += xorset;
1799 std::cout << polys.size() << std::endl;
1800 for(unsigned int i = 0; i < polys.size(); ++i)
1801 std::cout << polys[i] << std::endl;
1802 }
1803
1804 //void testHandFloat() {
1805 // using namespace gtl;
1806 // double handcoords[] = {
1807 //12375, 11050, 13175, 10200, 15825, 9275, 18750, 8525, 24150, 8300, 27575, 8400, 31775, 7800,
1808 //35975, 7200, 41375, 4800, 42575, 4200, 43175, 4200, 47375, 2400, 49175, 1800, 51150, 2200,
1809 //52275, 2825, 52625, 4150, 52375, 4975, 51575, 6000, 49275, 6850, 45700, 7950, 43175, 9600,
1810 //39575, 10800, 37775, 12000, 37775, 12600, 37775, 13800, 38975, 14400, 41375, 14400, 45575, 13200,
1811 //48600, 13000, 51575, 13200, 55175, 12600, 58775, 12600, 61175, 13200, 62375, 14400, 62550, 15700,
1812 //61975, 16875, 60775, 17600, 60100, 17675, 58525, 17675, 56150, 17575, 52175, 18000, 47975, 18600,
1813 //45575, 19200, 44375, 19200, 42675, 19325, 41600, 19775, 41600, 20500, 42100, 20825, 44975, 20400,
1814 //48575, 20400, 52775, 21000, 53975, 21000, 57575, 21000, 62375, 21000, 65450, 22000, 66300, 23100,
1815 //66100, 24550, 64750, 25925, 62975, 26400, 61175, 26400, 58775, 26400, 56025, 26050, 53450, 26025,
1816 //50975, 26400, 48575, 26400, 46775, 26400, 43650, 26075, 41375, 26400, 40775, 27000, 40775, 27600,
1817 //42225, 28650, 44375, 29400, 48575, 30000, 50975, 31200, 53975, 31800, 58775, 33000, 61200, 34300,
1818 //62375, 35400, 62375, 37200, 61175, 38400, 60000, 38700, 57575, 38400, 54550, 37575, 50975, 36600,
1819 //49075, 36125, 47750, 36125, 45700, 35425, 42350, 34350, 38900, 33775, 30575, 33000, 26975, 33600,
1820 //25975, 34900, 26375, 36600, 28175, 38400, 30575, 40800, 32375, 43800, 33200, 46200, 33200, 48000,
1821 //32650, 49300, 31425, 50000, 29950, 50125, 28825, 49375, 27575, 48000, 25825, 46000, 23975, 44100,
1822 //22175, 42600, 19775, 39600, 17325, 37300, 14975, 34800, 13175, 31800, 10775, 29400, 9600, 27400,
1823 //10175, 27000, 11375, 27600, 12575, 28800, 14375, 31800, 16175, 34800, 18575, 37200, 21575, 39000,
1824 //22775, 40200, 23975, 41400, 24575, 42600, 26375, 44400, 28325, 46000, 29850, 46775, 31175, 46200,
1825 //31550, 44575, 30575, 43200, 28775, 40800, 25775, 38400, 24575, 34800, 24750, 33175, 26975, 31800,
1826 //29975, 31800, 33575, 31800, 37775, 32400, 39575, 33000, 41975, 33600, 45150, 34175, 46975, 34750,
1827 //48575, 35400, 50975, 35400, 51575, 34800, 51875, 33725, 50775, 32575, 48575, 31800, 45750, 30875,
1828 //43775, 30600, 41375, 29400, 38975, 28800, 35975, 28200, 34775, 27600, 34175, 27000, 34775, 25800,
1829 //37175, 25200, 40175, 25200, 43175, 25200, 46775, 25200, 50975, 25425, 53375, 25200, 55175, 24600,
1830 //55525, 23450, 53975, 22200, 52775, 22200, 49075, 21850, 45950, 21925, 40775, 21600, 37775, 21600,
1831 //35150, 21350, 34325, 20950, 34175, 19800, 35975, 19200, 38375, 19200, 40750, 18900, 42575, 18600,
1832 //44375, 18000, 47975, 17400, 50375, 17125, 52025, 16625, 52775, 15600, 52100, 14625, 49675, 14125,
1833 //48625, 14125, 46775, 14400, 44375, 15000, 41375, 15150, 37700, 15275, 34775, 15600, 32850, 15925,
1834 //31775, 15600, 31425, 14875, 32375, 13800, 36575, 11400, 38975, 10200, 41375, 9000, 43075, 8150,
1835 //43650, 7200, 43325, 6250, 42225, 5825, 40800, 6275, 38900, 6925, 35375, 8400, 32375, 10200,
1836 //27575, 11400, 22775, 12600, 19775, 13225, 16775, 13800, 14975, 14400, 13050, 14000, 11975, 12600,
1837 // 0, 0 };
1838 // std::vector<point_data<double> > handpoints;
1839 // for(unsigned int i = 0; i < 100000; i += 2) {
1840 // point_data<double> pt(handcoords[i], handcoords[i+1]);
1841 // if(pt == point_data<double> (0, 0)) break;
1842 // handpoints.push_back(pt);
1843 // }
1844 // polygon_data<double> handpoly;
1845 // handpoly.set(handpoints.begin(), handpoints.end());
1846 // double spiralcoords [] = {
1847 //37200, 3600, 42075, 4025, 47475, 5875, 51000, 7800, 55800, 12300, 59000, 17075, 60000, 20400,
1848 //61200, 25800, 61200, 29400, 60600, 33600, 58800, 38400, 55800, 42600, 53200, 45625,
1849 //49200, 48600, 43200, 51000, 35400, 51600, 29400, 50400, 23400, 47400, 19200, 43800,
1850 //16200, 39600, 14400, 35400, 13200, 29400, 13200, 24000, 15000, 18600, 17400, 13800,
1851 //20525, 10300, 24600, 7200, 29400, 4800, 32450, 4000, 34825, 3675, 35625, 3625,
1852 //35825, 7275, 39600, 7200, 43800, 8400, 46800, 9600, 50400, 12000, 53400, 15000,
1853 //55800, 18600, 57000, 23400, 57600, 27000, 57000, 32400, 55200, 37200, 52200, 41400,
1854 //48000, 45000, 42000, 47400, 35400, 48000, 30000, 46800, 24600, 43800, 20325, 39100,
1855 //17850, 34275, 16800, 27600, 17400, 22200, 20400, 16200, 24600, 11400, 28800, 9000,
1856 //32400, 7800, 33200, 7575, 33925, 11050, 35400, 10800, 37200, 10800, 41400, 11400,
1857 //46200, 13200, 49800, 16200, 51600, 19200, 53400, 23400, 54000, 29400, 52800, 33600,
1858 //49800, 39000, 45000, 42600, 39000, 44400, 33600, 43800, 28200, 42000, 24000, 37800,
1859 //21000, 33000, 20400, 26400, 21600, 21000, 24600, 16200, 28200, 13200, 31875, 11625,
1860 //33200, 15625, 36000, 15000, 39000, 15000, 43800, 16800, 46800, 19200, 49200, 23400,
1861 //49800, 27600, 48750, 32700, 46350, 36275, 42600, 39000, 38400, 40200, 31800, 39000,
1862 //28200, 36600, 25200, 31200, 24600, 26400, 26025, 21800, 28200, 18600, 30600, 16800,
1863 //32575, 19875, 34200, 19200, 36000, 18600, 37200, 18600, 40375, 19125, 43200, 21000,
1864 //45600, 24000, 46200, 27600, 45600, 30600, 43800, 33600, 41475, 35625, 37800, 36600,
1865 //33600, 36000, 30000, 33600, 28200, 28800, 28800, 24600, 30000, 22200, 31200, 23400,
1866 //30600, 25200, 30000, 27000, 30600, 30000, 31800, 32400, 34200, 34200, 38400, 34800,
1867 //41400, 33000, 44025, 30225, 44400, 26400, 43200, 23400, 40900, 21200, 37800, 20400,
1868 //34950, 20675, 32400, 22200, 30175, 19475, 28425, 21300, 27000, 24000, 26400, 27600,
1869 //27000, 31800, 31200, 36600, 36600, 38400, 42600, 37200, 46200, 33600, 48000, 30000,
1870 //47650, 24425, 45600, 20400, 42650, 18200, 39000, 16800, 35400, 16800, 33600, 17400,
1871 //32875, 17675, 31100, 13850, 28200, 15600, 25200, 18600, 22800, 22800, 22200, 27000,
1872 //23400, 33600, 26400, 38400, 31675, 41575, 37800, 42600, 40850, 42150, 42800, 41550,
1873 //47050, 39025, 50100, 35375, 52200, 29400, 51675, 23950, 49800, 19200, 46200, 15600,
1874 //41400, 13200, 37800, 12600, 35025, 12750, 33350, 13050, 32400, 9600, 30025, 10325,
1875 //25925, 12725, 22200, 16800, 19800, 21000, 18600, 25800, 18600, 30000, 20400, 35400,
1876 //22575, 39250, 25225, 41825, 28200, 43800, 33600, 46200, 39000, 46200, 44400, 45000,
1877 //48650, 42350, 52800, 37800, 55200, 32400, 55800, 26400, 54600, 21000, 53400, 18000,
1878 //50400, 14400, 47400, 12000, 42600, 9600, 39000, 9000, 36000, 9000, 34775, 9125,
1879 //34300, 5600, 30000, 6600, 25800, 8400, 22025, 11350, 18725, 15125, 16200, 20400,
1880 //15000, 24600, 15000, 30600, 16800, 36600, 20400, 42600, 25800, 46800, 31200, 49200,
1881 //38400, 49800, 45000, 48600, 51000, 45000, 55475, 40225, 58200, 34800, 59400, 30000,
1882 //59400, 25200, 58200, 19800, 55200, 14400, 52225, 11150, 47400, 7800, 44175, 6500,
1883 //40200, 5400, 38400, 5400, 37200, 5400, 0, 0 };
1884 // std::vector<point_data<double> > spiralpoints;
1885 // for(unsigned int i = 0; i < 100000; i += 2) {
1886 // point_data<double> pt(spiralcoords[i], spiralcoords[i+1]);
1887 // if(pt == point_data<double> (0, 0)) break;
1888 // spiralpoints.push_back(pt);
1889 // }
1890 // polygon_data<double> spiralpoly;
1891 // spiralpoly.set(spiralpoints.begin(), spiralpoints.end());
1892 // polygon_set_data<double> handset;
1893 // handset += handpoly;
1894 // polygon_set_data<double> spiralset;
1895 // spiralset += spiralpoly;
1896 // polygon_set_data<double> xorset = handset ^ spiralset;
1897 // std::vector<polygon_data<double> > polys;
1898 // polys += xorset;
1899 // std::cout << polys.size() << std::endl;
1900 // for(unsigned int i = 0; i < polys.size(); ++i)
1901 // std::cout << polys[i] << std::endl;
1902 //}
1903
testDirectionalSize()1904 bool testDirectionalSize() {
1905 {
1906 PolygonSet ps(VERTICAL);
1907 ps += Rectangle(0, 0, 100, 100);
1908 ps.resize(0, -10, 0, -10);
1909 std::vector<Rectangle> rects;
1910 ps.get(rects);
1911 if(rects.size() != 1) return false;
1912 std::cout << rects[0] << std::endl;
1913 std::cout << Rectangle(0, 0, 90, 90) << std::endl;
1914 if(rects[0] != Rectangle(0, 0, 90, 90)) return false;
1915 }
1916 {
1917 PolygonSet ps(VERTICAL);
1918 ps += Rectangle(0, 0, 100, 100);
1919 ps.resize(0, 0, 0, -10);
1920 std::vector<Rectangle> rects;
1921 ps.get(rects);
1922 if(rects.size() != 1) return false;
1923 std::cout << rects[0] << std::endl;
1924 std::cout << Rectangle(0, 0, 100, 90) << std::endl;
1925 if(rects[0] != Rectangle(0, 0, 100, 90)) return false;
1926 }
1927 {
1928 PolygonSet ps;
1929 ps += Rectangle(0, 0, 100, 100);
1930 ps.resize(0, -10, 0, 0);
1931 std::vector<Rectangle> rects;
1932 ps.get(rects);
1933 if(rects.size() != 1) return false;
1934 std::cout << rects[0] << std::endl;
1935 std::cout << Rectangle(0, 0, 90, 100) << std::endl;
1936 if(rects[0] != Rectangle(0, 0, 90, 100)) return false;
1937 }
1938 {
1939 PolygonSet ps;
1940 ps += Rectangle(0, 0, 100, 100);
1941 ps.resize(0, 0, -10, 0);
1942 std::vector<Rectangle> rects;
1943 ps.get(rects);
1944 if(rects.size() != 1) return false;
1945 std::cout << rects[0] << std::endl;
1946 std::cout << Rectangle(0, 10, 100, 100) << std::endl;
1947 if(rects[0] != Rectangle(0, 10, 100, 100)) return false;
1948 }
1949 {
1950 PolygonSet ps;
1951 ps += Rectangle(0, 0, 100, 100);
1952 ps.resize(-10, 0, 0, 0);
1953 std::vector<Rectangle> rects;
1954 ps.get(rects);
1955 if(rects.size() != 1) return false;
1956 std::cout << rects[0] << std::endl;
1957 std::cout << Rectangle(10, 0, 100, 100) << std::endl;
1958 if(rects[0] != Rectangle(10, 0, 100, 100)) return false;
1959 }
1960 {
1961 PolygonSet ps;
1962 ps += Rectangle(0, 0, 100, 100);
1963 ps.resize(-10, 10, 0, 0);
1964 std::vector<Rectangle> rects;
1965 ps.get(rects);
1966 if(rects.size() != 1) return false;
1967 std::cout << rects[0] << std::endl;
1968 std::cout << Rectangle(10, 0, 110, 100) << std::endl;
1969 if(rects[0] != Rectangle(10, 0, 110, 100)) return false;
1970 }
1971 {
1972 PolygonSet ps;
1973 ps += Rectangle(0, 0, 100, 100);
1974 ps.resize(-10, 10, 10, -10);
1975 std::vector<Rectangle> rects;
1976 ps.get(rects);
1977 if(rects.size() != 1) return false;
1978 std::cout << rects[0] << std::endl;
1979 std::cout << Rectangle(10, -10, 110, 90) << std::endl;
1980 if(rects[0] != Rectangle(10, -10, 110, 90)) return false;
1981 }
1982 {
1983 PolygonSet ps;
1984 ps += Rectangle(0, 0, 100, 100);
1985 ps.resize(10, 10, -10, -10);
1986 std::vector<Rectangle> rects;
1987 ps.get(rects);
1988 if(rects.size() != 1) return false;
1989 std::cout << rects[0] << std::endl;
1990 std::cout << Rectangle(-10, 10, 110, 90) << std::endl;
1991 if(rects[0] != Rectangle(-10, 10, 110, 90)) return false;
1992 }
1993 return true;
1994 }
1995
testMaxCover()1996 bool testMaxCover() {
1997 std::vector<Rectangle> rects;
1998 rects.push_back(Rectangle(Interval(60, 124), Interval( 1, 3)));
1999 rects.push_back(Rectangle(Interval(59, 83), Interval( 9, 28)));
2000 rects.push_back(Rectangle(Interval(90, 124), Interval( 3, 29)));
2001 rects.push_back(Rectangle(Interval(64, 124), Interval( 29, 35)));
2002 rects.push_back(Rectangle(Interval(64, 102), Interval( 35, 49)));
2003 rects.push_back(Rectangle(Interval(1, 20), Interval( 44, 60)));
2004 rects.push_back(Rectangle(Interval(50, 102), Interval( 49, 71)));
2005 rects.push_back(Rectangle(Interval(49, 102), Interval( 71, 72)));
2006 rects.push_back(Rectangle(Interval(49, 94), Interval( 72, 75)));
2007 rects.push_back(Rectangle(Interval(50, 74), Interval( 75, 81)));
2008 rects.push_back(Rectangle(Interval(90, 127), Interval( 75, 81)));
2009 rects.push_back(Rectangle(Interval(50, 127), Interval( 81, 82)));
2010 rects.push_back(Rectangle(Interval(3, 7), Interval( 60, 88)));
2011 rects.push_back(Rectangle(Interval(50, 92), Interval( 82, 94)));
2012 rects.push_back(Rectangle(Interval(58, 92), Interval( 94, 111)));
2013 std::vector<Rectangle> expected_result;
2014 expected_result.push_back(Rectangle(Interval(60, 124), Interval( 1, 3)));
2015 expected_result.push_back(Rectangle(Interval(90, 124), Interval( 1, 35)));
2016 expected_result.push_back(Rectangle(Interval(90, 102), Interval( 1, 72)));
2017 expected_result.push_back(Rectangle(Interval(90, 94 ), Interval(1 ,82)));
2018 expected_result.push_back(Rectangle(Interval(90, 92), Interval( 1, 111)));
2019 expected_result.push_back(Rectangle(Interval(59, 83 ), Interval(9, 28)));
2020 expected_result.push_back(Rectangle(Interval(64, 124), Interval( 29, 35)));
2021 expected_result.push_back(Rectangle(Interval(64, 102), Interval( 29, 72)));
2022 expected_result.push_back(Rectangle(Interval(64, 94), Interval( 29, 75)));
2023 expected_result.push_back(Rectangle(Interval(64, 74), Interval( 29, 111)));
2024 expected_result.push_back(Rectangle(Interval(1, 20), Interval( 44, 60)));
2025 expected_result.push_back(Rectangle(Interval(3, 7), Interval( 44, 88)));
2026 expected_result.push_back(Rectangle(Interval(50, 102 ), Interval(49, 72)));
2027 expected_result.push_back(Rectangle(Interval(50, 94), Interval( 49, 75)));
2028 expected_result.push_back(Rectangle(Interval(50, 74), Interval( 49, 94)));
2029 expected_result.push_back(Rectangle(Interval(58, 74), Interval( 49, 111)));
2030 expected_result.push_back(Rectangle(Interval(49, 102 ), Interval(71, 72)));
2031 expected_result.push_back(Rectangle(Interval(49, 94 ), Interval(71, 75)));
2032 expected_result.push_back(Rectangle(Interval(90, 127), Interval( 75, 82)));
2033 expected_result.push_back(Rectangle(Interval(50, 127), Interval( 81, 82)));
2034 expected_result.push_back(Rectangle(Interval(50, 92), Interval( 81, 94)));
2035 expected_result.push_back(Rectangle(Interval(58, 92), Interval( 81, 111)));
2036 std::vector<Rectangle> result;
2037 get_max_rectangles(result, rects);
2038 std::cout << "result XOR clean: " << equivalence(result, rects) << std::endl;
2039 std::cout << "expected result XOR clean: " << equivalence(expected_result, rects) << std::endl;
2040 std::vector<Rectangle>& output = result;
2041 std::vector<Rectangle>& voutput = expected_result;
2042 std::sort(output.begin(), output.end(), less_rectangle_concept< Rectangle, Rectangle>());
2043 std::sort(voutput.begin(), voutput.end(), less_rectangle_concept< Rectangle, Rectangle>());
2044 if(output != voutput) {
2045 std::cerr << "Max Rectangle TEST failed\n";
2046 for(unsigned int i = 0; i < output.size(); ++i) {
2047 std::cerr << output[i] << std::endl;
2048 }
2049 std::cerr << "Incorrect result\n";
2050 for(unsigned int i = 0; i < voutput.size(); ++i) {
2051 std::cerr << voutput[i] << std::endl;
2052 }
2053 std::cerr << "Max Rectangle TEST failed\n";
2054 for(unsigned int i = 0; i < rects.size(); ++i) {
2055 std::cout << rects[i] << std::endl;
2056 }
2057 return false;
2058 }
2059 return true;
2060 }
2061
max_cover_stress_test()2062 void max_cover_stress_test() {
2063 for(unsigned int k = 3; k < 20; k++) {
2064 for(unsigned int i = 0; i < k * k; ++i) {
2065 std::vector<Rectangle> rects, result;
2066 //std::cout << "test " << i << std::endl;
2067 for(unsigned int j = 0; j < k; ++j) {
2068 int x1 = rand() % 100;
2069 int x2 = rand() % 50;
2070 int y1 = rand() % 100;
2071 int y2 = rand() % 50;
2072 rects.push_back(Rectangle(x1, y1, x1+x2, y1+y2));
2073 //std::cout << rects.back() << std::endl;
2074 }
2075 get_max_rectangles(result, rects);
2076 }
2077 }
2078 }
2079
2080 // namespace boost { namespace polygon{
2081 // template <typename GCT, typename T>
2082 // struct view_of {};
2083
2084 // template <typename T>
2085 // struct view_of<polygon_45_concept, T> {
2086 // const T* t;
2087 // view_of(const T& obj) : t(&obj) {}
2088 // typedef typename polygon_traits<T>::coordinate_type coordinate_type;
2089 // typedef typename polygon_traits<T>::iterator_type iterator_type;
2090 // typedef typename polygon_traits<T>::point_type point_type;
2091
2092 // /// Get the begin iterator
2093 // inline iterator_type begin() const {
2094 // return polygon_traits<T>::begin_points(*t);
2095 // }
2096
2097 // /// Get the end iterator
2098 // inline iterator_type end() const {
2099 // return polygon_traits<T>::end_points(*t);
2100 // }
2101
2102 // /// Get the number of sides of the polygon
2103 // inline unsigned int size() const {
2104 // return polygon_traits<T>::size(*t);
2105 // }
2106
2107 // /// Get the winding direction of the polygon
2108 // inline winding_direction winding() const {
2109 // return polygon_traits<T>::winding(*t);
2110 // }
2111 // };
2112
2113 // template <typename T1, typename T2>
2114 // view_of<T1, T2> view_as(const T2& obj) { return view_of<T1, T2>(obj); }
2115
2116 // template <typename T>
2117 // struct geometry_concept<view_of<polygon_45_concept, T> > {
2118 // typedef polygon_45_concept type;
2119 // };
2120
2121 // template <typename T>
2122 // struct view_of<polygon_90_concept, T> {
2123 // const T* t;
2124 // view_of(const T& obj) : t(&obj) {}
2125 // typedef typename polygon_traits<T>::coordinate_type coordinate_type;
2126 // typedef typename polygon_traits<T>::iterator_type iterator_type;
2127 // typedef typename polygon_traits<T>::point_type point_type;
2128 // typedef iterator_points_to_compact<iterator_type, point_type> compact_iterator_type;
2129
2130 // /// Get the begin iterator
2131 // inline compact_iterator_type begin_compact() const {
2132 // return compact_iterator_type(polygon_traits<T>::begin_points(*t),
2133 // polygon_traits<T>::end_points(*t));
2134 // }
2135
2136 // /// Get the end iterator
2137 // inline compact_iterator_type end_compact() const {
2138 // return compact_iterator_type(polygon_traits<T>::end_points(*t),
2139 // polygon_traits<T>::end_points(*t));
2140 // }
2141
2142 // /// Get the number of sides of the polygon
2143 // inline unsigned int size() const {
2144 // return polygon_traits<T>::size(*t);
2145 // }
2146
2147 // /// Get the winding direction of the polygon
2148 // inline winding_direction winding() const {
2149 // return polygon_traits<T>::winding(*t);
2150 // }
2151 // };
2152
2153 // template <typename T>
2154 // struct geometry_concept<view_of<polygon_90_concept, T> > {
2155 // typedef polygon_90_concept type;
2156 // };
2157 // }}
2158 using namespace gtl;
2159
2160 //this test fails and I'd like to get it to pass
test_colinear_duplicate_points()2161 bool test_colinear_duplicate_points() {
2162 Point pts[6] = { Point(0, 10), Point(0, 0), Point(100, 0), Point(100, 100), Point(0, 100), Point(0, 10)};
2163 Polygon45 p1;
2164 p1.set(pts, pts+5);
2165 Polygon45 pg;
2166 pg.set(pts, pts+6);
2167 Polygon45 p2;
2168 p2.set(pts+1, pts+6);
2169 std::cout << p2 << std::endl;
2170 if(!equivalence(view_as<polygon_90_concept>(p2), view_as<polygon_90_concept>(pg))) return false;
2171 std::cout << p1 << std::endl;
2172 if(!equivalence(view_as<polygon_90_concept>(p1), view_as<polygon_90_concept>(pg))) return false;
2173 return true;
2174 }
2175
test_extents()2176 bool test_extents() {
2177 PolygonSet psT(gtl::VERTICAL);
2178 //int xy[] = { 126, 69, 54, 69, 54, 81, 126, 81 };
2179 //CPolygonQuery polygon(0, 4, xy);
2180 //Rectangle rectIn(54, 69, 126, 81);
2181 polygon_data<int> polygon;
2182 std::vector<Point> pts;
2183 pts.push_back(Point(126, 69));
2184 pts.push_back(Point(54, 69));
2185 pts.push_back(Point(54, 81));
2186 pts.push_back(Point(126, 81));
2187 set_points(polygon, pts.begin(), pts.end());
2188 psT.insert(view_as<polygon_90_concept>(polygon));
2189
2190 Rectangle rect, rect2;
2191 psT.extents(rect2);
2192 gtl::extents(rect, psT);
2193
2194 if (rect != rect2) {
2195 std::cout << "gtl::Rectangles differ: " << gtl::xl(rect) << " " << gtl::xh(rect) << " " << gtl::yl(rect) << " " << gtl::yh(rect) << std::endl;
2196 std::cout << " " << gtl::xl(rect2) << " " << gtl::xh(rect2) << " " << gtl::yl(rect2) << " " << gtl::yh(rect2) << std::endl;
2197 return false;
2198 }
2199 return true;
2200 }
2201
test_extents2()2202 bool test_extents2() {
2203 Polygon45Set psT;
2204 Point xy[] = { Point(130, 50), Point(50, 50), Point(50, 100), Point(119, 100),
2205 Point(119, 59), Point(89, 89), Point(59, 59), Point(119, 59), Point(119, 100), Point(130, 100) };
2206 Polygon45 polygon(xy, xy+10);
2207
2208 psT.insert(polygon);
2209 psT += 2;
2210
2211 Rectangle rect, rect2;
2212 psT.extents(rect2);
2213 gtl::extents(rect, psT);
2214 std::cout << "Extents: " << gtl::xl(rect) << " " << gtl::xh(rect) << " " << gtl::yl(rect) << " " << gtl::yh(rect) << std::endl;
2215 std::cout << "Extents: " << gtl::xl(rect2) << " " << gtl::xh(rect2) << " " << gtl::yl(rect2) << " " << gtl::yh(rect2) << std::endl;
2216 std::vector<Polygon45WithHoles> pwhs;
2217 psT.get(pwhs);
2218 for(unsigned int i = 0; i < pwhs.size(); ++i) {
2219 std::cout << pwhs[i] << std::endl;
2220 }
2221 return gtl::equivalence(rect, rect2);
2222 }
2223
2224 /*************New Polygon Formation Tests********************/
2225 /*
2226 *
2227 * Test Input:
2228 * +--------------------+
2229 * | +-------+ |
2230 * | | | |
2231 * | | | |
2232 * +-----+ | | |
2233 * | | | |
2234 * | | | |
2235 * +-----+ | | |
2236 * | | | |
2237 * | | | |
2238 * | +-------+ |
2239 * +--------+ |
2240 * | |
2241 * | |
2242 * +--------+ |
2243 * | |
2244 * | |
2245 * +--------+ |
2246 * | |
2247 * | |
2248 * +--------+ |
2249 * | |
2250 * | |
2251 * +--------------------+
2252 *
2253 * Test Plan:
2254 * a. call 'get(out, param)' , param >=4
2255 * b. check if each polygon in the container is <= param
2256 * c. check the area of all the pieces sum up to original piece
2257 */
2258 typedef int intDC;
2259 typedef boost::polygon::polygon_90_with_holes_data<intDC> GTLPolygon;
2260 typedef boost::polygon::polygon_90_set_data<intDC> GTLPolygonSet;
2261 typedef boost::polygon::polygon_90_concept GTLPolygonConcept;
2262 typedef boost::polygon::point_data<intDC> GTLPoint;
2263 inline void PrintPolygon(const GTLPolygon&);
2264 inline GTLPolygon CreateGTLPolygon(const int*, size_t);
test_new_polygon_formation(int argc,char ** argv)2265 int test_new_polygon_formation(int argc, char** argv){
2266 // //
2267 // Sub-Test-1: do a Boolean and call the new get //
2268 // //
2269 int coordinates[] = {0,0, 10,0, 10,10, 0,10};
2270 int coordinates1[] = {9,1, 20,1, 20,10, 9,10};
2271 std::vector<GTLPoint> pts;
2272 size_t count = sizeof(coordinates)/(2*sizeof(intDC));
2273 size_t count1 = sizeof(coordinates1)/(2*sizeof(intDC));
2274 GTLPolygon poly, poly1;
2275 GTLPolygonSet polySet;
2276
2277 poly = CreateGTLPolygon(coordinates, count);
2278 poly1 = CreateGTLPolygon(coordinates1, count1);
2279
2280 polySet.insert(poly);
2281 polySet.insert(poly1);
2282
2283 std::vector<GTLPolygon> result;
2284 polySet.get(result, 100);
2285
2286 if(result.size() > 1){
2287 std::cerr << "FAILED: expecting only one polygon because the"
2288 " threshold is 100" << std::endl;
2289 return 1;
2290 }
2291
2292 if(result[0].size() != 6){
2293 std::cerr << "FAILED: expecting only 6 vertices" << std::endl;
2294 return 1;
2295 }
2296
2297 if(area(result[0]) != 190){
2298 std::cerr <<"FAILED: expecting only 6 vertices" << std::endl;
2299 return 1;
2300 }
2301
2302 //expect no more than 1 polygon
2303 std::cout << "Found " << result.size() << "polygons after union"
2304 << std::endl;
2305 for(size_t i=0; i<result.size(); i++){
2306 PrintPolygon(result[i]);
2307 }
2308
2309 intDC shell_coords[] = {0,0, 10,0, 10,21, 0,21, 0,15, 3,15, 3,13,
2310 0,13, 0,10, 5,10, 5,8, 0,8, 0,5, 5,5, 5,3, 0,3};
2311 intDC hole_coords[] = {4,11, 7,11, 7,19, 4,19};
2312 GTLPolygon slice_polygon, slice_hole;
2313 count = sizeof(shell_coords)/(2*sizeof(intDC));
2314 count1 = sizeof(hole_coords)/(2*sizeof(intDC));
2315
2316 slice_polygon = CreateGTLPolygon(shell_coords, count);
2317 slice_hole = CreateGTLPolygon(hole_coords, count1);
2318
2319 result.clear();
2320 polySet.clear();
2321 polySet.insert(slice_polygon);
2322 polySet.insert(slice_hole, true);
2323
2324 polySet.get(result);
2325 double gold_area = 0;
2326 std::cout << "Found " << result.size() << " slices" << std::endl;
2327 for(size_t i=0; i<result.size(); i++){
2328 PrintPolygon(result[i]);
2329 gold_area += area(result[i]);
2330 }
2331
2332 result.clear();
2333 polySet.get(result, 6);
2334 double platinum_area = 0;
2335 std::cout << "Found " << result.size() << " slices" << std::endl;
2336 for(size_t i=0; i<result.size(); i++){
2337 PrintPolygon(result[i]);
2338 platinum_area += area(result[i]);
2339 if(result[i].size() > 6){
2340 std::cerr << "FAILED: expecting size to be less than 6" << std::endl;
2341 return 1;
2342 }
2343 }
2344
2345 std::cout << "platinum_area = " << platinum_area << " , gold_area="
2346 << gold_area << std::endl;
2347 if( platinum_area != gold_area){
2348 std::cerr << "FAILED: Area mismatch" << std::endl;
2349 return 1;
2350 }
2351 std::cout << "[SUB-TEST-1] PASSED\n";
2352
2353 result.clear();
2354 polySet.get(result, 4);
2355 platinum_area = 0;
2356 std::cout << "Found " << result.size() << " slices" << std::endl;
2357 for(size_t i=0; i<result.size(); i++){
2358 PrintPolygon(result[i]);
2359 platinum_area += area(result[i]);
2360 if(result[i].size() > 4){
2361 std::cerr << "FAILED: expecting size to be < 4" << std::endl;
2362 return 1;
2363 }
2364 }
2365
2366 std::cout << "platinum_area=" << platinum_area << ", gold_area="
2367 << gold_area << std::endl;
2368
2369 if( platinum_area != gold_area){
2370 std::cerr << "FAILED: Area mismatch" << std::endl;
2371 return 1;
2372 }
2373
2374 std::cout << "[SUB-TEST-1] PASSED" << std::endl;
2375 return 0;
2376 }
2377
2378 /*
2379 * INPUT:
2380 * +--------+
2381 * | |
2382 * | |
2383 * | +---+
2384 * | |
2385 * | +---+
2386 * | |
2387 * +--------+
2388 * X
2389 *
2390 * TEST PLAN: as the sweepline moves and reaches
2391 * X the number of vertices in the solid jumps by 4
2392 * instead of 2. So make sure we don't get a 6 vertex
2393 * polygon when the threshold is 4 and 6.
2394 */
test_new_polygon_formation_marginal_threshold(int argc,char **)2395 int test_new_polygon_formation_marginal_threshold(int argc, char**){
2396 std::vector<GTLPoint> pts;
2397 GTLPolygon polygon;
2398 GTLPolygonSet pset;
2399 std::vector<GTLPolygon> result;
2400 intDC coords[] = {0,0, 15,0, 15,10, 10,10, 10,15, 5,15, 5,10, 0,10};
2401 size_t count = sizeof(coords)/(2*sizeof(intDC));
2402
2403 polygon = CreateGTLPolygon(coords, count);
2404 pset.insert(polygon);
2405
2406 for(size_t i=0; i<1; i++){
2407 pset.get(result, i ? 4 : 6);
2408 double gold_area = 175, plat_area = 0;
2409 for(size_t i=0; i<result.size(); i++){
2410 if(result[i].size() > (i ? 4 : 6) ){
2411 size_t expected = i ? 4 : 6;
2412 std::cerr << "FAILED: Expecting no more than " <<
2413 expected << " vertices" << std::endl;
2414 return 1;
2415 }
2416 PrintPolygon(result[i]);
2417 plat_area += area(result[i]);
2418 }
2419
2420 if(plat_area != gold_area){
2421 std::cerr << "FAILED area mismatch gold=" << gold_area <<
2422 " plat=" << plat_area << std::endl;
2423 return 1;
2424 }
2425 }
2426 std::cout << "Test Passed" << std::endl;
2427 return 0;
2428 }
2429
PrintPolygon(const GTLPolygon & p)2430 inline void PrintPolygon(const GTLPolygon& p){
2431 //get an iterator of the point_data<int>
2432 boost::polygon::point_data<int> pt;
2433 boost::polygon::polygon_90_data<int>::iterator_type itr;
2434
2435 size_t vertex_id = 0;
2436 for(itr = p.begin(); itr != p.end(); ++itr){
2437 pt = *itr;
2438 std::cout << "Vertex-" << ++vertex_id << "(" << pt.x() <<
2439 "," << pt.y() << ")" << std::endl;
2440 }
2441 }
2442
2443 // size: is the number of vertices //
CreateGTLPolygon(const int * coords,size_t size)2444 inline GTLPolygon CreateGTLPolygon(const int *coords, size_t size){
2445 GTLPolygon r;
2446 std::vector<GTLPoint> pts;
2447
2448 for(size_t i=0; i<size; i++){
2449 pts.push_back( GTLPoint(coords[2*i], coords[2*i+1]) );
2450 }
2451 boost::polygon::set_points(r, pts.begin(), pts.end());
2452 return r;
2453 }
2454
2455 /************************************************************/
2456
main()2457 int main() {
2458 test_view_as();
2459 //this test fails and I'd like to get it to pass
2460 //if(!test_colinear_duplicate_points()) return 1;
2461 if(!test_extents2()) return 1;
2462 if(!test_extents()) return 1;
2463 if(!testMaxCover()) return 1;
2464 //max_cover_stress_test(); //does not include functional testing
2465 if(!testDirectionalSize()) return 1;
2466 testHand();
2467 //testHandFloat();
2468 if(!testpip()) return 1;
2469 {
2470 PolygonSet ps;
2471 Polygon p;
2472 assign(ps, p);
2473 }
2474 if(!testViewCopyConstruct()) return 1;
2475 if(!test_grow_and_45()) return 1;
2476 if(!test_self_xor_45()) return 1;
2477 if(!test_self_xor()) return 1;
2478 if(!test_directional_resize()) return 1;
2479 if(!test_scaling_by_floating()) return 1;
2480 if(!test_SQRT1OVER2()) return 1;
2481 if(!test_get_trapezoids()) return 1;
2482 if(!test_get_rectangles()) return 1;
2483 if(!test_45_concept_interact()) return 1;
2484 if(!test_45_touch_r()) return 1;
2485 if(!test_45_touch_ur()) return 1;
2486 if(!test_45_touch()) return 1;
2487 if(!test_45_touch_boundaries()) return 1;
2488 {
2489 Point pts[] = {Point(0,0), Point(5, 5), Point(5, 0)};
2490 Polygon45 p45(pts, pts+3);
2491 pts[1] = Point(0, 5);
2492 Polygon45 p452(pts, pts+3);
2493 if(!test_two_polygons(p45,p452)) return 1;
2494 pts[2] = Point(5,5);
2495 p45.set(pts, pts+3);
2496 if(!test_two_polygons(p45,p452)) return 1;
2497 pts[0] = Point(5,0);
2498 p452.set(pts, pts+3);
2499 if(!test_two_polygons(p45, p452)) return 1;
2500 Point pts2[] = {Point(0,5), Point(5, 5), Point(5, 0)};
2501 Point pts3[] = {Point(0,0), Point(5, 5), Point(5, 0)};
2502 p45.set(pts2, pts2 + 3);
2503 p452.set(pts3, pts3+3);
2504 if(!test_two_polygons(p45, p452)) return 1;
2505 Point pts4[] = {Point(0, 5), Point(3, 2), Point(3,5)};
2506 Point pts5[] = {Point(0,0), Point(5, 5), Point(5, 0)};
2507 p45.set(pts4, pts4+3);
2508 p452.set(pts5, pts5+3);
2509 if(!test_two_polygons(p45, p452)) return 1;
2510 }
2511 {
2512 std::vector<point_data<int> > pts;
2513 pts.push_back(point_data<int>(0, 0));
2514 pts.push_back(point_data<int>(10, 0));
2515 pts.push_back(point_data<int>(10, 10));
2516 pts.push_back(point_data<int>(0, 10));
2517 std::vector<point_data<int> > pts2;
2518 pts2.push_back(point_data<int>(0, 0));
2519 pts2.push_back(point_data<int>(10, 10));
2520 pts2.push_back(point_data<int>(0, 20));
2521 pts2.push_back(point_data<int>(-10, 10));
2522 std::vector<point_data<int> > pts3;
2523 pts3.push_back(point_data<int>(0, 0));
2524 pts3.push_back(point_data<int>(10, 11));
2525 pts3.push_back(point_data<int>(0, 20));
2526 pts3.push_back(point_data<int>(-100, 8));
2527 polygon_data<int> p, p1; p.set(pts3.begin(), pts3.end());
2528 polygon_45_data<int> p45, p451; p45.set(pts2.begin(), pts2.end());
2529 polygon_90_data<int> p90, p901; p90.set(pts.begin(), pts.end());
2530 polygon_with_holes_data<int> pwh, pwh1; pwh.set(pts3.begin(), pts3.end());
2531 polygon_45_with_holes_data<int> p45wh, p45wh1; p45wh.set(pts2.begin(), pts2.end());
2532 polygon_90_with_holes_data<int> p90wh, p90wh1; p90wh.set(pts.begin(), pts.end());
2533 assign(p, p90);
2534 assign(p, p45);
2535 assign(p1, p);
2536 //illegal: assign(p, p90wh);
2537 //illegal: assign(p, p45wh);
2538 //illegal: assign(p, pwh);
2539
2540 assign(p45, p90);
2541 assign(p451, p45);
2542 //illegal: assign(p45, p);
2543 //illegal: assign(p45, p90wh);
2544 //illegal: assign(p45, p45wh);
2545 //illegal: assign(p45, pwh);
2546
2547 assign(p901, p90);
2548 //illegal: assign(p90, p45);
2549 //illegal: assign(p90, p);
2550 //illegal: assign(p90, p90wh);
2551 //illegal: assign(p90, p45wh);
2552 //illegal: assign(p90, pwh);
2553
2554 assign(pwh, p90);
2555 assign(pwh, p45);
2556 assign(pwh, p);
2557 assign(pwh, p90wh);
2558 assign(pwh, p45wh);
2559 assign(pwh1, pwh);
2560
2561 assign(p45wh, p90);
2562 assign(p45wh, p45);
2563 //illegal: assign(p45wh, p);
2564 assign(p45wh, p90wh);
2565 assign(p45wh1, p45wh);
2566 //illegal: assign(p45wh, pwh);
2567
2568 assign(p90wh, p90);
2569 //illegal: assign(p90wh, p45);
2570 //illegal: assign(p90wh, p);
2571 assign(p90wh1, p90wh);
2572 //illegal: assign(p90wh, p45wh);
2573 //illegal: assign(p90wh, pwh);
2574 pts.clear();
2575 pts.push_back(point_data<int>(0, 0));
2576 pts.push_back(point_data<int>(3, 0));
2577 pts.push_back(point_data<int>(0, 1));
2578 p.set(pts.begin(), pts.end());
2579 std::cout << std::endl; std::cout << (area(p90));
2580 std::cout << std::endl; std::cout << (area(p45));
2581 std::cout << std::endl; std::cout << (area(p));
2582 std::cout << std::endl; std::cout << (area(p90wh));
2583 std::cout << std::endl; std::cout << (area(p45wh));
2584 std::cout << std::endl; std::cout << (area(pwh));
2585 std::cout << std::endl;
2586 point_data<int> pt(1, 1);
2587 std::cout << contains(p, pt) << std::endl;
2588 std::cout << contains(p90, pt) << std::endl;
2589
2590 interval_data<int> ivl = construct<interval_data<int> >(0, 10);
2591 std::cout << get(ivl, LOW) << std::endl;
2592 set(ivl, HIGH, 20);
2593
2594 std::cout << perimeter(p) << std::endl;
2595 if(winding(p) == LOW) std::cout << "LOW" << std::endl;
2596 if(winding(p) == HIGH) std::cout << "HIGH" << std::endl;
2597 rectangle_data<polygon_long_long_type> rd;
2598 std::cout << extents(rd, p) << std::endl;
2599 std::cout << rd << std::endl;
2600
2601 boolean_op::testBooleanOr<int>();
2602
2603 std::vector<rectangle_data<int> > rects1, rects2;
2604 rects2.push_back(rectangle_data<int>(0, 0, 10, 10));
2605 print_is_polygon_90_set_concept((polygon_90_set_data<int>()));
2606 print_is_mutable_polygon_90_set_concept((polygon_90_set_data<int>()));
2607 print_is_polygon_90_set_concept((polygon_90_data<int>()));
2608 print_is_polygon_90_set_concept((std::vector<polygon_90_data<int> >()));
2609 assign(rects1, rects2);
2610 polygon_90_set_data<int> ps90;
2611 assign(ps90, rects2);
2612 assign(rects2, ps90);
2613 assign(ps90, p90);
2614 assign(rects2, p90);
2615 std::cout << p90 << std::endl;
2616 for(unsigned int i = 0; i < rects2.size(); ++i) {
2617 std::cout << rects2[i] << std::endl;
2618 }
2619 bloat(rects2, 10);
2620 shrink(rects2[0], 10);
2621 for(unsigned int i = 0; i < rects2.size(); ++i) {
2622 std::cout << rects2[i] << std::endl;
2623 }
2624 move(rects2[0], HORIZONTAL, 30);
2625 assign(rects1, rects2 + p90);
2626 std::cout << "result of boolean or\n";
2627 for(unsigned int i = 0; i < rects1.size(); ++i) {
2628 std::cout << rects1[i] << std::endl;
2629 }
2630 rects1 -= p90;
2631 std::cout << "result of boolean not\n";
2632 for(unsigned int i = 0; i < rects1.size(); ++i) {
2633 std::cout << rects1[i] << std::endl;
2634 }
2635 rects1 += p90;
2636 std::cout << "result of boolean OR\n";
2637 for(unsigned int i = 0; i < rects1.size(); ++i) {
2638 std::cout << rects1[i] << std::endl;
2639 }
2640 rects1 *= p90;
2641 std::cout << "result of boolean AND\n";
2642 for(unsigned int i = 0; i < rects1.size(); ++i) {
2643 std::cout << rects1[i] << std::endl;
2644 }
2645 rects1 ^= rects2;
2646 std::cout << "result of boolean XOR\n";
2647 for(unsigned int i = 0; i < rects1.size(); ++i) {
2648 std::cout << rects1[i] << std::endl;
2649 }
2650 rects2.clear();
2651 get_max_rectangles(rects2, p90);
2652 std::cout << "result of max rectangles\n";
2653 for(unsigned int i = 0; i < rects2.size(); ++i) {
2654 std::cout << rects2[i] << std::endl;
2655 }
2656 rects2.clear();
2657 //operator += and -= don't support polygons, so + and - should not exist
2658 // rects2 += p90 + 6;
2659 // std::cout << "result of resize\n";
2660 // for(unsigned int i = 0; i < rects2.size(); ++i) {
2661 // std::cout << rects2[i] << std::endl;
2662 // }
2663 // std::cout << "result of resize\n";
2664 std::vector<polygon_90_with_holes_data<int> > polyswh1, polyswh2;
2665 // polyswh1 += p90 -2;
2666 // for(unsigned int i = 0; i < polyswh1.size(); ++i) {
2667 // std::cout << polyswh1[i] << std::endl;
2668 // }
2669 // std::cout << "result of resize\n";
2670 std::vector<polygon_90_data<int> > polys1, polys2;
2671 polys1 += p90;
2672 polys1 -= 2;
2673 // polys1 += p90 -2;
2674 for(unsigned int i = 0; i < polys1.size(); ++i) {
2675 std::cout << polys1[i] << std::endl;
2676 }
2677
2678 boolean_op_45<int>::testScan45(std::cout);
2679 polygon_45_formation<int>::testPolygon45Formation(std::cout);
2680 polygon_45_formation<int>::testPolygon45Tiling(std::cout);
2681
2682 axis_transformation atr;
2683 transform(p, atr);
2684 transform(p45, atr);
2685 transform(p90, atr);
2686 transform(pwh, atr);
2687 transform(p45wh, atr);
2688 transform(p90wh, atr);
2689 scale_up(p, 2);
2690 scale_up(p45, 2);
2691 scale_up(p90, 2);
2692 scale_up(pwh, 2);
2693 scale_up(p45wh, 2);
2694 scale_up(p90wh, 2);
2695 scale_down(p, 2);
2696 scale_down(p45, 2);
2697 scale_down(p90, 2);
2698 scale_down(pwh, 2);
2699 scale_down(p45wh, 2);
2700 scale_down(p90wh, 2);
2701 std::vector<polygon_45_data<int> > p45s1, p45s2;
2702 std::cout << equivalence(p45s1, p45s2) << std::endl;
2703 std::cout << equivalence(p45, p45wh) << std::endl;
2704 std::cout << equivalence(p90, p45wh) << std::endl;
2705 gtl::assign(p45s1, p90);
2706 p90 = polys1[0];
2707 move(p90, orientation_2d(HORIZONTAL), 8);
2708 std::cout << p90 << std::endl << p45wh << std::endl;
2709 polygon_45_set_data<int> ps45 = p90 + p45wh;
2710 assign(p45s1, ps45);
2711 std::cout << "result\n";
2712 for(unsigned int i = 0; i < p45s1.size(); ++i) {
2713 std::cout << p45s1[i] << std::endl;
2714 }
2715 std::cout << equivalence(p, pwh) << std::endl;
2716 std::cout << equivalence(p90, pwh) << std::endl;
2717 std::cout << equivalence(p45, pwh) << std::endl;
2718 std::cout << equivalence(pwh, pwh) << std::endl;
2719 p + pwh;
2720 p90 + pwh;
2721 p45 + pwh;
2722 std::cout << testRectangle() << std::endl;
2723 std::cout << testPolygon() << std::endl;
2724 std::cout << testPropertyMerge() << std::endl;
2725 std::cout << testPolygonAssign() << std::endl;
2726 std::cout << testPolygonWithHoles() << std::endl;
2727 std::cout << (polygon_arbitrary_formation<int>::testPolygonArbitraryFormationRect(std::cout)) << std::endl;
2728 std::cout << (polygon_arbitrary_formation<int>::testPolygonArbitraryFormationP1(std::cout)) << std::endl;
2729 std::cout << (polygon_arbitrary_formation<int>::testPolygonArbitraryFormationP2(std::cout)) << std::endl;
2730 std::cout << (polygon_arbitrary_formation<int>::testPolygonArbitraryFormationPolys(std::cout)) << std::endl;
2731 std::cout << (polygon_arbitrary_formation<int>::testPolygonArbitraryFormationSelfTouch1(std::cout)) << std::endl;
2732 std::cout << (polygon_arbitrary_formation<int>::testPolygonArbitraryFormationSelfTouch2(std::cout)) << std::endl;
2733 std::cout << (polygon_arbitrary_formation<int>::testPolygonArbitraryFormationSelfTouch3(std::cout)) << std::endl;
2734 std::cout << (polygon_arbitrary_formation<int>::testSegmentIntersection(std::cout)) << std::endl;
2735 std::cout << (property_merge<int, int>::test_insertion(std::cout)) << std::endl;
2736 std::cout << (line_intersection<int>::test_verify_scan(std::cout)) << std::endl;
2737 std::cout << (line_intersection<int>::test_validate_scan(std::cout)) << std::endl;
2738 std::cout << (scanline<int, int>::test_scanline(std::cout)) << std::endl;
2739 std::cout << (property_merge<int, int>::test_merge(std::cout)) << std::endl;
2740 std::cout << (property_merge<int, int>::test_intersection(std::cout)) << std::endl;
2741 std::cout << (polygon_arbitrary_formation<int>::testPolygonArbitraryFormationColinear(std::cout)) << std::endl;
2742 std::cout << (property_merge<int, int>::test_manhattan_intersection(std::cout)) << std::endl;
2743 std::cout << (test_arbitrary_boolean_op<int>(std::cout)) << std::endl;
2744 }
2745 {
2746 polygon_set_data<int> psd;
2747 rectangle_data<int> rect;
2748 set_points(rect, point_data<int>(0, 0), point_data<int>(10, 10));
2749 psd.insert(rect);
2750 polygon_set_data<int> psd2;
2751 set_points(rect, point_data<int>(5, 5), point_data<int>(15, 15));
2752 psd2.insert(rect);
2753 std::vector<polygon_data<int> > pv;
2754 polygon_set_data<int> psd3;
2755 psd3 = psd + psd2;
2756 psd3.get(pv);
2757 for(unsigned int i = 0; i < pv.size(); ++i) {
2758 std::cout << pv[i] << std::endl;
2759 }
2760 psd += psd2;
2761 pv.clear();
2762 psd3.get(pv);
2763 for(unsigned int i = 0; i < pv.size(); ++i) {
2764 std::cout << pv[i] << std::endl;
2765 }
2766 }
2767 {
2768 polygon_90_set_data<int> psd;
2769 rectangle_data<int> rect;
2770 set_points(rect, point_data<int>(0, 0), point_data<int>(10, 10));
2771 psd.insert(rect);
2772 polygon_90_set_data<int> psd2;
2773 set_points(rect, point_data<int>(5, 5), point_data<int>(15, 15));
2774 psd2.insert(rect);
2775 std::vector<polygon_90_data<int> > pv;
2776 interact(psd, psd2);
2777 assign(pv, psd);
2778 for(unsigned int i = 0; i < pv.size(); ++i) {
2779 std::cout << pv[i] << std::endl;
2780 }
2781
2782 connectivity_extraction_90<int> ce;
2783 ce.insert(pv[0]);
2784 ce.insert(psd2);
2785 std::vector<std::set<int> > graph(2);
2786 ce.extract(graph);
2787 if(graph[0].size() == 1) std::cout << "connectivity extraction is alive\n";
2788
2789 //std::vector<rectangle_data<polygon_long_long_type> > lobs;
2790 //get_max_rectangles(lobs, psd);
2791 //if(lobs.size() == 1) std::cout << "max rectangles is alive\n";
2792
2793 std::vector<rectangle_data<int> > rv;
2794 rv.push_back(rect);
2795 set_points(rect, point_data<int>(0, 0), point_data<int>(10, 10));
2796 rv.push_back(rect);
2797 self_intersect(rv);
2798 if(rv.size() == 1) {
2799 assign(rect, rv.back());
2800 std::cout << rect << std::endl;
2801 }
2802
2803 assign(rv, rv + 1);
2804 std::cout << rv.size() << std::endl;
2805 if(rv.size() == 1) {
2806 assign(rect, rv.back());
2807 std::cout << rect << std::endl;
2808 }
2809 assign(rv, rv - 1);
2810 if(rv.size() == 1) {
2811 assign(rect, rv.back());
2812 std::cout << rect << std::endl;
2813 }
2814 rv += 1;
2815 if(rv.size() == 1) {
2816 assign(rect, rv.back());
2817 std::cout << rect << std::endl;
2818 }
2819 rv -= 1;
2820 if(rv.size() == 1) {
2821 assign(rect, rv.back());
2822 std::cout << rect << std::endl;
2823 }
2824 rv.clear();
2825 set_points(rect, point_data<int>(0, 0), point_data<int>(10, 10));
2826 rv.push_back(rect);
2827 set_points(rect, point_data<int>(12, 12), point_data<int>(20, 20));
2828 rv.push_back(rect);
2829 grow_and(rv, 7);
2830 if(rv.size() == 1) {
2831 assign(rect, rv.back());
2832 std::cout << rect << std::endl;
2833 }
2834 std::cout << area(rv) << std::endl;
2835 std::cout << area(rv) << std::endl;
2836
2837 scale_up(rv, 10);
2838 std::cout << area(rv) << std::endl;
2839 scale_down(rv, 7);
2840 std::cout << area(rv) << std::endl;
2841 if(rv.size() == 1) {
2842 assign(rect, rv.back());
2843 std::cout << rect << std::endl;
2844 }
2845 keep(rv, 290, 300, 7, 24, 7, 24);
2846 if(rv.size() == 1) {
2847 assign(rect, rv.back());
2848 std::cout << rect << std::endl;
2849 }
2850 keep(rv, 300, 310, 7, 24, 7, 24);
2851 if(rv.empty()) std::cout << "keep is alive\n";
2852 }
2853 {
2854 // typedef int Unit;
2855 // typedef point_data<int> Point;
2856 // typedef interval_data<int> Interval;
2857 // typedef rectangle_data<int> Rectangle;
2858 // typedef polygon_90_data<int> Polygon;
2859 // typedef polygon_90_with_holes_data<int> PolygonWithHoles;
2860 // typedef polygon_45_data<int> Polygon45;
2861 // typedef polygon_45_with_holes_data<int> Polygon45WithHoles;
2862 // typedef polygon_90_set_data<int> PolygonSet;
2863 // //typedef polygon_45_set_data<int> Polygon45Set;
2864 // typedef axis_transformation AxisTransform;
2865 // typedef transformation<int> Transform;
2866 //test polygon45 area, polygon45 with holes area
2867 std::vector<Point> pts;
2868 pts.clear();
2869 pts.push_back(Point(10, 10));
2870 pts.push_back(Point(15, 10));
2871 pts.push_back(Point(10, 15));
2872 Polygon45 polyHole;
2873 polyHole.set(pts.begin(), pts.end());
2874 pts.clear();
2875 pts.push_back(Point(10, 0));
2876 pts.push_back(Point(20, 10));
2877 pts.push_back(Point(20, 30));
2878 pts.push_back(Point(0, 50));
2879 pts.push_back(Point(0, 10));
2880 Polygon45WithHoles polyWHoles;
2881 polyWHoles.set(pts.begin(), pts.end());
2882 polyWHoles.set_holes(&polyHole, (&polyHole)+1);
2883 std::cout << polyWHoles << std::endl;
2884 std::cout << area(polyWHoles) << std::endl;
2885 std::cout << area(polyWHoles) << std::endl;
2886 //test polygon45, polygon45with holes transform
2887 AxisTransform atr(AxisTransform::EAST_SOUTH);
2888 Polygon45WithHoles p45wh(polyWHoles);
2889 transform(polyWHoles, atr);
2890 std::cout << polyWHoles << std::endl;
2891 Transform tr(atr);
2892 tr.invert();
2893 transform(polyWHoles, tr);
2894 std::cout << polyWHoles << std::endl;
2895 if(area(polyWHoles) != 687.5) return 1;
2896 //test polygon, polygon with holes transform
2897 Polygon ph;
2898 assign(ph, Rectangle(10, 10, 20, 20));
2899 PolygonWithHoles pwh;
2900 assign(pwh, Rectangle(0, 0, 100, 100));
2901 pwh.set_holes(&ph, (&ph)+1);
2902 std::cout << area(pwh) << std::endl;
2903 transform(pwh, atr);
2904 std::cout << pwh << std::endl;
2905 std::cout << area(pwh) << std::endl;
2906 transform(pwh, tr);
2907 std::cout << pwh << std::endl;
2908 std::cout << area(pwh) << std::endl;
2909 if(area(pwh) != 9900) return 1;
2910
2911 //test point scale up / down
2912 Point pt(10, 10);
2913 scale_up(pt, 25);
2914 if(pt != Point(250, 250)) return 1;
2915 std::cout << pt << std::endl;
2916 scale_down(pt, 25);
2917 if(pt != Point(10, 10)) return 1;
2918 std::cout << pt << std::endl;
2919 scale_down(pt, 25);
2920 if(pt != Point(0, 0)) return 1;
2921 std::cout << pt << std::endl;
2922
2923 //test polygon, polygon with holes scale up down
2924 PolygonWithHoles tmpPwh(pwh);
2925 scale_up(pwh, 25);
2926 std::cout << pwh << std::endl;
2927 scale_down(pwh, 25);
2928 if(area(pwh) != area(tmpPwh)) return 1;
2929 std::cout << pwh << std::endl;
2930 scale_down(pwh, 25);
2931 std::cout << pwh << std::endl;
2932 //test polygon45, polygon45 with holes is45
2933 std::cout << is_45(polyHole) << std::endl;
2934 if(is_45(polyHole) != true) return 1;
2935 pts.clear();
2936 pts.push_back(Point(10, 10));
2937 pts.push_back(Point(15, 10));
2938 pts.push_back(Point(10, 16));
2939 polyHole.set(pts.begin(), pts.end());
2940 std::cout << is_45(polyHole) << std::endl;
2941 if(is_45(polyHole) != false) return 1;
2942 //test polygon45, polygon45 with holes snap 45
2943 snap_to_45(polyHole);
2944 std::cout << is_45(polyHole) << std::endl;
2945 if(is_45(polyHole) != true) return 1;
2946 std::cout << polyHole << std::endl;
2947 //test polygon45, polygon45 with holes scalue up down
2948 scale_up(polyHole, 10000);
2949 std::cout << polyHole << std::endl;
2950 scale_down(polyHole, 3);
2951 std::cout << is_45(polyHole) << " " << polyHole << std::endl;
2952 if(is_45(polyHole) != true) return 1;
2953 scale_down(polyHole, 5);
2954 std::cout << is_45(polyHole) << " " << polyHole << std::endl;
2955 if(is_45(polyHole) != true) return 1;
2956 scale_down(polyHole, 7);
2957 std::cout << is_45(polyHole) << " " << polyHole << std::endl;
2958 if(is_45(polyHole) != true) return 1;
2959 scale_down(polyHole, 13);
2960 std::cout << is_45(polyHole) << " " << polyHole << std::endl;
2961 if(is_45(polyHole) != true) return 1;
2962 scale_down(polyHole, 2);
2963 std::cout << is_45(polyHole) << " " << polyHole << std::endl;
2964 if(is_45(polyHole) != true) return 1;
2965 scale_down(polyHole, 2);
2966 std::cout << is_45(polyHole) << " " << polyHole << std::endl;
2967 if(is_45(polyHole) != true) return 1;
2968 scale_down(polyHole, 2);
2969 std::cout << is_45(polyHole) << " " << polyHole << std::endl;
2970 if(is_45(polyHole) != true) return 1;
2971 scale_down(polyHole, 2);
2972 std::cout << is_45(polyHole) << " " << polyHole << std::endl;
2973 if(is_45(polyHole) != true) return 1;
2974 scale_down(polyHole, 2);
2975 std::cout << is_45(polyHole) << " " << polyHole << std::endl;
2976 if(is_45(polyHole) != true) return 1;
2977 scale_up(polyHole, 3);
2978 std::cout << is_45(polyHole) << " " << polyHole << std::endl;
2979 if(is_45(polyHole) != true) return 1;
2980 scale_down(polyHole, 2);
2981 std::cout << is_45(polyHole) << " " << polyHole << std::endl;
2982 if(is_45(polyHole) != true) return 1;
2983 scale_down(polyHole, 2);
2984 std::cout << is_45(polyHole) << " " << polyHole << std::endl;
2985 if(is_45(polyHole) != true) return 1;
2986 scale_down(polyHole, 2);
2987 std::cout << is_45(polyHole) << " " << polyHole << std::endl;
2988 if(is_45(polyHole) != true) return 1;
2989 scale_down(polyHole, 2);
2990 std::cout << is_45(polyHole) << " " << polyHole << std::endl;
2991 if(is_45(polyHole) != true) return 1;
2992 pts.clear();
2993 pts.push_back(Point(11, 1));
2994 pts.push_back(Point(21, 11));
2995 pts.push_back(Point(11, 21));
2996 pts.push_back(Point(1, 11));
2997 polyHole.set(pts.begin(), pts.end());
2998 std::cout << is_45(polyHole) << " " << polyHole << std::endl;
2999 if(is_45(polyHole) != true) return 1;
3000 scale_down(polyHole, 3);
3001 std::cout << is_45(polyHole) << " " << polyHole << std::endl;
3002 if(is_45(polyHole) != true) return 1;
3003 scale_up(polyHole, 10000);
3004 std::cout << polyHole << std::endl;
3005 scale_down(polyHole, 3);
3006 std::cout << is_45(polyHole) << " " << polyHole << std::endl;
3007 if(is_45(polyHole) != true) return 1;
3008 scale_down(polyHole, 5);
3009 std::cout << is_45(polyHole) << " " << polyHole << std::endl;
3010 if(is_45(polyHole) != true) return 1;
3011 scale_down(polyHole, 7);
3012 std::cout << is_45(polyHole) << " " << polyHole << std::endl;
3013 if(is_45(polyHole) != true) return 1;
3014 scale_down(polyHole, 13);
3015 std::cout << is_45(polyHole) << " " << polyHole << std::endl;
3016 if(is_45(polyHole) != true) return 1;
3017 scale_down(polyHole, 2);
3018 std::cout << is_45(polyHole) << " " << polyHole << std::endl;
3019 if(is_45(polyHole) != true) return 1;
3020 scale_down(polyHole, 2);
3021 std::cout << is_45(polyHole) << " " << polyHole << std::endl;
3022 if(is_45(polyHole) != true) return 1;
3023 scale_down(polyHole, 2);
3024 std::cout << is_45(polyHole) << " " << polyHole << std::endl;
3025 if(is_45(polyHole) != true) return 1;
3026 scale_down(polyHole, 2);
3027 std::cout << is_45(polyHole) << " " << polyHole << std::endl;
3028 if(is_45(polyHole) != true) return 1;
3029 scale_down(polyHole, 2);
3030 std::cout << is_45(polyHole) << " " << polyHole << std::endl;
3031 if(is_45(polyHole) != true) return 1;
3032 scale_up(polyHole, 3);
3033 std::cout << is_45(polyHole) << " " << polyHole << std::endl;
3034 if(is_45(polyHole) != true) return 1;
3035 scale_down(polyHole, 2);
3036 std::cout << is_45(polyHole) << " " << polyHole << std::endl;
3037 if(is_45(polyHole) != true) return 1;
3038 scale_down(polyHole, 2);
3039 std::cout << is_45(polyHole) << " " << polyHole << std::endl;
3040 if(is_45(polyHole) != true) return 1;
3041 scale_down(polyHole, 2);
3042 std::cout << is_45(polyHole) << " " << polyHole << std::endl;
3043 if(is_45(polyHole) != true) return 1;
3044 scale_down(polyHole, 2);
3045 std::cout << is_45(polyHole) << " " << polyHole << std::endl;
3046 if(is_45(polyHole) != true) return 1;
3047
3048 std::cout << is_45(polyWHoles) << " " << polyWHoles << std::endl;
3049 if(is_45(polyWHoles) != true) return 1;
3050 scale_up(polyWHoles, 100013);
3051 std::cout << polyWHoles << std::endl;
3052 scale_down(polyWHoles, 3);
3053 std::cout << is_45(polyWHoles) << " " << polyWHoles << std::endl;
3054 if(is_45(polyWHoles) != true) return 1;
3055 scale_down(polyWHoles, 2);
3056 std::cout << is_45(polyWHoles) << " " << polyWHoles << std::endl;
3057 if(is_45(polyWHoles) != true) return 1;
3058 scale_down(polyWHoles, 3);
3059 std::cout << is_45(polyWHoles) << " " << polyWHoles << std::endl;
3060 if(is_45(polyWHoles) != true) return 1;
3061 scale_down(polyWHoles, 2);
3062 std::cout << is_45(polyWHoles) << " " << polyWHoles << std::endl;
3063 if(is_45(polyWHoles) != true) return 1;
3064 scale_down(polyWHoles, 3);
3065 std::cout << is_45(polyWHoles) << " " << polyWHoles << std::endl;
3066 if(is_45(polyWHoles) != true) return 1;
3067 scale_down(polyWHoles, 2);
3068 std::cout << is_45(polyWHoles) << " " << polyWHoles << std::endl;
3069 if(is_45(polyWHoles) != true) return 1;
3070 scale_down(polyWHoles, 3);
3071 std::cout << is_45(polyWHoles) << " " << polyWHoles << std::endl;
3072 if(is_45(polyWHoles) != true) return 1;
3073 scale_down(polyWHoles, 2);
3074 std::cout << is_45(polyWHoles) << " " << polyWHoles << std::endl;
3075 if(is_45(polyWHoles) != true) return 1;
3076 scale_down(polyWHoles, 3);
3077 std::cout << is_45(polyWHoles) << " " << polyWHoles << std::endl;
3078 if(is_45(polyWHoles) != true) return 1;
3079 scale_down(polyWHoles, 2);
3080 std::cout << is_45(polyWHoles) << " " << polyWHoles << std::endl;
3081 if(is_45(polyWHoles) != true) return 1;
3082 scale_down(polyWHoles, 3);
3083 std::cout << is_45(polyWHoles) << " " << polyWHoles << std::endl;
3084 if(is_45(polyWHoles) != true) return 1;
3085 scale_down(polyWHoles, 3);
3086 std::cout << is_45(polyWHoles) << " " << polyWHoles << std::endl;
3087 if(is_45(polyWHoles) != true) return 1;
3088 scale_down(polyWHoles, 2);
3089 std::cout << is_45(polyWHoles) << " " << polyWHoles << std::endl;
3090 if(is_45(polyWHoles) != true) return 1;
3091 scale_down(polyWHoles, 3);
3092 std::cout << is_45(polyWHoles) << " " << polyWHoles << std::endl;
3093 if(is_45(polyWHoles) != true) return 1;
3094 scale_down(polyWHoles, 2);
3095 std::cout << is_45(polyWHoles) << " " << polyWHoles << std::endl;
3096 if(is_45(polyWHoles) != true) return 1;
3097 scale_down(polyWHoles, 3);
3098 std::cout << is_45(polyWHoles) << " " << polyWHoles << std::endl;
3099 if(is_45(polyWHoles) != true) return 1;
3100 scale_down(polyWHoles, 2);
3101 std::cout << is_45(polyWHoles) << " " << polyWHoles << std::endl;
3102 if(is_45(polyWHoles) != true) return 1;
3103
3104 std::cout << (boolean_op_45<Unit>::testScan45(std::cout)) << std::endl;
3105 std::cout << (polygon_45_formation<Unit>::testPolygon45Formation(std::cout)) << std::endl;
3106 std::cout << (polygon_45_formation<Unit>::testPolygon45Tiling(std::cout)) << std::endl;
3107
3108
3109 {
3110 PolygonSet ps;
3111 Rectangle rect;
3112 ps.insert(Rectangle(0, 0, 10, 10));
3113 std::cout << area(ps) << std::endl;
3114 if(area(ps) != 100) return 1;
3115 scale_up(ps, 3);
3116 std::cout << area(ps) << std::endl;
3117 if(area(ps) != 900) return 1;
3118 scale_down(ps, 2);
3119 std::cout << area(ps) << std::endl;
3120 if(area(ps) != 225) return 1;
3121 transform(ps, atr);
3122 std::vector<Rectangle> rv;
3123 rv.clear();
3124 ps.get(rv);
3125 if(rv.size() == 1) {
3126 assign(rect, rv.back());
3127 std::cout << rect << std::endl;
3128 }
3129 transform(ps, tr);
3130 rv.clear();
3131 ps.get(rv);
3132 if(rv.size() == 1) {
3133 assign(rect, rv.back());
3134 std::cout << rect << std::endl;
3135 }
3136 }
3137 //test polygon45set transform
3138 pts.clear();
3139 pts.push_back(Point(10, 10));
3140 pts.push_back(Point(15, 10));
3141 pts.push_back(Point(10, 15));
3142 polyHole.set(pts.begin(), pts.end());
3143 Polygon45Set ps451, ps452;
3144 ps451.insert(polyHole);
3145 ps452 = ps451;
3146 std::cout << (ps451 == ps452) << std::endl;
3147 if(ps451 != ps452) return 1;
3148 ps451.transform(atr);
3149 std::cout << (ps451 == ps452) << std::endl;
3150 if(ps451 == ps452) return 1;
3151 ps451.transform(tr);
3152 std::cout << (ps451 == ps452) << std::endl;
3153 if(ps451 != ps452) return 1;
3154
3155 //test polygon45set area
3156 std::cout << area(ps451) << std::endl;
3157 if(area(ps451) != 12.5) return 1;
3158 //test polygon45set scale up down
3159 ps451.scale_up(3);
3160 std::cout << area(ps451) << std::endl;
3161 if(area(ps451) != 112.5) return 1;
3162 ps451.scale_down(2);
3163 std::cout << area(ps451) << std::endl;
3164 if(area(ps451) != 32) return 1;
3165 //test polygonset scalue up down
3166 }
3167 {
3168 std::cout << (testPolygon45SetRect()) << std::endl;
3169 testPolygon45SetPerterbation(); //re-enable after non-intersection fix
3170 testPolygon45Set();
3171 testPolygon45SetDORA(); //re-enable after non-intersection fix
3172 polygon_45_set_data<int> ps45_1, ps45_2, ps45_3;
3173 ps45_1.insert(rectangle_data<int>(0, 0, 10, 10));
3174 ps45_2.insert(rectangle_data<int>(5, 5, 15, 15));
3175 std::vector<polygon_45_data<int> > p45s;
3176 ps45_3 = ps45_1 | ps45_2;
3177 ps45_3.get(p45s);
3178 if(p45s.size()) std::cout << p45s[0] << std::endl;
3179 else {
3180 std::cout << "test failed\n";
3181 return 1;
3182 }
3183 p45s.clear();
3184 ps45_3 = ps45_1 + ps45_2;
3185 ps45_3.get(p45s);
3186 if(p45s.size()) std::cout << p45s[0] << std::endl;
3187 else {
3188 std::cout << "test failed\n";
3189 return 1;
3190 }
3191 p45s.clear();
3192 ps45_3 = ps45_1 * ps45_2;
3193 ps45_3.get(p45s);
3194 if(p45s.size()) std::cout << p45s[0] << std::endl;
3195 else {
3196 std::cout << "test failed\n";
3197 return 1;
3198 }
3199 p45s.clear();
3200 ps45_3 = ps45_1 - ps45_2;
3201 ps45_3.get(p45s);
3202 if(p45s.size()) std::cout << p45s[0] << std::endl;
3203 else {
3204 std::cout << "test failed\n";
3205 return 1;
3206 }
3207 p45s.clear();
3208 ps45_3 = ps45_1 ^ ps45_2;
3209 ps45_3.get(p45s);
3210 if(p45s.size() == 2) std::cout << p45s[0] << " " << p45s[1] << std::endl;
3211 else {
3212 std::cout << "test failed\n";
3213 return 1;
3214 }
3215 std::vector<point_data<int> > pts;
3216 pts.clear();
3217 pts.push_back(point_data<int>(7, 0));
3218 pts.push_back(point_data<int>(20, 13));
3219 pts.push_back(point_data<int>(0, 13));
3220 pts.push_back(point_data<int>(0, 0));
3221 polygon_45_data<int> p45_1(pts.begin(), pts.end());
3222 ps45_3.clear();
3223 ps45_3.insert(p45_1);
3224 p45s.clear();
3225 ps45_3.get(p45s);
3226 if(p45s.size()) std::cout << p45s[0] << std::endl;
3227 else {
3228 std::cout << "test failed\n";
3229 return 1;
3230 }
3231 ps45_3 += 1;
3232 p45s.clear();
3233 ps45_3.get(p45s);
3234 if(p45s.size()) std::cout << p45s[0] << std::endl;
3235 else {
3236 std::cout << "test failed\n";
3237 return 1;
3238 }
3239 ps45_3 -= 1;
3240 p45s.clear();
3241 ps45_3.get(p45s);
3242 if(p45s.size()) std::cout << p45s[0] << std::endl;
3243 else {
3244 std::cout << "test failed\n";
3245 return 1;
3246 }
3247 }
3248 {
3249 polygon_90_set_data<int> p90sd;
3250 p90sd.insert(rectangle_data<int>(0, 0, 10, 10));
3251 std::vector<rectangle_data<int> > rects;
3252 std::vector<polygon_90_data<int> > polys90;
3253 std::vector<polygon_90_with_holes_data<int> > pwhs90;
3254 assign(rects, p90sd);
3255 assign(polys90, p90sd);
3256 assign(pwhs90, p90sd);
3257 std::cout << equivalence(rects, polys90) << std::endl;
3258 std::cout << equivalence(pwhs90, polys90) << std::endl;
3259 pwhs90.clear();
3260 assign(pwhs90, polys90);
3261 std::cout << equivalence(pwhs90, polys90) << std::endl;
3262 }
3263 {
3264 polygon_45_set_data<int> p45sd;
3265 p45sd.insert(rectangle_data<int>(0, 0, 10, 10));
3266 std::vector<rectangle_data<int> > rects;
3267 std::vector<polygon_45_data<int> > polys45;
3268 std::vector<polygon_45_with_holes_data<int> > pwhs45;
3269 get_trapezoids(polys45, p45sd);
3270 assign(polys45, p45sd);
3271 assign(pwhs45, p45sd);
3272 std::cout << equivalence(pwhs45, polys45) << std::endl;
3273 pwhs45.clear();
3274 assign(pwhs45, polys45);
3275 std::cout << equivalence(pwhs45, polys45) << std::endl;
3276 }
3277 {
3278 polygon_set_data<int> psd;
3279 psd.insert(rectangle_data<int>(0, 0, 10, 10));
3280 std::vector<polygon_data<int> > polys;
3281 std::vector<polygon_with_holes_data<int> > pwhs;
3282 assign(polys, psd);
3283 assign(pwhs, psd);
3284 std::cout << equivalence(pwhs, polys) << std::endl;
3285 pwhs.clear();
3286 assign(pwhs, polys);
3287 std::cout << equivalence(pwhs, polys) << std::endl;
3288 }
3289 {
3290 polygon_90_set_data<int> ps1(HORIZONTAL), ps2(VERTICAL);
3291 ps1 += rectangle_data<int>(0, 0, 10, 120);
3292 assign(ps1, ps2);
3293 std::cout << equivalence(ps1, ps2) << std::endl;
3294 }
3295 {
3296 std::vector<rectangle_data<polygon_long_long_type> > lobs, input;
3297 input.push_back(rectangle_data<polygon_long_long_type>(0, 0, 10, 10));
3298 input.push_back(rectangle_data<polygon_long_long_type>(10, 5, 15, 15));
3299 get_max_rectangles(lobs, input);
3300 if(lobs.size() == 3) std::cout << "max rectangles is correct\n";
3301 }
3302 {
3303 polygon_set_data<int> ps1, ps2, ps3;
3304 ps1.insert(rectangle_data<int>(0, 0, 10, 10));
3305 ps2.insert(rectangle_data<int>(0, 0, 15, 5));
3306 ps3.insert(rectangle_data<int>(0, 0, 20, 2));
3307 std::cout << area(ps1 + ps2) << std::endl;
3308 keep(ps1, 0, 100, 0, 100, 0, 100);
3309 if(empty(ps1)) return 1;
3310 rectangle_data<int> bbox;
3311 extents(bbox, ps1);
3312 std::cout << bbox << std::endl;
3313 //resize(ps1, 1);
3314 //shrink(ps1, 1);
3315 //bloat(ps1, 1);
3316 scale_up(ps1, 2);
3317 scale_down(ps1, 2);
3318 axis_transformation atr;
3319 transform(ps1, atr);
3320 std::cout << area(ps1) << std::endl;
3321 if(area(ps1) != 100) return 1;
3322 clear(ps1);
3323 if(!empty(ps1)) return 1;
3324 ps1 = ps2 * ps3;
3325 ps1 *= ps2;
3326 ps1 - ps2;
3327 ps1 -= ps2;
3328 ps1 ^ ps2;
3329 ps1 ^= ps2;
3330 ps1 | ps2;
3331 ps1 |= ps2;
3332 }
3333 {
3334 polygon_45_set_data<int> ps45_1, ps45_2;
3335 ps45_1.insert(rectangle_data<int>(0, 0, 10, 10));
3336 keep(ps45_1, 0, 1000, 0, 1000, 0, 1000);
3337 std::cout << area(ps45_1) << std::endl;
3338 std::cout << empty(ps45_1) << std::endl;
3339 rectangle_data<int> bbox;
3340 extents(bbox, ps45_1);
3341 std::cout << bbox << std::endl;
3342 resize(ps45_1, 1);
3343 shrink(ps45_1, 1);
3344 bloat(ps45_1, 1);
3345 scale_up(ps45_1, 2);
3346 scale_down(ps45_1, 2);
3347 axis_transformation atr;
3348 transform(ps45_1, atr);
3349 std::cout << area(ps45_1) << std::endl;
3350 if(area(ps45_1) != 144) return 1;
3351 clear(ps45_1);
3352 if(!empty(ps45_1)) return 1;
3353 }
3354 {
3355 std::vector<polygon_45_data<int> > p45v;
3356 p45v + p45v;
3357 p45v *= p45v;
3358 p45v += p45v;
3359 p45v - p45v;
3360 p45v -= p45v;
3361 p45v ^ p45v;
3362 p45v ^= p45v;
3363 p45v | p45v;
3364 p45v |= p45v;
3365 p45v + 1;
3366 p45v += 1;
3367 p45v - 1;
3368 p45v -= 1;
3369 p45v + (p45v + p45v);
3370 }
3371 {
3372 polygon_45_set_data<int> ps45;
3373 polygon_90_set_data<int> ps90;
3374 std::vector<polygon_90_with_holes_data<int> > p90whv;
3375 ps45.insert(ps90);
3376 ps45.insert(p90whv);
3377 ps45.insert(p90whv + p90whv);
3378
3379 ps45.insert(polygon_90_with_holes_data<int>());
3380 polygon_with_holes_data<int> pwh;
3381 snap_to_45(pwh);
3382 }
3383 {
3384 polygon_90_set_data<int> ps90_1, ps90_2;
3385 ps90_1.insert(rectangle_data<int>(0, 0, 10, 10));
3386 keep(ps90_1, 0, 1000, 0, 1000, 0, 1000);
3387 std::cout << area(ps90_1) << std::endl;
3388 std::cout << empty(ps90_1) << std::endl;
3389 rectangle_data<int> bbox;
3390 extents(bbox, ps90_1);
3391 std::cout << bbox << std::endl;
3392 resize(ps90_1, 1);
3393 shrink(ps90_1, 1);
3394 bloat(ps90_1, 1);
3395 scale_up(ps90_1, 2);
3396 scale_down(ps90_1, 2);
3397 scale(ps90_1, anisotropic_scale_factor<double>(2, 2));
3398 scale(ps90_1, anisotropic_scale_factor<double>(0.5, 0.5));
3399 axis_transformation atr;
3400 transform(ps90_1, atr);
3401 std::cout << area(ps90_1) << std::endl;
3402 if(area(ps90_1) != 144) return 1;
3403 clear(ps90_1);
3404 if(!empty(ps90_1)) return 1;
3405 }
3406 if(!nonInteger45StessTest()) return 1;
3407 {
3408 using namespace gtl;
3409 typedef polygon_45_property_merge<int, int> p45pm;
3410 p45pm::MergeSetData msd;
3411 polygon_45_set_data<int> ps;
3412 ps += rectangle_data<int>(0, 0, 10, 10);
3413 p45pm::populateMergeSetData(msd, ps.begin(), ps.end(), 444);
3414 ps.clear();
3415 ps += rectangle_data<int>(5, 5, 15, 15);
3416 p45pm::populateMergeSetData(msd, ps.begin(), ps.end(), 333);
3417 std::map<std::set<int>, polygon_45_set_data<int> > result;
3418 p45pm::performMerge(result, msd);
3419 int i = 0;
3420 for(std::map<std::set<int>, polygon_45_set_data<int> >::iterator itr = result.begin();
3421 itr != result.end(); ++itr) {
3422 for(std::set<int>::const_iterator itr2 = (*itr).first.begin();
3423 itr2 != (*itr).first.end(); ++itr2) {
3424 std::cout << *itr2 << " ";
3425 } std::cout << " : ";
3426 std::cout << area((*itr).second) << std::endl;
3427 if(i == 1) {
3428 if(area((*itr).second) != 100) return 1;
3429 } else
3430 if(area((*itr).second) != 300) return 1;
3431 ++i;
3432 }
3433
3434
3435 property_merge_45<int, int> pm;
3436 pm.insert(rectangle_data<int>(0, 0, 10, 10), 444);
3437 pm.insert(rectangle_data<int>(5, 5, 15, 15), 333);
3438 std::map<std::set<int>, polygon_45_set_data<int> > mp;
3439 pm.merge(mp);
3440 i = 0;
3441 for(std::map<std::set<int>, polygon_45_set_data<int> >::iterator itr = mp.begin();
3442 itr != mp.end(); ++itr) {
3443 for(std::set<int>::const_iterator itr2 = (*itr).first.begin();
3444 itr2 != (*itr).first.end(); ++itr2) {
3445 std::cout << *itr2 << " ";
3446 } std::cout << " : ";
3447 std::cout << area((*itr).second) << std::endl;
3448 if(i == 1) {
3449 if(area((*itr).second) != 25) return 1;
3450 } else
3451 if(area((*itr).second) != 75) return 1;
3452 ++i;
3453 }
3454 std::map<std::vector<int>, polygon_45_set_data<int> > mp2;
3455 pm.merge(mp2);
3456 i = 0;
3457 for(std::map<std::vector<int>, polygon_45_set_data<int> >::iterator itr = mp2.begin();
3458 itr != mp2.end(); ++itr) {
3459 for(std::vector<int>::const_iterator itr2 = (*itr).first.begin();
3460 itr2 != (*itr).first.end(); ++itr2) {
3461 std::cout << *itr2 << " ";
3462 } std::cout << " : ";
3463 std::cout << area((*itr).second) << std::endl;
3464 if(i == 1) {
3465 if(area((*itr).second) != 25) return 1;
3466 } else
3467 if(area((*itr).second) != 75) return 1;
3468 ++i;
3469 }
3470 }
3471 {
3472 std::cout << trapezoid_arbitrary_formation<int>::testTrapezoidArbitraryFormationRect(std::cout) << std::endl;
3473 std::cout << trapezoid_arbitrary_formation<int>::testTrapezoidArbitraryFormationP1(std::cout) << std::endl;
3474 std::cout << trapezoid_arbitrary_formation<int>::testTrapezoidArbitraryFormationP2(std::cout) << std::endl;
3475 std::cout << trapezoid_arbitrary_formation<int>::testTrapezoidArbitraryFormationPolys(std::cout) << std::endl;
3476 std::cout << polygon_arbitrary_formation<int>::testPolygonArbitraryFormationSelfTouch1(std::cout) << std::endl;
3477 std::cout << trapezoid_arbitrary_formation<int>::testTrapezoidArbitraryFormationSelfTouch1(std::cout) << std::endl;
3478 typedef rectangle_data<int> Rectangle;
3479 polygon_set_data<int> ps;
3480 ps += Rectangle(0, 1, 10, 11);
3481 ps += Rectangle(5, 6, 15, 16);
3482 std::vector<polygon_data<int> > polys;
3483 ps.get_trapezoids(polys);
3484 for(unsigned int i = 0; i < polys.size(); ++i) {
3485 std::cout << polys[i] << std::endl;
3486 }
3487 ps.transform(axis_transformation(axis_transformation::FLIP_X));
3488 polys.clear();
3489 ps.get_trapezoids(polys);
3490 for(unsigned int i = 0; i < polys.size(); ++i) {
3491 std::cout << polys[i] << std::endl;
3492 }
3493 polys.clear();
3494 ps.get_trapezoids(polys, HORIZONTAL);
3495 for(unsigned int i = 0; i < polys.size(); ++i) {
3496 std::cout << polys[i] << std::endl;
3497 }
3498 }
3499
3500 if(!test_aa_touch()) {
3501 std::cout << "test_aa_touch failed\n";
3502 return 1;
3503 }
3504 if(!test_aa_touch_ur()) {
3505 std::cout << "test_aa_touch_ur failed\n";
3506 return 1;
3507 }
3508 if(!test_aa_touch_ur()) {
3509 std::cout << "test_aa_touch_ur failed\n";
3510 return 1;
3511 }
3512 if(!test_aa_touch_r()) {
3513 std::cout << "test_aa_touch_r failed\n";
3514 return 1;
3515 }
3516 if(!test_aa_touch_boundaries()) {
3517 std::cout << "test_aa_touch_boundaries failed\n";
3518 return 1;
3519 }
3520 if(!test_aa_concept_interact()) {
3521 std::cout << "test_aa_concept_interact failed\n";
3522 return 1;
3523 }
3524
3525 {
3526 polygon_set_data<int> ps;
3527 polygon_90_set_data<int> ps90;
3528 rectangle_data<int> rect(0, 1, 10, 100);
3529 std::vector<polygon_data<int> > rupolys, rupolys45;
3530 ps.insert(rect);
3531 ps90.insert(rect);
3532 ps.bloat(10);
3533 ps90.bloat(10, 10, 10, 10);
3534 rupolys.clear();
3535 rupolys45.clear();
3536 ps.get(rupolys);
3537 ps90.get(rupolys45);
3538 std::cout << rupolys[0] << std::endl;
3539 std::cout << rupolys45[0] << std::endl;
3540 if(!equivalence(ps, ps90)) {
3541 std::cout << "test manhattan vs general resize up failed\n";
3542 return 1;
3543 }
3544 ps.shrink(10);
3545 ps90.shrink(10, 10, 10, 10);
3546 if(!equivalence(ps, rect)) {
3547 std::cout << "test manhattan vs general resize down failed\n";
3548 return 1;
3549 }
3550 rectangle_data<int> rect2(3, 4, 6, 80);
3551 ps -= rect2;
3552 ps90 -= rect2;
3553 ps.bloat(1);
3554 ps90.bloat(1, 1, 1, 1);
3555 if(!equivalence(ps, ps90)) {
3556 std::cout << "test manhattan vs general with hole resize up failed\n";
3557 return 1;
3558 }
3559 ps.shrink(1);
3560 ps90.shrink(1, 1, 1, 1);
3561 if(!equivalence(ps, ps90)) {
3562 std::cout << "test manhattan vs general with hole resize down failed\n";
3563 return 1;
3564 }
3565 ps.clear();
3566 polygon_45_data<int> poly;
3567 std::vector<point_data<int> > pts;
3568 pts.push_back(point_data<int>(0, 0));
3569 pts.push_back(point_data<int>(10, 0));
3570 pts.push_back(point_data<int>(0, 10));
3571 polygon_45_set_data<int> ps45;
3572 set_points(poly, pts.begin(), pts.end());
3573 ps.insert(poly);
3574 ps45.insert(poly);
3575 ps.bloat(9);
3576 ps45.resize(9);
3577 rupolys.clear();
3578 rupolys45.clear();
3579 ps.get(rupolys);
3580 ps45.get(rupolys45);
3581 std::cout << rupolys[0] << std::endl;
3582 std::cout << rupolys45[0] << std::endl;
3583 pts.clear();
3584 pts.push_back(point_data<int>(32, -9));
3585 pts.push_back(point_data<int>(-9, 32));
3586 pts.push_back(point_data<int>(-9, -9));
3587 set_points(poly, pts.begin(), pts.end());
3588 if(!equivalence(ps, poly)) {
3589 std::cout << "test general resize up failed\n";
3590 return 1;
3591 }
3592 // this test is waived due to rounding differences between 45 and general resizing
3593 // general resizing is computing floating point coordinates for the intersection
3594 // and rounding those to closest while 45 is computing the normal point and rounding
3595 // that to closest, it turns out to result in different intersection point
3596 // we want the general to be more accurate to avoid artifacts
3597 //if(!equivalence(ps, ps45)) {
3598 // std::cout << "test 45 vs general resize up failed\n";
3599 // return 1;
3600 //}
3601 ps.shrink(9);
3602 ps45.resize(-9);
3603 if(!equivalence(ps, ps45)) {
3604 std::cout << "test 45 vs general resize down failed\n";
3605 return 1;
3606 }
3607 pts.clear();
3608 pts.push_back(point_data<int>(1, 1));
3609 pts.push_back(point_data<int>(7, 1));
3610 pts.push_back(point_data<int>(1, 7));
3611 set_points(poly, pts.begin(), pts.end());
3612 ps.insert(poly, true);
3613 ps45.insert(poly, true);
3614 ps.bloat(1);
3615 ps45.resize(1);
3616 rupolys.clear();
3617 rupolys45.clear();
3618 ps.get(rupolys);
3619 ps45.get(rupolys45);
3620 std::cout << rupolys[0] << std::endl;
3621 std::cout << rupolys45[0] << std::endl;
3622 pts.clear();
3623 pts.push_back(point_data<int>(12, -1));
3624 pts.push_back(point_data<int>(5, 6));
3625 pts.push_back(point_data<int>(5, 2));
3626 pts.push_back(point_data<int>(2, 2));
3627 pts.push_back(point_data<int>(2, 5));
3628 pts.push_back(point_data<int>(5, 2));
3629 pts.push_back(point_data<int>(5, 6));
3630 pts.push_back(point_data<int>(-1, 12));
3631 pts.push_back(point_data<int>(-1, -1));
3632 pts.push_back(point_data<int>(12, -1));
3633 set_points(poly, pts.begin(), pts.end());
3634 //waived
3635 //if(!equivalence(ps, poly)) {
3636 // std::cout << "test general resize up with holes failed\n";
3637 // return 1;
3638 //}
3639 //waived
3640 //if(!equivalence(ps, ps45)) {
3641 // std::cout << "test 45 vs general resize up with holes failed\n";
3642 // return 1;
3643 //}
3644 ps.shrink(1);
3645 ps45.resize(-1);
3646 if(!equivalence(ps, ps45)) {
3647 std::cout << "test 45 vs general resize down with holes failed\n";
3648 return 1;
3649 }
3650 ps.shrink(10);
3651 ps45.resize(-10);
3652 if(!equivalence(ps, ps45)) {
3653 std::cout << "test 45 vs general resize down 2 with holes failed\n";
3654 return 1;
3655 }
3656 }
3657
3658 {
3659
3660 Point pts[] = {construct<Point>(1565, 5735),
3661 construct<Point>(915, 5735),
3662 construct<Point>(915, 7085),
3663 construct<Point>(1565, 7085) };
3664 Polygon poly;
3665 set_points(poly, pts, pts+4);
3666 bool ret=gtl::contains(poly,gtl::construct<Point>(920, 7080));
3667 if(!ret) {
3668 std::cout << "contains failed!" << std::endl;
3669 return 1;
3670 }
3671 polygon_data<int> poly_aa;
3672 set_points(poly_aa, pts, pts+4);
3673 ret=gtl::contains(poly,gtl::construct<Point>(920, 7080));
3674 if(!ret) {
3675 std::cout << "contains 90 failed!" << std::endl;
3676 return 1;
3677 }
3678 polygon_with_holes_data<int> pwh;
3679 polygon_90_with_holes_data<int> p90wh;
3680 Point pts2[] = {construct<Point>(565, 15735),
3681 construct<Point>(15, 15735),
3682 construct<Point>(15, 17085),
3683 construct<Point>(565, 17085) };
3684 set_points(pwh, pts2, pts2+4);
3685 set_points(p90wh, pts2, pts2+4);
3686 pwh.set_holes(&poly_aa, (&poly_aa)+1);
3687 p90wh.set_holes(&poly, (&poly)+1);
3688 ret=gtl::contains(pwh,gtl::construct<Point>(920, 7080));
3689 if(ret) {
3690 std::cout << "contains wh failed!" << std::endl;
3691 return 1;
3692 }
3693 ret=gtl::contains(p90wh,gtl::construct<Point>(920, 7080));
3694 if(ret) {
3695 std::cout << "contains 90wh failed!" << std::endl;
3696 return 1;
3697 }
3698 std::reverse(pts, pts+4);
3699 set_points(poly, pts, pts+4);
3700 ret=gtl::contains(poly,gtl::construct<Point>(920, 7080));
3701 if(!ret) {
3702 std::cout << "reverse contains failed!" << std::endl;
3703 return 1;
3704 }
3705 }
3706 {
3707 // //MULTIPOLYGON
3708 // (
3709 // ((200 400,100 400,100 300,200 400)),
3710 // ((300 100,200 100,200 0,300 0,300 100)),
3711 // ((600 700,500 700,500 600,600 700)),
3712 // ((700 300,600 300,600 200,700 300)),
3713 // ((800 500,700 600,700 500,800 500)),
3714 // ((900 800,800 700,900 700,900 800)),
3715 // ((1000 200,900 100,1000 100,1000 200)),
3716 // ((1000 800,900 900,900 800,1000 800))),
3717 int mp1 [7][2*4] = {
3718 {200,400,100,400,100,300,200,400},
3719 {600,700,500,700,500,600,600,700},
3720 {700,300,600,300,600,200,700,300},
3721 {800,500,700,600,700,500,800,500},
3722 {900,800,800,700,900,700,900,800},
3723 {1000,200,900,100,1000,100,1000,200},
3724 {1000,800,900,900,900,800,1000,800}
3725 };
3726 int mp11 [2*5] = {300,100,200,100,200,0,300,0,300,100};
3727 polygon_45_set_data<int> pset1;
3728 polygon_45_set_data<int> pset2;
3729 for(int i = 0; i < 7; ++i) {
3730 addpoly(pset1, mp1[i], 4);
3731 }
3732 addpoly(pset1, mp11, 5);
3733 // //MULTIPOLYGON
3734 // (
3735 // ((200 800,100 800,100 700,200 700,200 800)),
3736 // ((400 200,300 100,400 100,400 200)),
3737 // ((400 800,300 700,400 700,400 800)),
3738 // ((700 100,600 0,700 0,700 100)),
3739 // ((700 200,600 200,600 100,700 200)),
3740 // ((900 200,800 200,800 0,900 0,900 200)),
3741 // ((1000 300,900 200,1000 200,1000 300)))
3742 int mp2 [5][2*4] = {
3743 {400,200,300,100,400,100,400,200},
3744 {400,800,300,700,400,700,400,800},
3745 {700,100,600,0,700,0,700,100},
3746 {700,200,600,200,600,100,700,200},
3747 {1000,300,900,200,1000,200,1000,300},
3748 };
3749 int mp21 [2*5] = {200,800,100,800,100,700,200,700,200,800};
3750 int mp22 [2*5] = {900,200,800,200,800,0,900,0,900,200};
3751 for(int i = 0; i < 5; ++i) {
3752 addpoly(pset2, mp2[i], 4);
3753 }
3754 addpoly(pset2, mp21, 5);
3755 addpoly(pset2, mp22, 5);
3756 polygon_45_set_data<int> orr = pset1 + pset2;
3757 polygon_45_set_data<int> inr = pset1 & pset2;
3758 std::cout << area(orr)<<std::endl;;
3759 std::cout << area(inr)<<std::endl;;
3760 std::vector<polygon_45_with_holes_data<int> > polys;
3761 assign(polys, orr);
3762 std::cout << area(polys) << std::endl;
3763 polygon_set_data<int> testbug;
3764 testbug.insert(orr);
3765 std::cout << area(testbug) << std::endl;
3766 polygon_set_data<int> testbug2;
3767 for(size_t i = 0; i < polys.size(); ++i) {
3768 for(size_t j = 0; j < polys.size(); ++j) {
3769 testbug2.clear();
3770 testbug2.insert(polys[i]);
3771 testbug2.insert(polys[j]);
3772 std::cout << i << " " << j << std::endl;
3773 std::cout << polys[i] << std::endl;
3774 std::cout << polys[j] << std::endl;
3775 if(area(testbug2) == 0.0) {
3776 std::cout << area(testbug2) << std::endl;
3777 std::cout << "Self touch 45 through general interface failed!\n";
3778 return 1;
3779 }
3780 }
3781 }
3782 }
3783
3784 {
3785 polygon_set_data<int> t_eq;
3786 t_eq.insert(rectangle_data<int>(0, 0, 5, 10));
3787 t_eq.insert(rectangle_data<int>(0, 5, 5, 10));
3788 std::cout << t_eq <<std::endl;
3789 polygon_set_data<int> t_eq2;
3790 t_eq2 += rectangle_data<int>(0, 0, 5, 10);
3791 std::cout << area(t_eq) <<std::endl;
3792 std::cout << area(t_eq2) <<std::endl;
3793 std::cout << t_eq <<std::endl;
3794 std::cout << t_eq2 <<std::endl;
3795 if(t_eq != t_eq2) {
3796 std::cout << "equivalence failed" << std::endl;
3797 return 1;
3798 }
3799 }
3800
3801 {
3802 using namespace boost::polygon;
3803 typedef point_data<int> Point;
3804 typedef segment_data<int> Dls;
3805 Point pt1(0, 0);
3806 Point pt2(10, 10);
3807 Point pt3(20, 20);
3808 Point pt4(20, 0);
3809 Dls dls1(pt1, pt2);
3810 Dls dls2(pt1, pt3);
3811 Dls dls3(pt1, pt4);
3812 Dls dls4(pt2, pt1);
3813 typedef std::vector<segment_data<int> > Dlss;
3814 Dlss dlss, result;
3815 dlss.push_back(dls1);
3816 dlss.push_back(dls2);
3817 dlss.push_back(dls3);
3818 dlss.push_back(dls4);
3819 rectangle_data<int> rect;
3820 envelope_segments(rect, dlss.begin(), dlss.end());
3821 assert_s(area(rect) == 400.0, "envelope");
3822 intersect_segments(result, dlss.begin(), dlss.end());
3823 dlss.swap(result);
3824 for (Dlss::iterator itr = dlss.begin(); itr != dlss.end(); ++itr) {
3825 std::cout << *itr << std::endl;
3826 }
3827 assert_s(dlss.size() == 5, "intersection");
3828 Dls dls5(Point(0,5), Point(5,0));
3829 dlss.push_back(dls5);
3830 std::cout << std::endl;
3831 result.clear();
3832 intersect_segments(result, dlss.begin(), dlss.end());
3833 dlss.swap(result);
3834 for (Dlss::iterator itr = dlss.begin(); itr != dlss.end(); ++itr) {
3835 std::cout << *itr << std::endl;
3836 }
3837 assert_s(dlss.size() == 11, "intersection2");
3838 }
3839
3840 {
3841 using namespace boost::polygon;
3842 std::vector<std::pair<std::size_t, segment_data<int> > > segs;
3843 segment_data<int> sarray[2];
3844 sarray[0] = segment_data<int>(point_data<int>(0,0), point_data<int>(10,10));
3845 sarray[1] = segment_data<int>(point_data<int>(10,0), point_data<int>(0,10));
3846 intersect_segments(segs, sarray, sarray+2);
3847 std::cout << segs.size() << std::endl;
3848 assert_s(segs.size() == 4, "intersection3");
3849 }
3850
3851
3852 /*New polygon_formation tests*/
3853 if(test_new_polygon_formation(0,NULL)){
3854 std::cerr << "[test_new_polygon_formation] failed" << std::endl;
3855 return 1;
3856 }
3857
3858 if(test_new_polygon_formation_marginal_threshold(0,NULL)){
3859 std::cerr << "[test_new_polygon_formation_marginal_threshold] failed"
3860 << std::endl;
3861 return 1;
3862 }
3863
3864 std::cout << "ALL TESTS COMPLETE\n";
3865 return 0;
3866 }
3867