ceph/src/boost/boost/geometry/algorithms/detail/overlay/overlay.hpp

   1 // Boost.Geometry (aka GGL, Generic Geometry Library)
   2
   3 // Copyright (c) 2007-2015 Barend Gehrels, Amsterdam, the Netherlands.
   4 // Copyright (c) 2013-2015 Adam Wulkiewicz, Lodz, Poland
   5
   6 // This file was modified by Oracle on 2015, 2017.
   7 // Modifications copyright (c) 2015-2017, Oracle and/or its affiliates.
   8
   9 // Contributed and/or modified by Menelaos Karavelas, on behalf of Oracle
  10 // Contributed and/or modified by Adam Wulkiewicz, on behalf of Oracle
  11
  12 // Use, modification and distribution is subject to the Boost Software License,
  13 // Version 1.0. (See accompanying file LICENSE_1_0.txt or copy at
  14 // http://www.boost.org/LICENSE_1_0.txt)
  15
  16 #ifndef BOOST_GEOMETRY_ALGORITHMS_DETAIL_OVERLAY_OVERLAY_HPP
  17 #define BOOST_GEOMETRY_ALGORITHMS_DETAIL_OVERLAY_OVERLAY_HPP
  18
  19
  20 #include <deque>
  21 #include <map>
  22
  23 #include <boost/range.hpp>
  24 #include <boost/mpl/assert.hpp>
  25
  26
  27 #include <boost/geometry/algorithms/detail/overlay/cluster_info.hpp>
  28 #include <boost/geometry/algorithms/detail/overlay/enrich_intersection_points.hpp>
  29 #include <boost/geometry/algorithms/detail/overlay/enrichment_info.hpp>
  30 #include <boost/geometry/algorithms/detail/overlay/get_turns.hpp>
  31 #include <boost/geometry/algorithms/detail/overlay/is_self_turn.hpp>
  32 #include <boost/geometry/algorithms/detail/overlay/needs_self_turns.hpp>
  33 #include <boost/geometry/algorithms/detail/overlay/overlay_type.hpp>
  34 #include <boost/geometry/algorithms/detail/overlay/traverse.hpp>
  35 #include <boost/geometry/algorithms/detail/overlay/traversal_info.hpp>
  36 #include <boost/geometry/algorithms/detail/overlay/self_turn_points.hpp>
  37 #include <boost/geometry/algorithms/detail/overlay/turn_info.hpp>
  38
  39 #include <boost/geometry/algorithms/detail/recalculate.hpp>
  40
  41 #include <boost/geometry/algorithms/is_empty.hpp>
  42 #include <boost/geometry/algorithms/reverse.hpp>
  43
  44 #include <boost/geometry/algorithms/detail/overlay/add_rings.hpp>
  45 #include <boost/geometry/algorithms/detail/overlay/assign_parents.hpp>
  46 #include <boost/geometry/algorithms/detail/overlay/ring_properties.hpp>
  47 #include <boost/geometry/algorithms/detail/overlay/select_rings.hpp>
  48 #include <boost/geometry/algorithms/detail/overlay/do_reverse.hpp>
  49
  50 #include <boost/geometry/policies/robustness/segment_ratio_type.hpp>
  51
  52
  53 #ifdef BOOST_GEOMETRY_DEBUG_ASSEMBLE
  54 #  include <boost/geometry/io/dsv/write.hpp>
  55 #endif
  56
  57
  58 namespace boost { namespace geometry
  59 {
  60
  61
  62 #ifndef DOXYGEN_NO_DETAIL
  63 namespace detail { namespace overlay
  64 {
  65
  66
  67 //! Default visitor for overlay, doing nothing
  68 struct overlay_null_visitor
  69 {
  70     void print(char const* ) {}
  71
  72     template <typename Turns>
  73     void print(char const* , Turns const& , int) {}
  74
  75     template <typename Turns>
  76     void print(char const* , Turns const& , int , int ) {}
  77
  78     template <typename Turns>
  79     void visit_turns(int , Turns const& ) {}
  80
  81     template <typename Clusters, typename Turns>
  82     void visit_clusters(Clusters const& , Turns const& ) {}
  83
  84     template <typename Turns, typename Turn, typename Operation>
  85     void visit_traverse(Turns const& , Turn const& , Operation const& , char const*)
  86     {}
  87
  88     template <typename Turns, typename Turn, typename Operation>
  89     void visit_traverse_reject(Turns const& , Turn const& , Operation const& , traverse_error_type )
  90     {}
  91 };
  92
  93 template
  94 <
  95     overlay_type OverlayType,
  96     typename TurnInfoMap,
  97     typename Turns,
  98     typename Clusters
  99 >
 100 inline void get_ring_turn_info(TurnInfoMap& turn_info_map, Turns const& turns, Clusters const& clusters)
 101 {
 102     typedef typename boost::range_value<Turns>::type turn_type;
 103     typedef typename turn_type::turn_operation_type turn_operation_type;
 104     typedef typename turn_type::container_type container_type;
 105
 106     static const operation_type target_operation
 107             = operation_from_overlay<OverlayType>::value;
 108     static const operation_type opposite_operation
 109             = target_operation == operation_union
 110             ? operation_intersection
 111             : operation_union;
 112
 113     for (typename boost::range_iterator<Turns const>::type
 114             it = boost::begin(turns);
 115          it != boost::end(turns);
 116          ++it)
 117     {
 118         turn_type const& turn = *it;
 119
 120         bool cluster_checked = false;
 121         bool has_blocked = false;
 122
 123         for (typename boost::range_iterator<container_type const>::type
 124                 op_it = boost::begin(turn.operations);
 125             op_it != boost::end(turn.operations);
 126             ++op_it)
 127         {
 128             turn_operation_type const& op = *op_it;
 129             ring_identifier const ring_id
 130                 (
 131                     op.seg_id.source_index,
 132                     op.seg_id.multi_index,
 133                     op.seg_id.ring_index
 134                 );
 135
 136             if (! is_self_turn<OverlayType>(turn)
 137                 && (
 138                     (target_operation == operation_union
 139                       && op.enriched.count_left > 0)
 140                   || (target_operation == operation_intersection
 141                       && op.enriched.count_right <= 2)))
 142             {
 143                 // Avoid including untraversed rings which have polygons on
 144                 // their left side (union) or not two on their right side (int)
 145                 // This can only be done for non-self-turns because of count
 146                 // information
 147                 turn_info_map[ring_id].has_blocked_turn = true;
 148                 continue;
 149             }
 150
 151             if (turn.any_blocked())
 152             {
 153                 turn_info_map[ring_id].has_blocked_turn = true;
 154             }
 155             if (turn_info_map[ring_id].has_traversed_turn
 156                     || turn_info_map[ring_id].has_blocked_turn)
 157             {
 158                 continue;
 159             }
 160
 161             // Check information in colocated turns
 162             if (! cluster_checked && turn.is_clustered())
 163             {
 164                 check_colocation(has_blocked, turn.cluster_id, turns, clusters);
 165                 cluster_checked = true;
 166             }
 167
 168             // Block rings where any other turn is blocked,
 169             // and (with exceptions): i for union and u for intersection
 170             // Exceptions: don't block self-uu for intersection
 171             //             don't block self-ii for union
 172             //             don't block (for union) i/u if there is an self-ii too
 173             if (has_blocked
 174                 || (op.operation == opposite_operation
 175                     && ! turn.has_colocated_both
 176                     && ! (turn.both(opposite_operation)
 177                           && is_self_turn<OverlayType>(turn))))
 178             {
 179                 turn_info_map[ring_id].has_blocked_turn = true;
 180             }
 181         }
 182     }
 183 }
 184
 185 template
 186 <
 187     typename GeometryOut, overlay_type OverlayType, bool ReverseOut,
 188     typename Geometry1, typename Geometry2,
 189     typename OutputIterator, typename Strategy
 190 >
 191 inline OutputIterator return_if_one_input_is_empty(Geometry1 const& geometry1,
 192             Geometry2 const& geometry2,
 193             OutputIterator out, Strategy const& strategy)
 194 {
 195     typedef std::deque
 196         <
 197             typename geometry::ring_type<GeometryOut>::type
 198         > ring_container_type;
 199
 200     typedef typename geometry::point_type<Geometry1>::type point_type1;
 201
 202     typedef ring_properties
 203         <
 204             point_type1,
 205             typename Strategy::template area_strategy
 206                 <
 207                     point_type1
 208                 >::type::return_type
 209         > properties;
 210
 211 // Silence warning C4127: conditional expression is constant
 212 #if defined(_MSC_VER)
 213 #pragma warning(push)
 214 #pragma warning(disable : 4127)
 215 #endif
 216
 217     // Union: return either of them
 218     // Intersection: return nothing
 219     // Difference: return first of them
 220     if (OverlayType == overlay_intersection
 221         || (OverlayType == overlay_difference && geometry::is_empty(geometry1)))
 222     {
 223         return out;
 224     }
 225
 226 #if defined(_MSC_VER)
 227 #pragma warning(pop)
 228 #endif
 229
 230
 231     std::map<ring_identifier, ring_turn_info> empty;
 232     std::map<ring_identifier, properties> all_of_one_of_them;
 233
 234     select_rings<OverlayType>(geometry1, geometry2, empty, all_of_one_of_them, strategy);
 235     ring_container_type rings;
 236     assign_parents(geometry1, geometry2, rings, all_of_one_of_them, strategy);
 237     return add_rings<GeometryOut>(all_of_one_of_them, geometry1, geometry2, rings, out,
 238                                   strategy.template get_area_strategy<point_type1>());
 239 }
 240
 241
 242 template
 243 <
 244     typename Geometry1, typename Geometry2,
 245     bool Reverse1, bool Reverse2, bool ReverseOut,
 246     typename GeometryOut,
 247     overlay_type OverlayType
 248 >
 249 struct overlay
 250 {
 251     template <typename RobustPolicy, typename OutputIterator, typename Strategy, typename Visitor>
 252     static inline OutputIterator apply(
 253                 Geometry1 const& geometry1, Geometry2 const& geometry2,
 254                 RobustPolicy const& robust_policy,
 255                 OutputIterator out,
 256                 Strategy const& strategy,
 257                 Visitor& visitor)
 258     {
 259         bool const is_empty1 = geometry::is_empty(geometry1);
 260         bool const is_empty2 = geometry::is_empty(geometry2);
 261
 262         if (is_empty1 && is_empty2)
 263         {
 264             return out;
 265         }
 266
 267         if (is_empty1 || is_empty2)
 268         {
 269             return return_if_one_input_is_empty
 270                 <
 271                     GeometryOut, OverlayType, ReverseOut
 272                 >(geometry1, geometry2, out, strategy);
 273         }
 274
 275         typedef typename geometry::point_type<GeometryOut>::type point_type;
 276         typedef detail::overlay::traversal_turn_info
 277         <
 278             point_type,
 279             typename geometry::segment_ratio_type<point_type, RobustPolicy>::type
 280         > turn_info;
 281         typedef std::deque<turn_info> turn_container_type;
 282
 283         typedef std::deque
 284             <
 285                 typename geometry::ring_type<GeometryOut>::type
 286             > ring_container_type;
 287
 288         // Define the clusters, mapping cluster_id -> turns
 289         typedef std::map
 290             <
 291                 signed_size_type,
 292                 cluster_info
 293             > cluster_type;
 294
 295         turn_container_type turns;
 296
 297 #ifdef BOOST_GEOMETRY_DEBUG_ASSEMBLE
 298 std::cout << "get turns" << std::endl;
 299 #endif
 300         detail::get_turns::no_interrupt_policy policy;
 301         geometry::get_turns
 302             <
 303                 Reverse1, Reverse2,
 304                 detail::overlay::assign_null_policy
 305             >(geometry1, geometry2, strategy, robust_policy, turns, policy);
 306
 307         visitor.visit_turns(1, turns);
 308
 309 #ifdef BOOST_GEOMETRY_INCLUDE_SELF_TURNS
 310         if (needs_self_turns<Geometry1>::apply(geometry1))
 311         {
 312             self_get_turn_points::self_turns<Reverse1, assign_null_policy>(geometry1,
 313                 strategy, robust_policy, turns, policy, 0);
 314         }
 315         if (needs_self_turns<Geometry2>::apply(geometry2))
 316         {
 317             self_get_turn_points::self_turns<Reverse2, assign_null_policy>(geometry2,
 318                 strategy, robust_policy, turns, policy, 1);
 319         }
 320 #endif
 321
 322
 323 #ifdef BOOST_GEOMETRY_DEBUG_ASSEMBLE
 324 std::cout << "enrich" << std::endl;
 325 #endif
 326         typename Strategy::side_strategy_type side_strategy = strategy.get_side_strategy();
 327         cluster_type clusters;
 328         std::map<ring_identifier, ring_turn_info> turn_info_per_ring;
 329
 330         geometry::enrich_intersection_points<Reverse1, Reverse2, OverlayType>(turns,
 331                 clusters, geometry1, geometry2,
 332                     robust_policy,
 333                     side_strategy);
 334
 335         visitor.visit_turns(2, turns);
 336
 337         visitor.visit_clusters(clusters, turns);
 338
 339 #ifdef BOOST_GEOMETRY_DEBUG_ASSEMBLE
 340 std::cout << "traverse" << std::endl;
 341 #endif
 342         // Traverse through intersection/turn points and create rings of them.
 343         // Note that these rings are always in clockwise order, even in CCW polygons,
 344         // and are marked as "to be reversed" below
 345         ring_container_type rings;
 346         traverse<Reverse1, Reverse2, Geometry1, Geometry2, OverlayType>::apply
 347                 (
 348                     geometry1, geometry2,
 349                     strategy,
 350                     robust_policy,
 351                     turns, rings,
 352                     turn_info_per_ring,
 353                     clusters,
 354                     visitor
 355                 );
 356         visitor.visit_turns(3, turns);
 357
 358         get_ring_turn_info<OverlayType>(turn_info_per_ring, turns, clusters);
 359
 360         typedef typename Strategy::template area_strategy<point_type>::type area_strategy_type;
 361
 362         typedef ring_properties
 363             <
 364                 point_type,
 365                 typename area_strategy_type::return_type
 366             > properties;
 367
 368         // Select all rings which are NOT touched by any intersection point
 369         std::map<ring_identifier, properties> selected_ring_properties;
 370         select_rings<OverlayType>(geometry1, geometry2, turn_info_per_ring,
 371                 selected_ring_properties, strategy);
 372
 373         // Add rings created during traversal
 374         area_strategy_type const area_strategy = strategy.template get_area_strategy<point_type>();
 375         {
 376             ring_identifier id(2, 0, -1);
 377             for (typename boost::range_iterator<ring_container_type>::type
 378                     it = boost::begin(rings);
 379                  it != boost::end(rings);
 380                  ++it)
 381             {
 382                 selected_ring_properties[id] = properties(*it, area_strategy);
 383                 selected_ring_properties[id].reversed = ReverseOut;
 384                 id.multi_index++;
 385             }
 386         }
 387
 388         assign_parents(geometry1, geometry2, rings, selected_ring_properties, strategy);
 389
 390         // NOTE: There is no need to check result area for union because
 391         // as long as the polygons in the input are valid the resulting
 392         // polygons should be valid as well.
 393         // By default the area is checked (this is old behavior) however this
 394         // can be changed with #define. This may be important in non-cartesian CSes.
 395         // The result may be too big, so the area is negative. In this case either
 396         // it can be returned or an exception can be thrown.
 397         return add_rings<GeometryOut>(selected_ring_properties, geometry1, geometry2, rings, out,
 398                                       area_strategy,
 399                                       OverlayType == overlay_union ?
 400 #if defined(BOOST_GEOMETRY_UNION_THROW_INVALID_OUTPUT_EXCEPTION)
 401                                       add_rings_throw_if_reversed
 402 #elif defined(BOOST_GEOMETRY_UNION_RETURN_INVALID)
 403                                       add_rings_add_unordered
 404 #else
 405                                       add_rings_ignore_unordered
 406 #endif
 407                                       : add_rings_ignore_unordered);
 408     }
 409
 410     template <typename RobustPolicy, typename OutputIterator, typename Strategy>
 411     static inline OutputIterator apply(
 412                 Geometry1 const& geometry1, Geometry2 const& geometry2,
 413                 RobustPolicy const& robust_policy,
 414                 OutputIterator out,
 415                 Strategy const& strategy)
 416     {
 417         overlay_null_visitor visitor;
 418         return apply(geometry1, geometry2, robust_policy, out, strategy, visitor);
 419     }
 420 };
 421
 422
 423 }} // namespace detail::overlay
 424 #endif // DOXYGEN_NO_DETAIL
 425
 426
 427 }} // namespace boost::geometry
 428
 429
 430 #endif // BOOST_GEOMETRY_ALGORITHMS_DETAIL_OVERLAY_OVERLAY_HPP