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