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

   1 // Boost.Geometry (aka GGL, Generic Geometry Library)
   2 // Unit Test
   3
   4 // Copyright (c) 2016 Barend Gehrels, Amsterdam, the Netherlands.
   5 // Copyright (c) 2017 Adam Wulkiewicz, Lodz, Poland.
   6
   7 // This file was modified by Oracle on 2017, 2019.
   8 // Modifications copyright (c) 2017, 2019, 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.hpp>
  18 #include <boost/geometry/algorithms/detail/overlay/debug_turn_info.hpp>
  19 #include <boost/geometry/geometries/geometries.hpp>
  20 #include <boost/assign/list_of.hpp>
  21 #include <boost/foreach.hpp>
  22
  23 #include "multi_overlay_cases.hpp"
  24
  25
  26 namespace
  27 {
  28
  29 template <typename T>
  30 std::string as_string(std::vector<T> const& v)
  31 {
  32     std::stringstream out;
  33     bool first = true;
  34     BOOST_FOREACH(T const& value, v)
  35     {
  36         out << (first ? "[" : " , ") << value;
  37         first = false;
  38     }
  39     out << (first ? "" : "]");
  40     return out.str();
  41 }
  42
  43 }
  44
  45 // Adapted copy of handle_colocations::gather_cluster_properties
  46 template
  47 <
  48     bool Reverse1, bool Reverse2,
  49     bg::overlay_type OverlayType,
  50     typename Clusters,
  51     typename Turns,
  52     typename Geometry1,
  53     typename Geometry2,
  54     typename SideStrategy
  55 >
  56 std::vector<std::size_t> gather_cluster_properties(
  57         Clusters& clusters, Turns& turns,
  58         bg::detail::overlay::operation_type for_operation,
  59         Geometry1 const& geometry1, Geometry2 const& geometry2,
  60         SideStrategy const& strategy)
  61 {
  62     using namespace boost::geometry;
  63     using namespace boost::geometry::detail::overlay;
  64
  65     std::vector<std::size_t> result;
  66
  67     typedef typename boost::range_value<Turns>::type turn_type;
  68     typedef typename turn_type::point_type point_type;
  69     typedef typename turn_type::turn_operation_type turn_operation_type;
  70
  71     // Define sorter, sorting counter-clockwise such that polygons are on the
  72     // right side
  73     typedef sort_by_side::side_sorter
  74         <
  75             Reverse1, Reverse2, OverlayType, point_type, SideStrategy, std::less<int>
  76         > sbs_type;
  77
  78     for (typename Clusters::iterator mit = clusters.begin();
  79          mit != clusters.end(); ++mit)
  80     {
  81         cluster_info& cinfo = mit->second;
  82         std::set<signed_size_type> const& ids = cinfo.turn_indices;
  83         if (ids.empty())
  84         {
  85             return result;
  86         }
  87
  88         sbs_type sbs(strategy);
  89         point_type turn_point; // should be all the same for all turns in cluster
  90
  91         bool first = true;
  92         for (typename std::set<signed_size_type>::const_iterator sit = ids.begin();
  93              sit != ids.end(); ++sit)
  94         {
  95             signed_size_type turn_index = *sit;
  96             turn_type const& turn = turns[turn_index];
  97             if (first)
  98             {
  99                 turn_point = turn.point;
 100             }
 101             for (int i = 0; i < 2; i++)
 102             {
 103                 turn_operation_type const& op = turn.operations[i];
 104                 sbs.add(op, turn_index, i, geometry1, geometry2, first);
 105                 first = false;
 106             }
 107         }
 108         sbs.apply(turn_point);
 109
 110         sbs.find_open();
 111         sbs.assign_zones(for_operation);
 112
 113         cinfo.open_count = sbs.open_count(for_operation);
 114         result.push_back(cinfo.open_count);
 115     }
 116     return result;
 117 }
 118
 119
 120 // Adapted copy of overlay::apply
 121 template
 122 <
 123     bg::overlay_type OverlayType,
 124     bool Reverse1, bool Reverse2, bool ReverseOut,
 125     typename GeometryOut,
 126     typename Geometry1, typename Geometry2,
 127     typename RobustPolicy, typename Strategy
 128 >
 129 std::vector<std::size_t> apply_overlay(
 130             Geometry1 const& geometry1, Geometry2 const& geometry2,
 131             RobustPolicy const& robust_policy,
 132             Strategy const& strategy)
 133 {
 134     using namespace boost::geometry;
 135
 136     typedef typename bg::point_type<GeometryOut>::type point_type;
 137     typedef bg::detail::overlay::traversal_turn_info
 138     <
 139         point_type,
 140         typename bg::detail::segment_ratio_type<point_type, RobustPolicy>::type
 141     > turn_info;
 142     typedef std::deque<turn_info> turn_container_type;
 143
 144     // Define the clusters, mapping cluster_id -> turns
 145     typedef std::map
 146         <
 147             signed_size_type,
 148             bg::detail::overlay::cluster_info
 149         > cluster_type;
 150
 151     turn_container_type turns;
 152
 153     detail::get_turns::no_interrupt_policy policy;
 154     bg::get_turns
 155         <
 156             Reverse1, Reverse2,
 157             detail::overlay::assign_null_policy
 158         >(geometry1, geometry2, strategy, robust_policy, turns, policy);
 159
 160     cluster_type clusters;
 161
 162     bg::enrich_intersection_points<Reverse1, Reverse2, OverlayType>(turns,
 163             clusters, geometry1, geometry2, robust_policy, strategy);
 164
 165     // Gather cluster properties, with test option
 166     return ::gather_cluster_properties<Reverse1, Reverse2, OverlayType>(
 167             clusters, turns, bg::detail::overlay::operation_from_overlay<OverlayType>::value,
 168                 geometry1, geometry2, strategy.get_side_strategy());
 169 }
 170
 171
 172 template <typename Geometry, bg::overlay_type OverlayType>
 173 void test_sort_by_side(std::string const& case_id,
 174         std::string const& wkt1, std::string const& wkt2,
 175         std::vector<std::size_t> const& expected_open_count)
 176 {
 177 //    std::cout << case_id << std::endl;
 178
 179     Geometry g1;
 180     bg::read_wkt(wkt1, g1);
 181
 182     Geometry g2;
 183     bg::read_wkt(wkt2, g2);
 184
 185     // Reverse if necessary
 186     bg::correct(g1);
 187     bg::correct(g2);
 188
 189     typedef typename boost::range_value<Geometry>::type geometry_out;
 190
 191     typedef typename bg::rescale_overlay_policy_type
 192     <
 193         Geometry,
 194         Geometry
 195     >::type rescale_policy_type;
 196
 197     rescale_policy_type robust_policy
 198         = bg::get_rescale_policy<rescale_policy_type>(g1, g2);
 199
 200     typedef typename bg::strategy::intersection::services::default_strategy
 201         <
 202             typename bg::cs_tag<Geometry>::type
 203         >::type strategy_type;
 204
 205     strategy_type strategy;
 206
 207     std::vector<std::size_t> result = ::apply_overlay
 208                                         <
 209                                             OverlayType, false, false, false, geometry_out
 210                                         >(g1, g2, robust_policy, strategy);
 211
 212     BOOST_CHECK_MESSAGE(result == expected_open_count,
 213                         "  caseid="  << case_id
 214                         << " open count: expected="  << as_string(expected_open_count)
 215                         << " detected="  << as_string(result));
 216 }
 217
 218
 219 // Define two small macro's to avoid repetitions of testcases/names etc
 220 #define TEST_INT(caseid, exp) { (test_sort_by_side<multi_polygon, bg::overlay_intersection>) \
 221     ( #caseid "_int", caseid[0], caseid[1], exp); }
 222
 223 #define TEST_UNION(caseid, exp) { (test_sort_by_side<multi_polygon, bg::overlay_union>) \
 224     ( #caseid "_union", caseid[0], caseid[1], exp); }
 225
 226 using boost::assign::list_of;
 227
 228 template <typename T>
 229 void test_all()
 230 {
 231     typedef bg::model::point<T, 2, bg::cs::cartesian> point_type;
 232     typedef bg::model::polygon<point_type> polygon;
 233     typedef bg::model::multi_polygon<polygon> multi_polygon;
 234
 235     // Selection of test cases having only one cluster
 236
 237     TEST_INT(case_64_multi, list_of(1));
 238     TEST_INT(case_72_multi, list_of(3));
 239     TEST_INT(case_107_multi, list_of(2));
 240     TEST_INT(case_123_multi, list_of(3));
 241     TEST_INT(case_124_multi, list_of(3));
 242     TEST_INT(case_recursive_boxes_10, list_of(2));
 243     TEST_INT(case_recursive_boxes_20, list_of(2));
 244     TEST_INT(case_recursive_boxes_21, list_of(1));
 245     TEST_INT(case_recursive_boxes_22, list_of(0));
 246
 247     TEST_UNION(case_recursive_boxes_46, list_of(2)(1)(2)(1)(1)(2)(1));
 248
 249     TEST_UNION(case_62_multi, list_of(2));
 250     TEST_UNION(case_63_multi, list_of(2));
 251     TEST_UNION(case_64_multi, list_of(1));
 252     TEST_UNION(case_107_multi, list_of(1));
 253     TEST_UNION(case_123_multi, list_of(1));
 254     TEST_UNION(case_124_multi, list_of(1));
 255     TEST_UNION(case_recursive_boxes_10, list_of(1));
 256     TEST_UNION(case_recursive_boxes_18, list_of(3));
 257     TEST_UNION(case_recursive_boxes_19, list_of(3));
 258     TEST_UNION(case_recursive_boxes_20, list_of(2));
 259     TEST_UNION(case_recursive_boxes_21, list_of(1));
 260     TEST_UNION(case_recursive_boxes_22, list_of(1));
 261     TEST_UNION(case_recursive_boxes_23, list_of(3));
 262 }
 263
 264 int test_main(int, char* [])
 265 {
 266     test_all<double>();
 267     return 0;
 268 }