1 // Boost.Geometry (aka GGL, Generic Geometry Library)
2 //
3 // Copyright (c) 2007-2015 Barend Gehrels, Amsterdam, the Netherlands.
4 // Copyright (c) 2017 Adam Wulkiewicz, Lodz, Poland.
5 //
6 // This file was modified by Oracle on 2017, 2018.
7 // Modifications copyright (c) 2017-2018 Oracle and/or its affiliates.
8 // Contributed and/or modified by Adam Wulkiewicz, on behalf of Oracle
9 //
10 // Use, modification and distribution is subject to the Boost Software License,
11 // Version 1.0. (See accompanying file LICENSE_1_0.txt or copy at
12 // http://www.boost.org/LICENSE_1_0.txt)
13
14 #include <geometry_test_common.hpp>
15
16 #include <algorithms/test_overlay.hpp>
17
18
19 #include <boost/geometry/geometry.hpp>
20 #include <boost/geometry/geometries/multi_point.hpp>
21 #include <boost/geometry/geometries/point_xy.hpp>
22 #include <boost/geometry/geometries/register/point.hpp>
23
24 #include <boost/geometry/algorithms/detail/partition.hpp>
25
26 #include <boost/geometry/io/wkt/wkt.hpp>
27
28 #if defined(TEST_WITH_SVG)
29 # include <boost/geometry/io/svg/svg_mapper.hpp>
30 #endif
31
32 #include <boost/random/linear_congruential.hpp>
33 #include <boost/random/uniform_int.hpp>
34 #include <boost/random/uniform_real.hpp>
35 #include <boost/random/variate_generator.hpp>
36
37
38 template <typename Box>
39 struct box_item
40 {
41 int id;
42 Box box;
box_itembox_item43 box_item(int i = 0, std::string const& wkt = "")
44 : id(i)
45 {
46 if (! wkt.empty())
47 {
48 bg::read_wkt(wkt, box);
49 }
50 }
51 };
52
53
54 struct get_box
55 {
56 template <typename Box, typename InputItem>
applyget_box57 static inline void apply(Box& total, InputItem const& item)
58 {
59 bg::expand(total, item.box);
60 }
61 };
62
63 struct ovelaps_box
64 {
65 template <typename Box, typename InputItem>
applyovelaps_box66 static inline bool apply(Box const& box, InputItem const& item)
67 {
68 typename bg::strategy::disjoint::services::default_strategy
69 <
70 Box, Box
71 >::type strategy;
72
73 return ! bg::detail::disjoint::disjoint_box_box(box, item.box, strategy);
74 }
75 };
76
77
78 template <typename Box>
79 struct box_visitor
80 {
81 int count;
82 typename bg::default_area_result<Box>::type area;
83
box_visitorbox_visitor84 box_visitor()
85 : count(0)
86 , area(0)
87 {}
88
89 template <typename Item>
applybox_visitor90 inline bool apply(Item const& item1, Item const& item2)
91 {
92 if (bg::intersects(item1.box, item2.box))
93 {
94 Box b;
95 bg::intersection(item1.box, item2.box, b);
96 area += bg::area(b);
97 count++;
98 }
99 return true;
100 }
101 };
102
103 struct point_in_box_visitor
104 {
105 int count;
106
point_in_box_visitorpoint_in_box_visitor107 point_in_box_visitor()
108 : count(0)
109 {}
110
111 template <typename Point, typename BoxItem>
applypoint_in_box_visitor112 inline bool apply(Point const& point, BoxItem const& box_item)
113 {
114 if (bg::within(point, box_item.box))
115 {
116 count++;
117 }
118 return true;
119 }
120 };
121
122 struct reversed_point_in_box_visitor
123 {
124 int count;
125
reversed_point_in_box_visitorreversed_point_in_box_visitor126 reversed_point_in_box_visitor()
127 : count(0)
128 {}
129
130 template <typename BoxItem, typename Point>
applyreversed_point_in_box_visitor131 inline bool apply(BoxItem const& box_item, Point const& point)
132 {
133 if (bg::within(point, box_item.box))
134 {
135 count++;
136 }
137 return true;
138 }
139 };
140
141
142
143 template <typename Box>
test_boxes(std::string const & wkt_box_list,double expected_area,int expected_count)144 void test_boxes(std::string const& wkt_box_list, double expected_area, int expected_count)
145 {
146 std::vector<std::string> wkt_boxes;
147
148 boost::split(wkt_boxes, wkt_box_list, boost::is_any_of(";"), boost::token_compress_on);
149
150 typedef box_item<Box> sample;
151 std::vector<sample> boxes;
152
153 int index = 1;
154 BOOST_FOREACH(std::string const& wkt, wkt_boxes)
155 {
156 boxes.push_back(sample(index++, wkt));
157 }
158
159 box_visitor<Box> visitor;
160 bg::partition
161 <
162 Box
163 >::apply(boxes, visitor, get_box(), ovelaps_box(), 1);
164
165 BOOST_CHECK_CLOSE(visitor.area, expected_area, 0.001);
166 BOOST_CHECK_EQUAL(visitor.count, expected_count);
167 }
168
169
170
171 struct point_item
172 {
point_itempoint_item173 point_item()
174 : id(0)
175 {}
176
177 int id;
178 double x;
179 double y;
180 };
181
182 BOOST_GEOMETRY_REGISTER_POINT_2D(point_item, double, cs::cartesian, x, y)
183
184
185 struct get_point
186 {
187 template <typename Box, typename InputItem>
applyget_point188 static inline void apply(Box& total, InputItem const& item)
189 {
190 bg::expand(total, item);
191 }
192 };
193
194 struct ovelaps_point
195 {
196 template <typename Box, typename InputItem>
applyovelaps_point197 static inline bool apply(Box const& box, InputItem const& item)
198 {
199 return ! bg::disjoint(item, box);
200 }
201 };
202
203
204 struct point_visitor
205 {
206 int count;
207
point_visitorpoint_visitor208 point_visitor()
209 : count(0)
210 {}
211
212 template <typename Item>
applypoint_visitor213 inline bool apply(Item const& item1, Item const& item2)
214 {
215 if (bg::equals(item1, item2))
216 {
217 count++;
218 }
219 return true;
220 }
221 };
222
223
224
test_points(std::string const & wkt1,std::string const & wkt2,int expected_count)225 void test_points(std::string const& wkt1, std::string const& wkt2, int expected_count)
226 {
227 bg::model::multi_point<point_item> mp1, mp2;
228 bg::read_wkt(wkt1, mp1);
229 bg::read_wkt(wkt2, mp2);
230
231 int id = 1;
232 BOOST_FOREACH(point_item& p, mp1)
233 { p.id = id++; }
234 id = 1;
235 BOOST_FOREACH(point_item& p, mp2)
236 { p.id = id++; }
237
238 point_visitor visitor;
239 bg::partition
240 <
241 bg::model::box<point_item>
242 >::apply(mp1, mp2, visitor, get_point(), ovelaps_point(),
243 get_point(), ovelaps_point(), 1);
244
245 BOOST_CHECK_EQUAL(visitor.count, expected_count);
246 }
247
248
249
250 template <typename P>
test_all()251 void test_all()
252 {
253 typedef bg::model::box<P> box;
254
255 test_boxes<box>(
256 // 1 2 3 4 5 6 7
257 "box(0 0,1 1); box(0 0,2 2); box(9 9,10 10); box(8 8,9 9); box(4 4,6 6); box(2 4,6 8); box(7 1,8 2)",
258 5, // Area(Intersection(1,2)) + A(I(5,6))
259 3);
260
261 test_boxes<box>(
262 "box(0 0,10 10); box(4 4,6 6); box(3 3,7 7)",
263 4 + 16 + 4, // A(I(1,2)) + A(I(1,3)) + A(I(2,3))
264 3);
265
266 test_boxes<box>(
267 "box(0 2,10 3); box(3 1,4 5); box(7 1,8 5)",
268 1 + 1, // A(I(1,2)) + A(I(1,3))
269 2);
270
271 test_points("multipoint((1 1))", "multipoint((1 1))", 1);
272 test_points("multipoint((0 0),(1 1),(7 3),(10 10))", "multipoint((1 1),(2 2),(7 3))", 2);
273
274 }
275
276 //------------------- higher volumes
277
278 #if defined(TEST_WITH_SVG)
279 template <typename SvgMapper>
280 struct svg_visitor
281 {
282 SvgMapper& m_mapper;
283
svg_visitorsvg_visitor284 svg_visitor(SvgMapper& mapper)
285 : m_mapper(mapper)
286 {}
287
288 template <typename Box>
applysvg_visitor289 inline void apply(Box const& box, int level)
290 {
291 /*
292 std::string color("rgb(64,64,64)");
293 switch(level)
294 {
295 case 0 : color = "rgb(255,0,0)"; break;
296 case 1 : color = "rgb(0,255,0)"; break;
297 case 2 : color = "rgb(0,0,255)"; break;
298 case 3 : color = "rgb(255,255,0)"; break;
299 case 4 : color = "rgb(255,0,255)"; break;
300 case 5 : color = "rgb(0,255,255)"; break;
301 case 6 : color = "rgb(255,128,0)"; break;
302 case 7 : color = "rgb(0,128,255)"; break;
303 }
304 std::ostringstream style;
305 style << "fill:none;stroke-width:" << (5.0 - level / 2.0) << ";stroke:" << color << ";";
306 m_mapper.map(box, style.str());
307 */
308 m_mapper.map(box, "fill:none;stroke-width:2;stroke:rgb(0,0,0);");
309
310 }
311 };
312 #endif
313
314
315 template <typename Collection>
fill_points(Collection & collection,int seed,int size,int count)316 void fill_points(Collection& collection, int seed, int size, int count)
317 {
318 typedef boost::minstd_rand base_generator_type;
319
320 base_generator_type generator(seed);
321
322 boost::uniform_int<> random_coordinate(0, size - 1);
323 boost::variate_generator<base_generator_type&, boost::uniform_int<> >
324 coordinate_generator(generator, random_coordinate);
325
326 std::set<std::pair<int, int> > included;
327
328 int n = 0;
329 for (int i = 0; n < count && i < count*count; i++)
330 {
331 int x = coordinate_generator();
332 int y = coordinate_generator();
333 std::pair<int, int> pair = std::make_pair(x, y);
334 if (included.find(pair) == included.end())
335 {
336 included.insert(pair);
337 typename boost::range_value<Collection>::type item;
338 item.x = x;
339 item.y = y;
340 collection.push_back(item);
341 n++;
342 }
343 }
344 }
345
test_many_points(int seed,int size,int count)346 void test_many_points(int seed, int size, int count)
347 {
348 bg::model::multi_point<point_item> mp1, mp2;
349
350 fill_points(mp1, seed, size, count);
351 fill_points(mp2, seed * 2, size, count);
352
353 // Test equality in quadratic loop
354 int expected_count = 0;
355 BOOST_FOREACH(point_item const& item1, mp1)
356 {
357 BOOST_FOREACH(point_item const& item2, mp2)
358 {
359 if (bg::equals(item1, item2))
360 {
361 expected_count++;
362 }
363 }
364 }
365
366 #if defined(TEST_WITH_SVG)
367 std::ostringstream filename;
368 filename << "partition" << seed << ".svg";
369 std::ofstream svg(filename.str().c_str());
370
371 bg::svg_mapper<point_item> mapper(svg, 800, 800);
372
373 {
374 point_item p;
375 p.x = -1; p.y = -1; mapper.add(p);
376 p.x = size + 1; p.y = size + 1; mapper.add(p);
377 }
378
379 typedef svg_visitor<bg::svg_mapper<point_item> > box_visitor_type;
380 box_visitor_type box_visitor(mapper);
381 #else
382 typedef bg::detail::partition::visit_no_policy box_visitor_type;
383 box_visitor_type box_visitor;
384 #endif
385
386 point_visitor visitor;
387 bg::partition
388 <
389 bg::model::box<point_item>,
390 bg::detail::partition::include_all_policy,
391 bg::detail::partition::include_all_policy
392 >::apply(mp1, mp2, visitor, get_point(), ovelaps_point(),
393 get_point(), ovelaps_point(), 2, box_visitor);
394
395 BOOST_CHECK_EQUAL(visitor.count, expected_count);
396
397 #if defined(TEST_WITH_SVG)
398 BOOST_FOREACH(point_item const& item, mp1)
399 {
400 mapper.map(item, "fill:rgb(255,128,0);stroke:rgb(0,0,100);stroke-width:1", 8);
401 }
402 BOOST_FOREACH(point_item const& item, mp2)
403 {
404 mapper.map(item, "fill:rgb(0,128,255);stroke:rgb(0,0,100);stroke-width:1", 4);
405 }
406 #endif
407 }
408
409 template <typename Collection>
fill_boxes(Collection & collection,int seed,int size,int count)410 void fill_boxes(Collection& collection, int seed, int size, int count)
411 {
412 typedef boost::minstd_rand base_generator_type;
413
414 base_generator_type generator(seed);
415
416 boost::uniform_int<> random_coordinate(0, size * 10 - 1);
417 boost::variate_generator<base_generator_type&, boost::uniform_int<> >
418 coordinate_generator(generator, random_coordinate);
419
420 int n = 0;
421 for (int i = 0; n < count && i < count*count; i++)
422 {
423 int w = coordinate_generator() % 30;
424 int h = coordinate_generator() % 30;
425 if (w > 0 && h > 0)
426 {
427 int x = coordinate_generator();
428 int y = coordinate_generator();
429 if (x + w < size * 10 && y + h < size * 10)
430 {
431 typename boost::range_value<Collection>::type item(n+1);
432 bg::assign_values(item.box, x / 10.0, y / 10.0, (x + w) / 10.0, (y + h) / 10.0);
433 collection.push_back(item);
434 n++;
435 }
436 }
437 }
438 }
439
test_many_boxes(int seed,int size,int count)440 void test_many_boxes(int seed, int size, int count)
441 {
442 typedef bg::model::box<point_item> box_type;
443 std::vector<box_item<box_type> > boxes;
444
445 fill_boxes(boxes, seed, size, count);
446
447 // Test equality in quadratic loop
448 int expected_count = 0;
449 double expected_area = 0.0;
450 BOOST_FOREACH(box_item<box_type> const& item1, boxes)
451 {
452 BOOST_FOREACH(box_item<box_type> const& item2, boxes)
453 {
454 if (item1.id < item2.id)
455 {
456 if (bg::intersects(item1.box, item2.box))
457 {
458 box_type b;
459 bg::intersection(item1.box, item2.box, b);
460 expected_area += bg::area(b);
461 expected_count++;
462 }
463 }
464 }
465 }
466
467
468 #if defined(TEST_WITH_SVG)
469 std::ostringstream filename;
470 filename << "partition_box_" << seed << ".svg";
471 std::ofstream svg(filename.str().c_str());
472
473 bg::svg_mapper<point_item> mapper(svg, 800, 800);
474
475 {
476 point_item p;
477 p.x = -1; p.y = -1; mapper.add(p);
478 p.x = size + 1; p.y = size + 1; mapper.add(p);
479 }
480
481 BOOST_FOREACH(box_item<box_type> const& item, boxes)
482 {
483 mapper.map(item.box, "opacity:0.6;fill:rgb(50,50,210);stroke:rgb(0,0,0);stroke-width:1");
484 }
485
486 typedef svg_visitor<bg::svg_mapper<point_item> > partition_box_visitor_type;
487 partition_box_visitor_type partition_box_visitor(mapper);
488
489 #else
490 typedef bg::detail::partition::visit_no_policy partition_box_visitor_type;
491 partition_box_visitor_type partition_box_visitor;
492 #endif
493
494 box_visitor<box_type> visitor;
495 bg::partition
496 <
497 box_type,
498 bg::detail::partition::include_all_policy,
499 bg::detail::partition::include_all_policy
500 >::apply(boxes, visitor, get_box(), ovelaps_box(),
501 2, partition_box_visitor);
502
503 BOOST_CHECK_EQUAL(visitor.count, expected_count);
504 BOOST_CHECK_CLOSE(visitor.area, expected_area, 0.001);
505 }
506
test_two_collections(int seed1,int seed2,int size,int count)507 void test_two_collections(int seed1, int seed2, int size, int count)
508 {
509 typedef bg::model::box<point_item> box_type;
510 std::vector<box_item<box_type> > boxes1, boxes2;
511
512 fill_boxes(boxes1, seed1, size, count);
513 fill_boxes(boxes2, seed2, size, count);
514
515 // Get expectations in quadratic loop
516 int expected_count = 0;
517 double expected_area = 0.0;
518 BOOST_FOREACH(box_item<box_type> const& item1, boxes1)
519 {
520 BOOST_FOREACH(box_item<box_type> const& item2, boxes2)
521 {
522 if (bg::intersects(item1.box, item2.box))
523 {
524 box_type b;
525 bg::intersection(item1.box, item2.box, b);
526 expected_area += bg::area(b);
527 expected_count++;
528 }
529 }
530 }
531
532
533 #if defined(TEST_WITH_SVG)
534 std::ostringstream filename;
535 filename << "partition_boxes_" << seed1 << "_" << seed2 << ".svg";
536 std::ofstream svg(filename.str().c_str());
537
538 bg::svg_mapper<point_item> mapper(svg, 800, 800);
539
540 {
541 point_item p;
542 p.x = -1; p.y = -1; mapper.add(p);
543 p.x = size + 1; p.y = size + 1; mapper.add(p);
544 }
545
546 BOOST_FOREACH(box_item<box_type> const& item, boxes1)
547 {
548 mapper.map(item.box, "opacity:0.6;fill:rgb(50,50,210);stroke:rgb(0,0,0);stroke-width:1");
549 }
550 BOOST_FOREACH(box_item<box_type> const& item, boxes2)
551 {
552 mapper.map(item.box, "opacity:0.6;fill:rgb(0,255,0);stroke:rgb(0,0,0);stroke-width:1");
553 }
554
555 typedef svg_visitor<bg::svg_mapper<point_item> > partition_box_visitor_type;
556 partition_box_visitor_type partition_box_visitor(mapper);
557 #else
558 typedef bg::detail::partition::visit_no_policy partition_box_visitor_type;
559 partition_box_visitor_type partition_box_visitor;
560 #endif
561
562 box_visitor<box_type> visitor;
563 bg::partition
564 <
565 box_type,
566 bg::detail::partition::include_all_policy,
567 bg::detail::partition::include_all_policy
568 >::apply(boxes1, boxes2, visitor, get_box(), ovelaps_box(),
569 get_box(), ovelaps_box(), 2, partition_box_visitor);
570
571 BOOST_CHECK_EQUAL(visitor.count, expected_count);
572 BOOST_CHECK_CLOSE(visitor.area, expected_area, 0.001);
573 }
574
575
test_heterogenuous_collections(int seed1,int seed2,int size,int count)576 void test_heterogenuous_collections(int seed1, int seed2, int size, int count)
577 {
578 typedef bg::model::box<point_item> box_type;
579 std::vector<point_item> points;
580 std::vector<box_item<box_type> > boxes;
581
582 fill_points(points, seed1, size, count);
583 fill_boxes(boxes, seed2, size, count);
584
585 // Get expectations in quadratic loop
586 int expected_count = 0;
587 BOOST_FOREACH(point_item const& point, points)
588 {
589 BOOST_FOREACH(box_item<box_type> const& box_item, boxes)
590 {
591 if (bg::within(point, box_item.box))
592 {
593 expected_count++;
594 }
595 }
596 }
597
598
599 #if defined(TEST_WITH_SVG)
600 std::ostringstream filename;
601 filename << "partition_heterogeneous_" << seed1 << "_" << seed2 << ".svg";
602 std::ofstream svg(filename.str().c_str());
603
604 bg::svg_mapper<point_item> mapper(svg, 800, 800);
605
606 {
607 point_item p;
608 p.x = -1; p.y = -1; mapper.add(p);
609 p.x = size + 1; p.y = size + 1; mapper.add(p);
610 }
611
612 BOOST_FOREACH(point_item const& point, points)
613 {
614 mapper.map(point, "fill:rgb(255,128,0);stroke:rgb(0,0,100);stroke-width:1", 8);
615 }
616 BOOST_FOREACH(box_item<box_type> const& item, boxes)
617 {
618 mapper.map(item.box, "opacity:0.6;fill:rgb(0,255,0);stroke:rgb(0,0,0);stroke-width:1");
619 }
620
621 typedef svg_visitor<bg::svg_mapper<point_item> > partition_box_visitor_type;
622 partition_box_visitor_type partition_box_visitor(mapper);
623 #else
624 typedef bg::detail::partition::visit_no_policy partition_box_visitor_type;
625 partition_box_visitor_type partition_box_visitor;
626 #endif
627
628 point_in_box_visitor visitor1;
629 bg::partition
630 <
631 box_type,
632 bg::detail::partition::include_all_policy,
633 bg::detail::partition::include_all_policy
634 >::apply(points, boxes, visitor1, get_point(), ovelaps_point(),
635 get_box(), ovelaps_box(), 2, partition_box_visitor);
636
637 reversed_point_in_box_visitor visitor2;
638 bg::partition
639 <
640 box_type,
641 bg::detail::partition::include_all_policy,
642 bg::detail::partition::include_all_policy
643 >::apply(boxes, points, visitor2, get_box(), ovelaps_box(),
644 get_point(), ovelaps_point(), 2, partition_box_visitor);
645
646 BOOST_CHECK_EQUAL(visitor1.count, expected_count);
647 BOOST_CHECK_EQUAL(visitor2.count, expected_count);
648 }
649
test_main(int,char * [])650 int test_main( int , char* [] )
651 {
652 test_all<bg::model::d2::point_xy<double> >();
653
654 test_many_points(12345, 20, 40);
655 test_many_points(54321, 20, 60);
656 test_many_points(67890, 20, 80);
657 test_many_points(98765, 20, 100);
658 for (int i = 1; i < 10; i++)
659 {
660 test_many_points(i, 30, i * 20);
661 }
662
663 test_many_boxes(12345, 20, 40);
664 for (int i = 1; i < 10; i++)
665 {
666 test_many_boxes(i, 20, i * 10);
667 }
668
669 test_two_collections(12345, 54321, 20, 40);
670 test_two_collections(67890, 98765, 20, 60);
671
672 test_heterogenuous_collections(67890, 98765, 20, 60);
673
674 return 0;
675 }
676