libs/geometry/test/algorithms/detail/partition.cpp

   1 // Boost.Geometry (aka GGL, Generic Geometry Library)
   2 //
   3 // Copyright (c) 2007-2012 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/multi/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 #include <boost/geometry/multi/io/wkt/wkt.hpp>
  22
  23 #if defined(TEST_WITH_SVG)
  24 # include <boost/geometry/extensions/io/svg/svg_mapper.hpp>
  25 #endif
  26
  27 #include <boost/random/linear_congruential.hpp>
  28 #include <boost/random/uniform_int.hpp>
  29 #include <boost/random/uniform_real.hpp>
  30 #include <boost/random/variate_generator.hpp>
  31
  32
  33 template <typename Box>
  34 struct box_item
  35 {
  36     int id;
  37     Box box;
  38     box_item(int i = 0, std::string const& wkt = "")
  39         : id(i)
  40     {
  41         if (! wkt.empty())
  42         {
  43             bg::read_wkt(wkt, box);
  44         }
  45     }
  46 };
  47
  48
  49 struct get_box
  50 {
  51     template <typename Box, typename InputItem>
  52     static inline void apply(Box& total, InputItem const& item)
  53     {
  54         bg::expand(total, item.box);
  55     }
  56 };
  57
  58 struct ovelaps_box
  59 {
  60     template <typename Box, typename InputItem>
  61     static inline bool apply(Box const& box, InputItem const& item)
  62     {
  63         return ! bg::detail::disjoint::disjoint_box_box(box, item.box);
  64     }
  65 };
  66
  67
  68 template <typename Box>
  69 struct box_visitor
  70 {
  71     int count;
  72     typename bg::default_area_result<Box>::type area;
  73
  74     box_visitor()
  75         : count(0)
  76         , area(0)
  77     {}
  78
  79     template <typename Item>
  80     inline void apply(Item const& item1, Item const& item2)
  81     {
  82         if (bg::intersects(item1.box, item2.box))
  83         {
  84             Box b;
  85             bg::intersection(item1.box, item2.box, b);
  86             area += bg::area(b);
  87             count++;
  88         }
  89     }
  90 };
  91
  92
  93
  94 template <typename Box>
  95 void test_boxes(std::string const& wkt_box_list, double expected_area, int expected_count)
  96 {
  97     std::vector<std::string> wkt_boxes;
  98
  99     boost::split(wkt_boxes, wkt_box_list, boost::is_any_of(";"), boost::token_compress_on);
 100
 101     typedef box_item<Box> sample;
 102     std::vector<sample> boxes;
 103
 104     int index = 1;
 105     BOOST_FOREACH(std::string const& wkt, wkt_boxes)
 106     {
 107         boxes.push_back(sample(index++, wkt));
 108     }
 109
 110     box_visitor<Box> visitor;
 111     bg::partition
 112         <
 113             Box, get_box, ovelaps_box
 114         >::apply(boxes, visitor, 1);
 115
 116     BOOST_CHECK_CLOSE(visitor.area, expected_area, 0.001);
 117     BOOST_CHECK_EQUAL(visitor.count, expected_count);
 118 }
 119
 120
 121
 122 struct point_item
 123 {
 124     point_item()
 125         : id(0)
 126     {}
 127
 128     int id;
 129     double x;
 130     double y;
 131 };
 132
 133 BOOST_GEOMETRY_REGISTER_POINT_2D(point_item, double, cs::cartesian, x, y)
 134
 135
 136 struct get_point
 137 {
 138     template <typename Box, typename InputItem>
 139     static inline void apply(Box& total, InputItem const& item)
 140     {
 141         bg::expand(total, item);
 142     }
 143 };
 144
 145 struct ovelaps_point
 146 {
 147     template <typename Box, typename InputItem>
 148     static inline bool apply(Box const& box, InputItem const& item)
 149     {
 150         return ! bg::disjoint(item, box);
 151     }
 152 };
 153
 154
 155 struct point_visitor
 156 {
 157     int count;
 158
 159     point_visitor()
 160         : count(0)
 161     {}
 162
 163     template <typename Item>
 164     inline void apply(Item const& item1, Item const& item2)
 165     {
 166         if (bg::equals(item1, item2))
 167         {
 168             count++;
 169         }
 170     }
 171 };
 172
 173
 174
 175 void test_points(std::string const& wkt1, std::string const& wkt2, int expected_count)
 176 {
 177     bg::model::multi_point<point_item> mp1, mp2;
 178     bg::read_wkt(wkt1, mp1);
 179     bg::read_wkt(wkt2, mp2);
 180
 181     int id = 1;
 182     BOOST_FOREACH(point_item& p, mp1)
 183     { p.id = id++; }
 184     id = 1;
 185     BOOST_FOREACH(point_item& p, mp2)
 186     { p.id = id++; }
 187
 188     point_visitor visitor;
 189     bg::partition
 190         <
 191             bg::model::box<point_item>, get_point, ovelaps_point
 192         >::apply(mp1, mp2, visitor, 1);
 193
 194     BOOST_CHECK_EQUAL(visitor.count, expected_count);
 195 }
 196
 197
 198
 199 template <typename P>
 200 void test_all()
 201 {
 202     typedef bg::model::box<P> box;
 203
 204     test_boxes<box>(
 205         // 1           2             3               4             5             6             7
 206         "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)",
 207         5, // Area(Intersection(1,2)) + A(I(5,6))
 208         3);
 209
 210     test_boxes<box>(
 211         "box(0 0,10 10); box(4 4,6 6); box(3 3,7 7)",
 212             4 + 16 + 4,  // A(I(1,2)) + A(I(1,3)) + A(I(2,3))
 213             3);
 214
 215     test_boxes<box>(
 216         "box(0 2,10 3); box(3 1,4 5); box(7 1,8 5)",
 217             1 + 1,  // A(I(1,2)) + A(I(1,3))
 218             2);
 219
 220     test_points("multipoint((1 1))", "multipoint((1 1))", 1);
 221     test_points("multipoint((0 0),(1 1),(7 3),(10 10))", "multipoint((1 1),(2 2),(7 3))", 2);
 222
 223 }
 224
 225 //------------------- higher volumes
 226
 227 template <typename SvgMapper>
 228 struct svg_visitor
 229 {
 230     SvgMapper& m_mapper;
 231
 232     svg_visitor(SvgMapper& mapper)
 233         : m_mapper(mapper)
 234     {}
 235
 236     template <typename Box>
 237     inline void apply(Box const& box, int level)
 238     {
 239         /*
 240         std::string color("rgb(64,64,64)");
 241         switch(level)
 242         {
 243             case 0 : color = "rgb(255,0,0)"; break;
 244             case 1 : color = "rgb(0,255,0)"; break;
 245             case 2 : color = "rgb(0,0,255)"; break;
 246             case 3 : color = "rgb(255,255,0)"; break;
 247             case 4 : color = "rgb(255,0,255)"; break;
 248             case 5 : color = "rgb(0,255,255)"; break;
 249             case 6 : color = "rgb(255,128,0)"; break;
 250             case 7 : color = "rgb(0,128,255)"; break;
 251         }
 252         std::ostringstream style;
 253         style << "fill:none;stroke-width:" << (5.0 - level / 2.0) << ";stroke:" << color << ";";
 254         m_mapper.map(box, style.str());
 255         */
 256         m_mapper.map(box, "fill:none;stroke-width:2;stroke:rgb(0,0,0);");
 257
 258     }
 259 };
 260
 261
 262
 263
 264 template <typename Collection>
 265 void fill_points(Collection& collection, int seed, int size, int count)
 266 {
 267     typedef boost::minstd_rand base_generator_type;
 268
 269     base_generator_type generator(seed);
 270
 271     boost::uniform_int<> random_coordinate(0, size - 1);
 272     boost::variate_generator<base_generator_type&, boost::uniform_int<> >
 273         coordinate_generator(generator, random_coordinate);
 274
 275     std::set<std::pair<int, int> > included;
 276
 277     int n = 0;
 278     for (int i = 0; n < count && i < count*count; i++)
 279     {
 280         int x = coordinate_generator();
 281         int y = coordinate_generator();
 282         std::pair<int, int> pair = std::make_pair(x, y);
 283         if (included.find(pair) == included.end())
 284         {
 285             included.insert(pair);
 286             typename boost::range_value<Collection>::type item;
 287             item.x = x;
 288             item.y = y;
 289             collection.push_back(item);
 290             n++;
 291         }
 292     }
 293 }
 294
 295 void test_many_points(int seed, int size, int count)
 296 {
 297     bg::model::multi_point<point_item> mp1, mp2;
 298
 299     fill_points(mp1, seed, size, count);
 300     fill_points(mp2, seed * 2, size, count);
 301
 302     // Test equality in quadratic loop
 303     int expected_count = 0;
 304     BOOST_FOREACH(point_item const& item1, mp1)
 305     {
 306         BOOST_FOREACH(point_item const& item2, mp2)
 307         {
 308             if (bg::equals(item1, item2))
 309             {
 310                 expected_count++;
 311             }
 312         }
 313     }
 314
 315 #if defined(TEST_WITH_SVG)
 316     std::ostringstream filename;
 317     filename << "partition" << seed << ".svg";
 318     std::ofstream svg(filename.str().c_str());
 319
 320     bg::svg_mapper<point_item> mapper(svg, 800, 800);
 321
 322     {
 323         point_item p;
 324         p.x = -1; p.y = -1; mapper.add(p);
 325         p.x = size + 1; p.y = size + 1; mapper.add(p);
 326     }
 327
 328     typedef svg_visitor<bg::svg_mapper<point_item> > box_visitor_type;
 329     box_visitor_type box_visitor(mapper);
 330 #else
 331     typedef bg::visit_no_policy box_visitor_type;
 332     box_visitor_type box_visitor;
 333 #endif
 334
 335     point_visitor visitor;
 336     bg::partition
 337         <
 338             bg::model::box<point_item>, get_point, ovelaps_point,
 339             box_visitor_type
 340         >::apply(mp1, mp2, visitor, 2, box_visitor);
 341
 342     BOOST_CHECK_EQUAL(visitor.count, expected_count);
 343
 344 #if defined(TEST_WITH_SVG)
 345     BOOST_FOREACH(point_item const& item, mp1)
 346     {
 347         mapper.map(item, "fill:rgb(255,128,0);stroke:rgb(0,0,100);stroke-width:1", 8);
 348     }
 349     BOOST_FOREACH(point_item const& item, mp2)
 350     {
 351         mapper.map(item, "fill:rgb(0,128,255);stroke:rgb(0,0,100);stroke-width:1", 4);
 352     }
 353 #endif
 354 }
 355
 356 template <typename Collection>
 357 void fill_boxes(Collection& collection, int seed, int size, int count)
 358 {
 359     typedef boost::minstd_rand base_generator_type;
 360
 361     base_generator_type generator(seed);
 362
 363     boost::uniform_int<> random_coordinate(0, size * 10 - 1);
 364     boost::variate_generator<base_generator_type&, boost::uniform_int<> >
 365         coordinate_generator(generator, random_coordinate);
 366
 367     int n = 0;
 368     for (int i = 0; n < count && i < count*count; i++)
 369     {
 370         int w = coordinate_generator() % 30;
 371         int h = coordinate_generator() % 30;
 372         if (w > 0 && h > 0)
 373         {
 374             int x = coordinate_generator();
 375             int y = coordinate_generator();
 376             if (x + w < size * 10 && y + h < size * 10)
 377             {
 378                 typename boost::range_value<Collection>::type item(n+1);
 379                 bg::assign_values(item.box, x / 10.0, y / 10.0, (x + w) / 10.0, (y + h) / 10.0);
 380                 collection.push_back(item);
 381                 n++;
 382             }
 383         }
 384     }
 385 }
 386
 387
 388
 389 void test_many_boxes(int seed, int size, int count)
 390 {
 391     typedef bg::model::box<point_item> box_type;
 392     std::vector<box_item<box_type> > boxes;
 393
 394     fill_boxes(boxes, seed, size, count);
 395
 396     // Test equality in quadratic loop
 397     int expected_count = 0;
 398     double expected_area = 0.0;
 399     BOOST_FOREACH(box_item<box_type> const& item1, boxes)
 400     {
 401         BOOST_FOREACH(box_item<box_type> const& item2, boxes)
 402         {
 403             if (item1.id < item2.id)
 404             {
 405                 if (bg::intersects(item1.box, item2.box))
 406                 {
 407                     box_type b;
 408                     bg::intersection(item1.box, item2.box, b);
 409                     expected_area += bg::area(b);
 410                     expected_count++;
 411                 }
 412             }
 413         }
 414     }
 415
 416
 417 #if defined(TEST_WITH_SVG)
 418     std::ostringstream filename;
 419     filename << "partition_box_" << seed << ".svg";
 420     std::ofstream svg(filename.str().c_str());
 421
 422     bg::svg_mapper<point_item> mapper(svg, 800, 800);
 423
 424     {
 425         point_item p;
 426         p.x = -1; p.y = -1; mapper.add(p);
 427         p.x = size + 1; p.y = size + 1; mapper.add(p);
 428     }
 429
 430     BOOST_FOREACH(box_item<box_type> const& item, boxes)
 431     {
 432         mapper.map(item.box, "opacity:0.6;fill:rgb(50,50,210);stroke:rgb(0,0,0);stroke-width:1");
 433     }
 434
 435     typedef svg_visitor<bg::svg_mapper<point_item> > partition_visitor_type;
 436     partition_visitor_type partition_visitor(mapper);
 437
 438
 439     box_visitor<box_type> visitor;
 440     bg::partition
 441         <
 442             box_type, get_box, ovelaps_box,
 443             partition_visitor_type
 444         >::apply(boxes, visitor, 2, partition_visitor);
 445
 446     BOOST_CHECK_EQUAL(visitor.count, expected_count);
 447     BOOST_CHECK_CLOSE(visitor.area, expected_area, 0.001);
 448
 449 #endif
 450 }
 451
 452
 453
 454
 455
 456 int test_main( int , char* [] )
 457 {
 458     test_all<bg::model::d2::point_xy<double> >();
 459
 460     test_many_points(12345, 20, 40);
 461     test_many_points(54321, 20, 60);
 462     test_many_points(67890, 20, 80);
 463     test_many_points(98765, 20, 100);
 464     for (int i = 1; i < 10; i++)
 465     {
 466         test_many_points(i, 30, i * 20);
 467     }
 468
 469     test_many_boxes(12345, 20, 40);
 470     for (int i = 1; i < 10; i++)
 471     {
 472         test_many_boxes(i, 20, i * 10);
 473     }
 474
 475     return 0;
 476 }