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