libs/geometry/test/algorithms/overlay/overlay.cpp

   1 // Boost.Geometry (aka GGL, Generic Geometry Library)
   2 // Unit Test
   3
   4 // Copyright (c) 2015 Barend Gehrels, Amsterdam, the Netherlands.
   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
  15 #include <iostream>
  16 #include <iomanip>
  17 #include <fstream>
  18 #include <sstream>
  19 #include <string>
  20
  21 #include <boost/type_traits/is_same.hpp>
  22
  23 #if defined(TEST_WITH_SVG)
  24 #  include <boost/geometry/io/svg/svg_mapper.hpp>
  25 #endif
  26
  27 #include <geometry_test_common.hpp>
  28 #include <algorithms/check_validity.hpp>
  29
  30 #include <boost/geometry.hpp>
  31 #include <boost/geometry/algorithms/detail/overlay/debug_turn_info.hpp>
  32 #include <boost/geometry/geometries/geometries.hpp>
  33
  34 //#include <boost/geometry/extensions/algorithms/inverse.hpp>
  35
  36 #if defined(TEST_WITH_SVG)
  37 #  include <boost/geometry/io/svg/svg_mapper.hpp>
  38 #endif
  39
  40 #include "multi_overlay_cases.hpp"
  41
  42
  43 #if defined(TEST_WITH_SVG)
  44 template <typename Mapper>
  45 struct map_visitor
  46 {
  47     map_visitor(Mapper& mapper)
  48         : m_mapper(mapper)
  49         , m_traverse_seq(0)
  50         , m_do_output(true)
  51     {}
  52
  53     void print(char const* header)
  54     {}
  55
  56     template <typename Turns>
  57     void print(char const* header, Turns const& turns, int turn_index)
  58     {
  59         std::string style = "fill:rgb(0,0,0);font-family:Arial;font-size:6px";
  60         stream(turns, turns[turn_index], turns[turn_index].operations[0], header, style);
  61     }
  62
  63     template <typename Turns>
  64     void print(char const* header, Turns const& turns, int turn_index, int op_index)
  65     {
  66         std::string style = "fill:rgb(0,0,0);font-family:Arial;font-size:6px";
  67         stream(turns, turns[turn_index], turns[turn_index].operations[op_index], header, style);
  68     }
  69
  70     template <typename Turns>
  71     void visit_turns(int phase, Turns const& turns)
  72     {
  73         typedef typename boost::range_value<Turns>::type turn_type;
  74         int index = 0;
  75         BOOST_FOREACH(turn_type const& turn, turns)
  76         {
  77             switch (phase)
  78             {
  79                 case 1 :
  80                     m_mapper.map(turn.point, "fill:rgb(255,128,0);"
  81                             "stroke:rgb(0,0,0);stroke-width:1", 3);
  82                     break;
  83                 case 11 :
  84                     m_mapper.map(turn.point, "fill:rgb(92,255,0);" // Greenish
  85                             "stroke:rgb(0,0,0);stroke-width:1", 3);
  86                     break;
  87                 case 21 :
  88                     m_mapper.map(turn.point, "fill:rgb(0,128,255);" // Blueish
  89                             "stroke:rgb(0,0,0);stroke-width:1", 3);
  90                     break;
  91                 case 3 :
  92                     label_turn(index, turn);
  93                     break;
  94             }
  95             index++;
  96         }
  97     }
  98
  99     template <typename Turns, typename Turn, typename Operation>
 100     std::string stream_turn_index(Turns const& turns, Turn const& turn, Operation const& op)
 101     {
 102         std::ostringstream out;
 103
 104         if (turn.cluster_id >= 0)
 105         {
 106             out << "cl=" << turn.cluster_id << " ";
 107         }
 108
 109         // Because turn index is unknown here, and still useful for debugging,
 110         std::size_t index = 0;
 111         for (typename Turns::const_iterator it = turns.begin();
 112            it != turns.end(); ++it, ++index)
 113         {
 114           Turn const& t = *it;
 115           if (&t == &turn)
 116           {
 117               out << index;
 118               break;
 119           }
 120         }
 121
 122         if (&op == &turn.operations[0]) { out << "[0]"; }
 123         if (&op == &turn.operations[1]) { out << "[1]"; }
 124         return out.str();
 125     }
 126
 127     template <typename Clusters, typename Turns>
 128     void visit_clusters(Clusters const& clusters, Turns const& turns)
 129     {
 130         typedef typename boost::range_value<Turns>::type turn_type;
 131         int index = 0;
 132         BOOST_FOREACH(turn_type const& turn, turns)
 133         {
 134             if (turn.cluster_id >= 0)
 135             {
 136                 std::cout << " TURN: " << index << "  part of cluster "  << turn.cluster_id << std::endl;
 137             }
 138             index++;
 139         }
 140
 141         for (typename Clusters::const_iterator it = clusters.begin(); it != clusters.end(); ++it)
 142         {
 143             std::cout << " CLUSTER " << it->first << ": ";
 144             for (typename std::set<bg::signed_size_type>::const_iterator sit
 145                  = it->second.turn_indices.begin();
 146                  sit != it->second.turn_indices.end(); ++sit)
 147             {
 148                 std::cout << " "  << *sit;
 149             }
 150             std::cout << std::endl;
 151         }
 152
 153         std::cout << std::endl;
 154
 155     }
 156
 157     template <typename Turns, typename Turn, typename Operation>
 158     void visit_traverse(Turns const& turns, Turn const& turn, Operation const& op, const std::string& header)
 159     {
 160         typedef typename boost::range_value<Turns>::type turn_type;
 161
 162         if (! m_do_output)
 163         {
 164             return;
 165         }
 166
 167         std::cout << "Visit turn " << stream_turn_index(turns, turn, op)
 168                   << " " << bg::operation_char(turn.operations[0].operation)
 169                     << bg::operation_char(turn.operations[1].operation)
 170                 << " (" << bg::operation_char(op.operation) << ")"
 171                 << " "  << header << std::endl;
 172
 173         // Uncomment for more detailed debug info in SVG on traversal
 174         std::string style
 175                 = header == "Visit" ? "fill:rgb(80,80,80)" : "fill:rgb(0,0,0)";
 176
 177         style += ";font-family:Arial;font-size:6px";
 178
 179         stream(turns, turn, op, header.substr(0, 1), style);
 180     }
 181
 182     template <typename Turns, typename Turn, typename Operation>
 183     void visit_traverse_reject(Turns const& turns, Turn const& turn, Operation const& op,
 184                                bg::detail::overlay::traverse_error_type error)
 185     {
 186         if (! m_do_output)
 187         {
 188             return;
 189         }
 190         std::cout << "Reject turn " << stream_turn_index(turns, turn, op)
 191                   << bg::operation_char(turn.operations[0].operation)
 192                     << bg::operation_char(turn.operations[1].operation)
 193                 << " (" << bg::operation_char(op.operation) << ")"
 194                 << " "  << bg::detail::overlay::traverse_error_string(error) << std::endl;
 195         //return;
 196
 197         std::string style =  "fill:rgb(255,0,0);font-family:Arial;font-size:7px";
 198         stream(turns, turn, op, bg::detail::overlay::traverse_error_string(error), style);
 199
 200         m_do_output = false;
 201     }
 202
 203     template <typename Turns, typename Turn, typename Operation>
 204     void visit_traverse_select_turn_from_cluster(Turns const& turns, Turn const& turn, Operation const& op)
 205     {
 206         std::cout << "Visit turn from cluster " << stream_turn_index(turns, turn, op)
 207                   << " " << bg::operation_char(turn.operations[0].operation)
 208                     << bg::operation_char(turn.operations[1].operation)
 209                 << " (" << bg::operation_char(op.operation) << ")"
 210                 << std::endl;
 211         return;
 212     }
 213
 214     template <typename Turns, typename Turn, typename Operation>
 215     void stream(Turns const& turns, Turn const& turn, Operation const& op, const std::string& header, const std::string& style)
 216     {
 217         std::ostringstream out;
 218         out << m_traverse_seq++ << " " << header
 219             << " " << stream_turn_index(turns, turn, op);
 220
 221         out << " " << bg::visited_char(op.visited);
 222
 223         add_text(turn, out.str(), style);
 224     }
 225
 226     template <typename Turn>
 227     bool label_operation(Turn const& turn, int index, std::ostream& os)
 228     {
 229         os << bg::operation_char(turn.operations[index].operation);
 230         bool result = false;
 231         if (! turn.discarded)
 232         {
 233             if (turn.operations[index].enriched.next_ip_index != -1)
 234             {
 235                 os << "->" << turn.operations[index].enriched.next_ip_index;
 236                 if (turn.operations[index].enriched.next_ip_index != -1)
 237                 {
 238                     result = true;
 239                 }
 240             }
 241             else
 242             {
 243                 os << "->"  << turn.operations[index].enriched.travels_to_ip_index;
 244                 if (turn.operations[index].enriched.travels_to_ip_index != -1)
 245                 {
 246                     result = true;
 247                 }
 248             }
 249
 250             os << " {" << turn.operations[index].enriched.region_id
 251                << (turn.operations[index].enriched.isolated ? " ISO" : "")
 252                << "}";
 253
 254             if (! turn.operations[index].enriched.startable)
 255             {
 256                 os << "$";
 257             }
 258         }
 259
 260         return result;
 261     }
 262
 263     template <typename Turn>
 264     void label_turn(int index, Turn const& turn)
 265     {
 266         std::ostringstream out;
 267         out << index << " ";
 268         if (turn.cluster_id != -1)
 269         {
 270             out << " c=" << turn.cluster_id << " ";
 271         }
 272         bool lab1 = label_operation(turn, 0, out);
 273         out << " / ";
 274         bool lab2 = label_operation(turn, 1, out);
 275         if (turn.discarded)
 276         {
 277             out << "!";
 278         }
 279         if (turn.has_colocated_both)
 280         {
 281             out << "+";
 282         }
 283         bool const self_turn = bg::detail::overlay::is_self_turn<bg::overlay_union>(turn);
 284         if (self_turn)
 285         {
 286             out << "@";
 287         }
 288
 289         std::string font8 = "font-family:Arial;font-size:6px";
 290         std::string font6 = "font-family:Arial;font-size:4px";
 291         std::string style =  "fill:rgb(0,0,255);" + font8;
 292         if (self_turn)
 293         {
 294             if (turn.discarded)
 295             {
 296                 style =  "fill:rgb(128,28,128);" + font6;
 297             }
 298             else
 299             {
 300                 style =  "fill:rgb(255,0,255);" + font8;
 301             }
 302         }
 303         else if (turn.discarded)
 304         {
 305             style =  "fill:rgb(92,92,92);" + font6;
 306         }
 307         else if (turn.cluster_id != -1)
 308         {
 309             style =  "fill:rgb(0,0,255);" + font8;
 310         }
 311         else if (! lab1 || ! lab2)
 312         {
 313             style =  "fill:rgb(0,0,255);" + font6;
 314         }
 315
 316         add_text(turn, out.str(), style);
 317     }
 318
 319     template <typename Turn>
 320     void add_text(Turn const& turn, std::string const& text, std::string const& style)
 321     {
 322         int const margin = 5;
 323         int const lineheight = 6;
 324         double const half = 0.5;
 325         double const ten = 10;
 326
 327         // Map characteristics
 328         // Create a rounded off point
 329         std::pair<int, int> p
 330             = std::make_pair(
 331                 boost::numeric_cast<int>(half
 332                     + ten * bg::get<0>(turn.point)),
 333                 boost::numeric_cast<int>(half
 334                     + ten * bg::get<1>(turn.point))
 335                 );
 336         m_mapper.text(turn.point, text, style, margin, m_offsets[p], lineheight);
 337         m_offsets[p] += lineheight;
 338     }
 339
 340
 341     Mapper& m_mapper;
 342     std::map<std::pair<int, int>, int> m_offsets;
 343     int m_traverse_seq;
 344     bool m_do_output;
 345
 346 };
 347 #endif
 348
 349 template <typename Geometry, bg::overlay_type OverlayType>
 350 void test_overlay(std::string const& caseid,
 351         std::string const& wkt1, std::string const& wkt2,
 352         double expected_area,
 353         std::size_t expected_clip_count,
 354         std::size_t expected_hole_count)
 355 {
 356     Geometry g1;
 357     bg::read_wkt(wkt1, g1);
 358
 359     Geometry g2;
 360     bg::read_wkt(wkt2, g2);
 361
 362     // Reverse if necessary
 363     bg::correct(g1);
 364     bg::correct(g2);
 365
 366 #if defined(TEST_WITH_SVG)
 367     bool const ccw = bg::point_order<Geometry>::value == bg::counterclockwise;
 368     bool const open = bg::closure<Geometry>::value == bg::open;
 369
 370     std::ostringstream filename;
 371     filename << "overlay"
 372         << "_" << caseid
 373         << "_" << string_from_type<typename bg::coordinate_type<Geometry>::type>::name()
 374         << (ccw ? "_ccw" : "")
 375         << (open ? "_open" : "")
 376 #if defined(BOOST_GEOMETRY_USE_RESCALING)
 377         << "_rescaled"
 378 #endif
 379         << ".svg";
 380
 381     std::ofstream svg(filename.str().c_str());
 382
 383     typedef bg::svg_mapper<typename bg::point_type<Geometry>::type> svg_mapper;
 384
 385     svg_mapper mapper(svg, 500, 500);
 386     mapper.add(g1);
 387     mapper.add(g2);
 388
 389     // Input shapes in green (src=0) / blue (src=1)
 390     mapper.map(g1, "fill-opacity:0.5;fill:rgb(153,204,0);"
 391             "stroke:rgb(153,204,0);stroke-width:3");
 392     mapper.map(g2, "fill-opacity:0.3;fill:rgb(51,51,153);"
 393             "stroke:rgb(51,51,153);stroke-width:3");
 394 #endif
 395
 396
 397     typedef typename boost::range_value<Geometry>::type geometry_out;
 398     typedef bg::detail::overlay::overlay
 399         <
 400             Geometry, Geometry,
 401             bg::detail::overlay::do_reverse<bg::point_order<Geometry>::value>::value,
 402             OverlayType == bg::overlay_difference
 403             ? ! bg::detail::overlay::do_reverse<bg::point_order<Geometry>::value>::value
 404             : bg::detail::overlay::do_reverse<bg::point_order<Geometry>::value>::value,
 405             bg::detail::overlay::do_reverse<bg::point_order<Geometry>::value>::value,
 406             geometry_out,
 407             OverlayType
 408         > overlay;
 409
 410     typedef typename bg::strategy::intersection::services::default_strategy
 411         <
 412             typename bg::cs_tag<Geometry>::type
 413         >::type strategy_type;
 414
 415     strategy_type strategy;
 416
 417     typedef typename bg::rescale_overlay_policy_type
 418     <
 419         Geometry,
 420         Geometry
 421     >::type rescale_policy_type;
 422
 423     rescale_policy_type robust_policy
 424         = bg::get_rescale_policy<rescale_policy_type>(g1, g2);
 425
 426 #if defined(TEST_WITH_SVG)
 427     map_visitor<svg_mapper> visitor(mapper);
 428 #else
 429     bg::detail::overlay::overlay_null_visitor visitor;
 430 #endif
 431
 432     Geometry result;
 433     overlay::apply(g1, g2, robust_policy, std::back_inserter(result),
 434                    strategy, visitor);
 435
 436     std::string message;
 437     bool const valid = check_validity<Geometry>::apply(result, caseid, g1, g2, message);
 438     BOOST_CHECK_MESSAGE(valid,
 439         "overlay: " << caseid << " not valid: " << message
 440         << " type: " << (type_for_assert_message<Geometry, Geometry>()));
 441
 442     BOOST_CHECK_CLOSE(bg::area(result), expected_area, 0.001);
 443     BOOST_CHECK_MESSAGE((bg::num_interior_rings(result) == expected_hole_count),
 444                         caseid
 445                         << " hole count: detected: " << bg::num_interior_rings(result)
 446                         << " expected: "  << expected_hole_count);
 447     BOOST_CHECK_MESSAGE((result.size() == expected_clip_count),
 448                         caseid
 449                         << " clip count: detected: " << result.size()
 450                         << " expected: "  << expected_clip_count);
 451
 452 #if defined(TEST_WITH_SVG)
 453     mapper.map(result, "fill-opacity:0.2;stroke-opacity:0.4;fill:rgb(255,0,0);"
 454                         "stroke:rgb(255,0,255);stroke-width:8");
 455
 456 #endif
 457 }
 458
 459 #define TEST_INTERSECTION(caseid, area, clips, holes) (test_overlay<multi_polygon, bg::overlay_intersection>) \
 460     ( #caseid "_int", caseid[0], caseid[1], area, clips, holes)
 461 #define TEST_UNION(caseid, area, clips, holes) (test_overlay<multi_polygon, bg::overlay_union>) \
 462     ( #caseid "_union", caseid[0], caseid[1], area, clips, holes)
 463 #define TEST_DIFFERENCE_A(caseid, area, clips, holes) (test_overlay<multi_polygon, bg::overlay_difference>) \
 464     ( #caseid "_diff_a", caseid[0], caseid[1], area, clips, holes)
 465 #define TEST_DIFFERENCE_B(caseid, area, clips, holes) (test_overlay<multi_polygon, bg::overlay_difference>) \
 466     ( #caseid "_diff_b", caseid[1], caseid[0], area, clips, holes)
 467
 468 #define TEST_INTERSECTION_WITH(caseid, index1, index2, area, clips, holes) (test_overlay<multi_polygon, bg::overlay_intersection>) \
 469     ( #caseid "_int_" #index1 "_" #index2, caseid[index1], caseid[index2], area, clips, holes)
 470 #define TEST_UNION_WITH(caseid, index1, index2, area, clips, holes) (test_overlay<multi_polygon, bg::overlay_union>) \
 471     ( #caseid "_union" #index1 "_" #index2, caseid[index1], caseid[index2], area, clips, holes)
 472
 473 template <typename T, bool Clockwise>
 474 void test_all()
 475 {
 476     typedef bg::model::point<T, 2, bg::cs::cartesian> point_type;
 477     typedef bg::model::polygon<point_type, Clockwise> polygon;
 478     typedef bg::model::multi_polygon<polygon> multi_polygon;
 479
 480     TEST_UNION(case_multi_simplex, 14.58, 1, 0);
 481     TEST_INTERSECTION(case_multi_simplex, 6.42, 2, 0);
 482
 483     TEST_DIFFERENCE_A(case_multi_simplex, 5.58, 5, 0);
 484     TEST_DIFFERENCE_B(case_multi_simplex, 2.58, 4, 0);
 485
 486     // Contains 5 clusters, needing immediate selection of next turn
 487     TEST_UNION_WITH(case_58_multi, 0, 3, 19.8333333, 2, 0);
 488
 489     // Contains many clusters, needing to exclude u/u turns
 490     TEST_UNION(case_recursive_boxes_3, 56.5, 17, 6);
 491
 492     // Contains 4 clusters, one of which having 4 turns
 493     TEST_UNION(case_recursive_boxes_7, 7.0, 2, 0);
 494
 495     // Contains 5 clusters, needing immediate selection of next turn
 496     TEST_UNION(case_89_multi, 6.0, 1, 0);
 497
 498     // Needs ux/next_turn_index==-1 to be filtered out
 499     TEST_INTERSECTION(case_77_multi, 9.0, 5, 0);
 500     TEST_UNION(case_101_multi, 22.25, 1, 3);
 501     TEST_INTERSECTION(case_101_multi, 4.75, 4, 0);
 502
 503     TEST_INTERSECTION(case_recursive_boxes_11, 1.0, 2, 0);
 504     TEST_INTERSECTION(case_recursive_boxes_30, 6.0, 4, 0);
 505
 506     TEST_UNION(case_recursive_boxes_4, 96.75, 1, 2);
 507     TEST_INTERSECTION_WITH(case_58_multi, 2, 6, 13.25, 1, 1);
 508     TEST_INTERSECTION_WITH(case_72_multi, 1, 2, 6.15, 3, 1);
 509     TEST_UNION(case_recursive_boxes_12, 6.0, 6, 0);
 510     TEST_UNION(case_recursive_boxes_13, 10.25, 3, 0);
 511
 512
 513 //    std::cout
 514 //        << "    \""
 515 //        << bg::inverse<multi_polygon>(case_65_multi[0], 1.0)
 516 //        << "\"" << std::endl;
 517 }
 518
 519 int test_main(int, char* [])
 520 {
 521     test_all<double, true>();
 522 //    test_all<double, false>();
 523     return 0;
 524  }