ceph/src/boost/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
   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 #include <geometry_test_common.hpp>
  15
  16 #include <boost/geometry.hpp>
  17 #include <boost/geometry/algorithms/detail/overlay/debug_turn_info.hpp>
  18 #include <boost/geometry/geometries/geometries.hpp>
  19 #include <boost/assign/list_of.hpp>
  20 #include <boost/foreach.hpp>
  21
  22 #include "multi_overlay_cases.hpp"
  23
  24
  25 namespace
  26 {
  27
  28 template <typename T>
  29 std::string as_string(std::vector<T> const& v)
  30 {
  31     std::stringstream out;
  32     bool first = true;
  33     BOOST_FOREACH(T const& value, v)
  34     {
  35         out << (first ? "[" : " , ") << value;
  36         first = false;
  37     }
  38     out << (first ? "" : "]");
  39     return out.str();
  40 }
  41
  42 }
  43
  44 // Adapted copy of handle_colocations::gather_cluster_properties
  45 template
  46 <
  47     bool Reverse1, bool Reverse2,
  48     bg::overlay_type OverlayType,
  49     typename Turns,
  50     typename Clusters,
  51     typename Geometry1,
  52     typename Geometry2,
  53     typename SideStrategy
  54 >
  55 std::vector<std::size_t> test_gather_cluster_properties(std::string const& case_id,
  56         Clusters& clusters, Turns& turns,
  57         bg::detail::overlay::operation_type for_operation,
  58         Geometry1 const& geometry1, Geometry2 const& geometry2,
  59         SideStrategy const& strategy)
  60 {
  61     using namespace boost::geometry;
  62     using namespace boost::geometry::detail::overlay;
  63
  64     std::vector<std::size_t> result;
  65
  66     typedef typename boost::range_value<Turns>::type turn_type;
  67     typedef typename turn_type::point_type point_type;
  68     typedef typename turn_type::turn_operation_type turn_operation_type;
  69
  70     // Define sorter, sorting counter-clockwise such that polygons are on the
  71     // right side
  72     typedef sort_by_side::side_sorter
  73         <
  74             Reverse1, Reverse2, OverlayType, point_type, SideStrategy, std::less<int>
  75         > sbs_type;
  76
  77     for (typename Clusters::iterator mit = clusters.begin();
  78          mit != clusters.end(); ++mit)
  79     {
  80         cluster_info& cinfo = mit->second;
  81         std::set<signed_size_type> const& ids = cinfo.turn_indices;
  82         if (ids.empty())
  83         {
  84             return result;
  85         }
  86
  87         sbs_type sbs(strategy);
  88         point_type turn_point; // should be all the same for all turns in cluster
  89
  90         bool first = true;
  91         for (typename std::set<signed_size_type>::const_iterator sit = ids.begin();
  92              sit != ids.end(); ++sit)
  93         {
  94             signed_size_type turn_index = *sit;
  95             turn_type const& turn = turns[turn_index];
  96             if (first)
  97             {
  98                 turn_point = turn.point;
  99             }
 100             for (int i = 0; i < 2; i++)
 101             {
 102                 turn_operation_type const& op = turn.operations[i];
 103                 sbs.add(op, turn_index, i, geometry1, geometry2, first);
 104                 first = false;
 105             }
 106         }
 107         sbs.apply(turn_point);
 108
 109         sbs.find_open();
 110         sbs.assign_zones(for_operation);
 111
 112         cinfo.open_count = sbs.open_count(for_operation);
 113         result.push_back(cinfo.open_count);
 114     }
 115     return result;
 116 }
 117
 118
 119 // Adapted copy of overlay::apply
 120 template
 121 <
 122     bg::overlay_type OverlayType,
 123     bool Reverse1, bool Reverse2, bool ReverseOut,
 124     typename GeometryOut,
 125     typename Geometry1, typename Geometry2,
 126     typename RobustPolicy, typename Strategy
 127 >
 128 std::vector<std::size_t> apply_overlay(std::string const& case_id,
 129             Geometry1 const& geometry1, Geometry2 const& geometry2,
 130             RobustPolicy const& robust_policy,
 131             Strategy const& strategy)
 132 {
 133     using namespace boost::geometry;
 134
 135     typedef typename bg::point_type<GeometryOut>::type point_type;
 136     typedef bg::detail::overlay::traversal_turn_info
 137     <
 138         point_type,
 139         typename bg::segment_ratio_type<point_type, RobustPolicy>::type
 140     > turn_info;
 141     typedef std::deque<turn_info> turn_container_type;
 142
 143     // Define the clusters, mapping cluster_id -> turns
 144     typedef std::map
 145         <
 146             signed_size_type,
 147             bg::detail::overlay::cluster_info
 148         > cluster_type;
 149
 150     turn_container_type turns;
 151
 152     detail::get_turns::no_interrupt_policy policy;
 153     bg::get_turns
 154         <
 155             Reverse1, Reverse2,
 156             detail::overlay::assign_null_policy
 157         >(geometry1, geometry2, strategy, robust_policy, turns, policy);
 158
 159     typename Strategy::side_strategy_type side_strategy;
 160     cluster_type clusters;
 161
 162     bg::enrich_intersection_points<Reverse1, Reverse2, OverlayType>(turns,
 163             clusters, geometry1, geometry2,
 164                 robust_policy,
 165                 side_strategy);
 166
 167     // Gather cluster properties, with test option
 168     return test_gather_cluster_properties<Reverse1, Reverse2, OverlayType>(case_id,
 169             clusters, turns, bg::detail::overlay::operation_from_overlay<OverlayType>::value,
 170                 geometry1, geometry2, strategy.get_side_strategy());
 171 }
 172
 173
 174 template <typename Geometry, bg::overlay_type OverlayType>
 175 void test_sort_by_side(std::string const& case_id,
 176         std::string const& wkt1, std::string const& wkt2,
 177         std::vector<std::size_t> const& expected_open_count)
 178 {
 179 //    std::cout << case_id << std::endl;
 180
 181     Geometry g1;
 182     bg::read_wkt(wkt1, g1);
 183
 184     Geometry g2;
 185     bg::read_wkt(wkt2, g2);
 186
 187     // Reverse if necessary
 188     bg::correct(g1);
 189     bg::correct(g2);
 190
 191     typedef typename boost::range_value<Geometry>::type geometry_out;
 192
 193     typedef typename bg::rescale_overlay_policy_type
 194     <
 195         Geometry,
 196         Geometry
 197     >::type rescale_policy_type;
 198
 199     rescale_policy_type robust_policy
 200         = bg::get_rescale_policy<rescale_policy_type>(g1, g2);
 201
 202     typedef typename bg::strategy::intersection::services::default_strategy
 203         <
 204             typename bg::cs_tag<Geometry>::type
 205         >::type strategy_type;
 206
 207     strategy_type strategy;
 208
 209     std::vector<std::size_t> result = apply_overlay<OverlayType, false, false, false, geometry_out>(case_id, g1, g2,
 210                     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 }