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