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

   1 // Boost.Geometry (aka GGL, Generic Geometry Library)
   2 // Unit Test
   3
   4 // Copyright (c) 2017 Barend Gehrels, Amsterdam, the Netherlands.
   5 // Copyright (c) 2017 Adam Wulkiewicz, Lodz, Poland.
   6
   7 // This file was modified by Oracle on 2017.
   8 // Modifications copyright (c) 2017, Oracle and/or its affiliates.
   9 // Contributed and/or modified by Adam Wulkiewicz, on behalf of Oracle
  10
  11 // Use, modification and distribution is subject to the Boost Software License,
  12 // Version 1.0. (See accompanying file LICENSE_1_0.txt or copy at
  13 // http://www.boost.org/LICENSE_1_0.txt)
  14
  15 #include <geometry_test_common.hpp>
  16
  17 #include <boost/geometry/algorithms/detail/overlay/sort_by_side.hpp>
  18
  19 #include <boost/geometry/strategies/strategies.hpp>  // for equals/within
  20 #include <boost/geometry/algorithms/detail/overlay/get_turns.hpp>
  21 #include <boost/geometry/algorithms/detail/overlay/debug_turn_info.hpp>
  22 #include <boost/geometry/algorithms/correct.hpp>
  23 #include <boost/geometry/algorithms/equals.hpp>
  24 #include <boost/geometry/io/wkt/wkt.hpp>
  25 #include <boost/geometry/geometries/geometries.hpp>
  26
  27 #include <boost/assign/list_of.hpp>
  28 #include <boost/foreach.hpp>
  29
  30 #if defined(TEST_WITH_SVG)
  31 #include "debug_sort_by_side_svg.hpp"
  32 #endif
  33
  34 namespace
  35 {
  36
  37
  38 template <typename T>
  39 std::string as_string(std::vector<T> const& v)
  40 {
  41     std::stringstream out;
  42     bool first = true;
  43     BOOST_FOREACH(T const& value, v)
  44     {
  45         out << (first ? "[" : " , ") << value;
  46         first = false;
  47     }
  48     out << (first ? "" : "]");
  49     return out.str();
  50 }
  51
  52 }
  53
  54 template
  55 <
  56     typename Geometry, typename Point,
  57     typename RobustPolicy, typename Strategy
  58 >
  59 std::vector<std::size_t> apply_get_turns(std::string const& case_id,
  60             Geometry const& geometry1, Geometry const& geometry2,
  61             Point const& turn_point, Point const& origin_point,
  62             RobustPolicy const& robust_policy,
  63             Strategy const& strategy,
  64             std::size_t expected_open_count,
  65             std::size_t expected_max_rank,
  66             std::vector<bg::signed_size_type> const& expected_right_count)
  67 {
  68     using namespace boost::geometry;
  69
  70     std::vector<std::size_t> result;
  71
  72 //todo: maybe should be enriched to count left/right - but can also be counted from ranks
  73     typedef typename bg::point_type<Geometry>::type point_type;
  74     typedef bg::detail::overlay::turn_info
  75     <
  76         point_type,
  77         typename bg::detail::segment_ratio_type<point_type, RobustPolicy>::type
  78     > turn_info;
  79     typedef std::deque<turn_info> turn_container_type;
  80
  81     turn_container_type turns;
  82
  83     detail::get_turns::no_interrupt_policy policy;
  84     bg::get_turns
  85         <
  86             false, false,
  87             detail::overlay::assign_null_policy
  88         >(geometry1, geometry2, strategy, robust_policy, turns, policy);
  89
  90
  91     // Define sorter, sorting counter-clockwise such that polygons are on the
  92     // right side
  93     typedef typename Strategy::side_strategy_type side_strategy;
  94     typedef bg::detail::overlay::sort_by_side::side_sorter
  95         <
  96             false, false, overlay_union,
  97             point_type, side_strategy, std::less<int>
  98         > sbs_type;
  99
 100     sbs_type sbs(strategy.get_side_strategy());
 101
 102     std::cout << "Case: " << case_id << std::endl;
 103
 104     bool has_origin = false;
 105     for (std::size_t turn_index = 0; turn_index < turns.size(); turn_index++)
 106     {
 107         turn_info const& turn = turns[turn_index];
 108
 109         if (bg::equals(turn.point, turn_point))
 110         {
 111 //            std::cout << "Found turn: " << turn_index << std::endl;
 112             for (int i = 0; i < 2; i++)
 113             {
 114                 Point point1, point2, point3;
 115                 bg::copy_segment_points<false, false>(geometry1, geometry2,
 116                         turn.operations[i].seg_id, point1, point2, point3);
 117                 bool const is_origin = ! has_origin && bg::equals(point1, origin_point);
 118                 if (is_origin)
 119                 {
 120                     has_origin = true;
 121                 }
 122
 123                 sbs.add(turn.operations[i], turn_index, i,
 124                         geometry1, geometry2, is_origin);
 125
 126             }
 127         }
 128     }
 129
 130     BOOST_CHECK_MESSAGE(has_origin,
 131                         "  caseid="  << case_id
 132                         << " origin not found");
 133
 134     if (!has_origin)
 135     {
 136         for (std::size_t turn_index = 0; turn_index < turns.size(); turn_index++)
 137         {
 138             turn_info const& turn = turns[turn_index];
 139             if (bg::equals(turn.point, turn_point))
 140             {
 141                 for (int i = 0; i < 2; i++)
 142                 {
 143                     Point point1, point2, point3;
 144                     bg::copy_segment_points<false, false>(geometry1, geometry2,
 145                             turn.operations[i].seg_id, point1, point2, point3);
 146 //                    std::cout << "Turn " << turn_index << " op " << i << " point1=" << bg::wkt(point1) << std::endl;
 147                 }
 148             }
 149         }
 150         return result;
 151     }
 152
 153
 154     sbs.apply(turn_point);
 155
 156     sbs.find_open();
 157     sbs.assign_zones(detail::overlay::operation_union);
 158
 159     std::size_t const open_count = sbs.open_count(detail::overlay::operation_union);
 160     std::size_t const max_rank = sbs.m_ranked_points.back().rank;
 161     std::vector<bg::signed_size_type> right_count(max_rank + 1, -1);
 162
 163     int previous_rank = -1;
 164     int previous_to_rank = -1;
 165     for (std::size_t i = 0; i < sbs.m_ranked_points.size(); i++)
 166     {
 167         typename sbs_type::rp const& ranked_point = sbs.m_ranked_points[i];
 168
 169         int const rank = static_cast<int>(ranked_point.rank);
 170         bool const set_right = rank != previous_to_rank;
 171         if (rank != previous_rank)
 172         {
 173             BOOST_CHECK_MESSAGE(rank == previous_rank + 1,
 174                                 "  caseid="  << case_id
 175                                 << " ranks: conflict in ranks="  << ranked_point.rank
 176                                 << " vs " << previous_rank + 1);
 177             previous_rank = rank;
 178         }
 179
 180         if (ranked_point.direction != bg::detail::overlay::sort_by_side::dir_to)
 181         {
 182             continue;
 183         }
 184
 185         previous_to_rank = rank;
 186         if (set_right)
 187         {
 188             right_count[rank] = ranked_point.count_right;
 189         }
 190         else
 191         {
 192             BOOST_CHECK_MESSAGE(right_count[rank] == int(ranked_point.count_right),
 193                                 "  caseid="  << case_id
 194                                 << " ranks: conflict in right_count="  << ranked_point.count_right
 195                                 << " vs " << right_count[rank]);
 196         }
 197
 198     }
 199     BOOST_CHECK_MESSAGE(open_count == expected_open_count,
 200                         "  caseid="  << case_id
 201                         << " open_count: expected="  << expected_open_count
 202                         << " detected="  << open_count);
 203
 204     BOOST_CHECK_MESSAGE(max_rank == expected_max_rank,
 205                         "  caseid="  << case_id
 206                         << " max_rank: expected="  << expected_max_rank
 207                         << " detected="  << max_rank);
 208
 209     BOOST_CHECK_MESSAGE(right_count == expected_right_count,
 210                         "  caseid="  << case_id
 211                         << " right count: expected="  << as_string(expected_right_count)
 212                         << " detected="  << as_string(right_count));
 213
 214 #if defined(TEST_WITH_SVG)
 215     debug::sorted_side_map(case_id, sbs, turn_point, geometry1, geometry2);
 216 #endif
 217
 218     return result;
 219 }
 220
 221
 222 template <typename T>
 223 void test_basic(std::string const& case_id,
 224                 std::string const& wkt1,
 225                 std::string const& wkt2,
 226                 std::string const& wkt_turn_point,
 227                 std::string const& wkt_origin_point,
 228                 std::size_t expected_open_count,
 229                 std::size_t expected_max_rank,
 230                 std::vector<bg::signed_size_type> const& expected_right_count)
 231 {
 232     typedef bg::model::point<T, 2, bg::cs::cartesian> point_type;
 233     typedef bg::model::polygon<point_type> polygon;
 234     typedef bg::model::multi_polygon<polygon> multi_polygon;
 235
 236     multi_polygon g1;
 237     bg::read_wkt(wkt1, g1);
 238
 239     multi_polygon g2;
 240     bg::read_wkt(wkt2, g2);
 241
 242     point_type turn_point, origin_point;
 243     bg::read_wkt(wkt_turn_point, turn_point);
 244     bg::read_wkt(wkt_origin_point, origin_point);
 245
 246     // Reverse if necessary
 247     bg::correct(g1);
 248     bg::correct(g2);
 249
 250     typedef typename bg::rescale_overlay_policy_type
 251     <
 252         multi_polygon,
 253         multi_polygon
 254     >::type rescale_policy_type;
 255
 256     rescale_policy_type robust_policy
 257         = bg::get_rescale_policy<rescale_policy_type>(g1, g2);
 258
 259     typedef typename bg::strategy::intersection::services::default_strategy
 260         <
 261             typename bg::cs_tag<point_type>::type
 262         >::type strategy_type;
 263
 264     strategy_type strategy;
 265
 266     apply_get_turns(case_id, g1, g2, turn_point, origin_point,
 267         robust_policy, strategy,
 268         expected_open_count, expected_max_rank, expected_right_count);
 269 }
 270
 271 using boost::assign::list_of;
 272
 273 template <typename T>
 274 void test_all()
 275 {
 276     test_basic<T>("simplex",
 277       "MULTIPOLYGON(((0 2,1 2,1 1,0 1,0 2)))",
 278       "MULTIPOLYGON(((1 0,1 1,2 1,2 0,1, 0)))",
 279       "POINT(1 1)", "POINT(1 0)",
 280       2, 3, list_of(-1)(1)(-1)(1));
 281
 282     test_basic<T>("dup1",
 283       "MULTIPOLYGON(((0 2,1 2,1 1,0 1,0 2)))",
 284       "MULTIPOLYGON(((1 0,1 1,2 1,2 0,1, 0)),((0 2,1 2,1 1,0 1,0 2)))",
 285       "POINT(1 1)", "POINT(1 0)",
 286       2, 3, list_of(-1)(1)(-1)(2));
 287
 288     test_basic<T>("dup2",
 289       "MULTIPOLYGON(((0 2,1 2,1 1,0 1,0 2)),((1 0,1 1,2 1,2 0,1, 0)))",
 290       "MULTIPOLYGON(((1 0,1 1,2 1,2 0,1, 0)))",
 291       "POINT(1 1)", "POINT(1 0)",
 292       2, 3, list_of(-1)(2)(-1)(1));
 293
 294     test_basic<T>("dup3",
 295       "MULTIPOLYGON(((0 2,1 2,1 1,0 1,0 2)),((1 0,1 1,2 1,2 0,1, 0)))",
 296       "MULTIPOLYGON(((1 0,1 1,2 1,2 0,1, 0)),((0 2,1 2,1 1,0 1,0 2)))",
 297       "POINT(1 1)", "POINT(1 0)",
 298       2, 3, list_of(-1)(2)(-1)(2));
 299
 300     test_basic<T>("threequart1",
 301       "MULTIPOLYGON(((0 2,1 2,1 1,0 1,0 2)),((1 0,1 1,2 1,2 0,1, 0)))",
 302       "MULTIPOLYGON(((1 2,2 2,2 1,1 1,1 2)))",
 303       "POINT(1 1)", "POINT(1 0)",
 304       1, 3, list_of(-1)(1)(1)(1));
 305
 306     test_basic<T>("threequart2",
 307       "MULTIPOLYGON(((0 2,1 2,1 1,0 1,0 2)),((1 0,1 1,2 1,2 0,1, 0)))",
 308       "MULTIPOLYGON(((1 2,2 2,2 1,1 1,1 2)),((2 0,1 0,1 1,2 0)))",
 309       "POINT(1 1)", "POINT(1 0)",
 310       1, 4, list_of(-1)(2)(1)(1)(1));
 311
 312     test_basic<T>("threequart3",
 313       "MULTIPOLYGON(((0 2,1 2,1 1,0 1,0 2)),((1 0,1 1,2 1,2 0,1, 0)))",
 314       "MULTIPOLYGON(((1 2,2 2,2 1,1 1,1 2)),((2 0,1 0,1 1,2 0)),((0 1,0 2,1 1,0 1)))",
 315       "POINT(1 1)", "POINT(1 0)",
 316       1, 5, list_of(-1)(2)(1)(1)(-1)(2));
 317
 318     test_basic<T>("full1",
 319       "MULTIPOLYGON(((0 2,1 2,1 1,0 1,0 2)),((1 0,1 1,2 1,2 0,1, 0)))",
 320       "MULTIPOLYGON(((1 2,2 2,2 1,1 1,1 2)),((0 0,0 1,1 1,1 0,0 0)))",
 321       "POINT(1 1)", "POINT(1 0)",
 322       0, 3, list_of(1)(1)(1)(1));
 323
 324     test_basic<T>("hole1",
 325       "MULTIPOLYGON(((0 0,0 3,2 3,2 2,3 2,3 0,0 0),(1 1,2 1,2 2,1 2,1 1)),((4 2,3 2,3 3,4 3,4 2)))",
 326       "MULTIPOLYGON(((1 0,1 1,2 1,2 2,1 2,1 4,4 4,4 0,1, 0),(3 2,3 3,2 3,2 2,3 2)))",
 327       "POINT(1 2)", "POINT(2 2)",
 328       1, 2, list_of(-1)(2)(1));
 329
 330     test_basic<T>("hole2",
 331       "MULTIPOLYGON(((0 0,0 3,2 3,2 2,3 2,3 0,0 0),(1 1,2 1,2 2,1 2,1 1)),((4 2,3 2,3 3,4 3,4 2)))",
 332       "MULTIPOLYGON(((1 0,1 1,2 1,2 2,1 2,1 4,4 4,4 0,1, 0),(3 2,3 3,2 3,2 2,3 2)))",
 333       "POINT(2 2)", "POINT(2 1)",
 334       2, 3, list_of(-1)(2)(-1)(2));
 335
 336     test_basic<T>("hole3",
 337       "MULTIPOLYGON(((0 0,0 3,2 3,2 2,3 2,3 0,0 0),(1 1,2 1,2 2,1 2,1 1)),((4 2,3 2,3 3,4 3,4 2)))",
 338       "MULTIPOLYGON(((1 0,1 1,2 1,2 2,1 2,1 4,4 4,4 0,1, 0),(3 2,3 3,2 3,2 2,3 2)))",
 339       "POINT(3 2)", "POINT(2 2)",
 340       1, 3, list_of(-1)(2)(-1)(2));
 341 }
 342
 343
 344 int test_main(int, char* [])
 345 {
 346     test_all<double>();
 347     return 0;
 348 }