ceph/src/boost/libs/geometry/test/algorithms/detail/partition.cpp

   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;
  43     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>
  57     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>
  66     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
  84     box_visitor()
  85         : count(0)
  86         , area(0)
  87     {}
  88
  89     template <typename Item>
  90     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
 107     point_in_box_visitor()
 108         : count(0)
 109     {}
 110
 111     template <typename Point, typename BoxItem>
 112     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
 126     reversed_point_in_box_visitor()
 127         : count(0)
 128     {}
 129
 130     template <typename BoxItem, typename Point>
 131     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>
 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 {
 173     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>
 188     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>
 197     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
 208     point_visitor()
 209         : count(0)
 210     {}
 211
 212     template <typename Item>
 213     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
 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>
 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
 284     svg_visitor(SvgMapper& mapper)
 285         : m_mapper(mapper)
 286     {}
 287
 288     template <typename Box>
 289     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>
 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
 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>
 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
 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
 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
 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
 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 }