detail/overlay/overlay.hpp

0001 // Boost.Geometry (aka GGL, Generic Geometry Library)
0002
0003 // Copyright (c) 2007-2015 Barend Gehrels, Amsterdam, the Netherlands.
0004 // Copyright (c) 2013-2017 Adam Wulkiewicz, Lodz, Poland
0005
0006 // This file was modified by Oracle on 2015-2024.
0007 // Modifications copyright (c) 2015-2024, Oracle and/or its affiliates.
0008 // Contributed and/or modified by Vissarion Fysikopoulos, on behalf of Oracle
0009 // Contributed and/or modified by Menelaos Karavelas, on behalf of Oracle
0010 // Contributed and/or modified by Adam Wulkiewicz, on behalf of Oracle
0011
0012 // Use, modification and distribution is subject to the Boost Software License,
0013 // Version 1.0. (See accompanying file LICENSE_1_0.txt or copy at
0014 // http://www.boost.org/LICENSE_1_0.txt)
0015
0016 #ifndef BOOST_GEOMETRY_ALGORITHMS_DETAIL_OVERLAY_OVERLAY_HPP
0017 #define BOOST_GEOMETRY_ALGORITHMS_DETAIL_OVERLAY_OVERLAY_HPP
0018
0019
0020 #include <deque>
0021 #include <map>
0022
0023 #include <boost/range/begin.hpp>
0024 #include <boost/range/end.hpp>
0025 #include <boost/range/value_type.hpp>
0026
0027 #include <boost/geometry/algorithms/detail/overlay/cluster_info.hpp>
0028 #include <boost/geometry/algorithms/detail/overlay/enrich_intersection_points.hpp>
0029 #include <boost/geometry/algorithms/detail/overlay/enrichment_info.hpp>
0030 #include <boost/geometry/algorithms/detail/overlay/get_turns.hpp>
0031 #include <boost/geometry/algorithms/detail/overlay/is_self_turn.hpp>
0032 #include <boost/geometry/algorithms/detail/overlay/needs_self_turns.hpp>
0033 #include <boost/geometry/algorithms/detail/overlay/overlay_type.hpp>
0034 #include <boost/geometry/algorithms/detail/overlay/traverse.hpp>
0035 #include <boost/geometry/algorithms/detail/overlay/traversal_info.hpp>
0036 #include <boost/geometry/algorithms/detail/overlay/self_turn_points.hpp>
0037 #include <boost/geometry/algorithms/detail/overlay/turn_info.hpp>
0038
0039 #include <boost/geometry/algorithms/is_empty.hpp>
0040 #include <boost/geometry/algorithms/reverse.hpp>
0041
0042 #include <boost/geometry/algorithms/detail/overlay/add_rings.hpp>
0043 #include <boost/geometry/algorithms/detail/overlay/assign_parents.hpp>
0044 #include <boost/geometry/algorithms/detail/overlay/ring_properties.hpp>
0045 #include <boost/geometry/algorithms/detail/overlay/select_rings.hpp>
0046 #include <boost/geometry/algorithms/detail/overlay/do_reverse.hpp>
0047
0048 #include <boost/geometry/util/condition.hpp>
0049
0050
0051 namespace boost { namespace geometry
0052 {
0053
0054
0055 #ifndef DOXYGEN_NO_DETAIL
0056 namespace detail { namespace overlay
0057 {
0058
0059
0060 //! Default visitor for overlay, doing nothing
0061 struct overlay_null_visitor
0062 {
0063     template <typename Turns>
0064     void visit_turns(int , Turns const& ) {}
0065
0066     template <typename Clusters, typename Turns>
0067     void visit_clusters(Clusters const& , Turns const& ) {}
0068
0069     template <typename Turns, typename Turn, typename Operation>
0070     void visit_traverse(Turns const& , Turn const& , Operation const& , char const*)
0071     {}
0072
0073     template <typename Turns, typename Turn, typename Operation>
0074     void visit_traverse_reject(Turns const& , Turn const& , Operation const& , traverse_error_type )
0075     {}
0076
0077     template <typename Rings>
0078     void visit_generated_rings(Rings const& )
0079     {}
0080 };
0081
0082 template
0083 <
0084     overlay_type OverlayType,
0085     typename TurnInfoMap,
0086     typename Turns,
0087     typename Clusters
0088 >
0089 inline void get_ring_turn_info(TurnInfoMap& turn_info_map, Turns const& turns, Clusters const& clusters)
0090 {
0091     static const operation_type target_operation
0092             = operation_from_overlay<OverlayType>::value;
0093     static const operation_type opposite_operation
0094             = target_operation == operation_union
0095             ? operation_intersection
0096             : operation_union;
0097     static const bool is_union = target_operation == operation_union;
0098
0099     for (auto const& turn : turns)
0100     {
0101         bool cluster_checked = false;
0102         bool has_blocked = false;
0103
0104         if (turn.discarded && (turn.method == method_start || is_self_turn<OverlayType>(turn)))
0105         {
0106             // Discarded self-turns or start turns don't need to block the ring
0107             continue;
0108         }
0109
0110         for (int i = 0; i < 2; i++)
0111         {
0112             auto const& op = turn.operations[i];
0113             auto const& other_op = turn.operations[1 - i];
0114             ring_identifier const ring_id = ring_id_by_seg_id(op.seg_id);
0115
0116             // If the turn (one of its operations) is used during traversal,
0117             // and it is an intersection or difference, it cannot be set to blocked.
0118             // This is a rare case, related to floating point precision,
0119             // and can happen if there is, for example, only one start turn which is
0120             // used to traverse through one of the rings (the other should be marked
0121             // as not traversed, but neither blocked).
0122             bool const can_block
0123                 = is_union
0124                 || ! (op.visited.finalized() || other_op.visited.finalized());
0125
0126             if (! is_self_turn<OverlayType>(turn) && can_block)
0127             {
0128                 turn_info_map[ring_id].has_blocked_turn = true;
0129                 continue;
0130             }
0131
0132             if (is_union && turn.any_blocked())
0133             {
0134                 turn_info_map[ring_id].has_blocked_turn = true;
0135             }
0136             if (turn_info_map[ring_id].has_traversed_turn
0137                     || turn_info_map[ring_id].has_blocked_turn)
0138             {
0139                 continue;
0140             }
0141
0142             // Check information in colocated turns
0143             if (! cluster_checked && turn.is_clustered())
0144             {
0145                 check_colocation(has_blocked, turn.cluster_id, turns, clusters);
0146                 cluster_checked = true;
0147             }
0148
0149             // Block rings where any other turn is blocked,
0150             // and (with exceptions): i for union and u for intersection
0151             // Exceptions: don't block self-uu for intersection
0152             //             don't block self-ii for union
0153             //             don't block (for union) i/u if there is an self-ii too
0154             if (has_blocked
0155                 || (op.operation == opposite_operation
0156                     && can_block
0157                     && ! turn.has_colocated_both
0158                     && ! (turn.both(opposite_operation)
0159                           && is_self_turn<OverlayType>(turn))))
0160             {
0161                 turn_info_map[ring_id].has_blocked_turn = true;
0162             }
0163         }
0164     }
0165 }
0166
0167 template
0168 <
0169     typename GeometryOut, overlay_type OverlayType, bool ReverseOut,
0170     typename Geometry1, typename Geometry2,
0171     typename OutputIterator, typename Strategy
0172 >
0173 inline OutputIterator return_if_one_input_is_empty(Geometry1 const& geometry1,
0174             Geometry2 const& geometry2,
0175             OutputIterator out, Strategy const& strategy)
0176 {
0177     using ring_type = geometry::ring_type_t<GeometryOut>;
0178     using ring_container_type = std::deque<ring_type>;
0179
0180     using properties = ring_properties
0181         <
0182             geometry::point_type_t<ring_type>,
0183             typename geometry::area_result<ring_type, Strategy>::type
0184         >;
0185
0186 // Silence warning C4127: conditional expression is constant
0187 #if defined(_MSC_VER)
0188 #pragma warning(push)
0189 #pragma warning(disable : 4127)
0190 #endif
0191
0192     // Union: return either of them
0193     // Intersection: return nothing
0194     // Difference: return first of them
0195     if (OverlayType == overlay_intersection
0196         || (OverlayType == overlay_difference && geometry::is_empty(geometry1)))
0197     {
0198         return out;
0199     }
0200
0201 #if defined(_MSC_VER)
0202 #pragma warning(pop)
0203 #endif
0204
0205
0206     std::map<ring_identifier, ring_turn_info> empty;
0207     std::map<ring_identifier, properties> all_of_one_of_them;
0208
0209     select_rings<OverlayType>(geometry1, geometry2, empty, all_of_one_of_them, strategy);
0210     ring_container_type rings;
0211     assign_parents<OverlayType>(geometry1, geometry2, rings, all_of_one_of_them, strategy);
0212     return add_rings<GeometryOut>(all_of_one_of_them, geometry1, geometry2, rings, out, strategy);
0213 }
0214
0215
0216 template
0217 <
0218     typename Geometry1, typename Geometry2,
0219     bool Reverse1, bool Reverse2, bool ReverseOut,
0220     typename GeometryOut,
0221     overlay_type OverlayType
0222 >
0223 struct overlay
0224 {
0225     template <typename OutputIterator, typename Strategy, typename Visitor>
0226     static inline OutputIterator apply(
0227                 Geometry1 const& geometry1, Geometry2 const& geometry2,
0228                 OutputIterator out,
0229                 Strategy const& strategy,
0230                 Visitor& visitor)
0231     {
0232         bool const is_empty1 = geometry::is_empty(geometry1);
0233         bool const is_empty2 = geometry::is_empty(geometry2);
0234
0235         if (is_empty1 && is_empty2)
0236         {
0237             return out;
0238         }
0239
0240         if (is_empty1 || is_empty2)
0241         {
0242             return return_if_one_input_is_empty
0243                 <
0244                     GeometryOut, OverlayType, ReverseOut
0245                 >(geometry1, geometry2, out, strategy);
0246         }
0247
0248         using point_type = geometry::point_type_t<GeometryOut>;
0249         using turn_info = detail::overlay::traversal_turn_info
0250         <
0251             point_type,
0252             typename segment_ratio_type<point_type>::type
0253         >;
0254         using turn_container_type = std::deque<turn_info>;
0255
0256         using ring_type = geometry::ring_type_t<GeometryOut>;
0257         using ring_container_type = std::deque<ring_type>;
0258
0259         // Define the clusters, mapping cluster_id -> turns
0260         using cluster_type = std::map
0261             <
0262                 signed_size_type,
0263                 cluster_info
0264             >;
0265
0266         constexpr operation_type target_operation = operation_from_overlay<OverlayType>::value;
0267
0268         turn_container_type turns;
0269
0270         detail::get_turns::no_interrupt_policy policy;
0271         geometry::get_turns
0272             <
0273                 Reverse1, Reverse2,
0274                 assign_policy_only_start_turns
0275             >(geometry1, geometry2, strategy, turns, policy);
0276
0277         visitor.visit_turns(1, turns);
0278
0279 #if ! defined(BOOST_GEOMETRY_NO_SELF_TURNS)
0280         if (! turns.empty() || OverlayType == overlay_dissolve)
0281         {
0282             // Calculate self turns if the output contains turns already,
0283             // and if necessary (e.g.: multi-geometry, polygon with interior rings)
0284             if (needs_self_turns<Geometry1>::apply(geometry1))
0285             {
0286                 self_get_turn_points::self_turns<Reverse1, assign_policy_only_start_turns>(geometry1,
0287                     strategy, turns, policy, 0);
0288             }
0289             if (needs_self_turns<Geometry2>::apply(geometry2))
0290             {
0291                 self_get_turn_points::self_turns<Reverse2, assign_policy_only_start_turns>(geometry2,
0292                     strategy, turns, policy, 1);
0293             }
0294         }
0295 #endif
0296
0297         cluster_type clusters;
0298         std::map<ring_identifier, ring_turn_info> turn_info_per_ring;
0299
0300         // Handle colocations, gathering clusters and (below) their properties.
0301         detail::overlay::handle_colocations
0302                     <
0303                         Reverse1, Reverse2, OverlayType, Geometry1, Geometry2
0304                     >(turns, clusters);
0305
0306         // Gather cluster properties (using even clusters with
0307         // discarded turns - for open turns)
0308         detail::overlay::gather_cluster_properties
0309             <
0310                 Reverse1,
0311                 Reverse2,
0312                 OverlayType
0313             >(clusters, turns, target_operation, geometry1, geometry2, strategy);
0314
0315         geometry::enrich_intersection_points<Reverse1, Reverse2, OverlayType>(
0316             turns, clusters, geometry1, geometry2, strategy);
0317
0318         visitor.visit_turns(2, turns);
0319
0320         visitor.visit_clusters(clusters, turns);
0321
0322         // Traverse through intersection/turn points and create rings of them.
0323         // These rings are always in clockwise order.
0324         // In CCW polygons they are marked as "to be reversed" below.
0325         ring_container_type rings;
0326         traverse<Reverse1, Reverse2, Geometry1, Geometry2, OverlayType>::apply
0327                 (
0328                     geometry1, geometry2,
0329                     strategy,
0330                     turns, rings,
0331                     turn_info_per_ring,
0332                     clusters,
0333                     visitor
0334                 );
0335         visitor.visit_turns(3, turns);
0336
0337         get_ring_turn_info<OverlayType>(turn_info_per_ring, turns, clusters);
0338
0339         using properties = ring_properties
0340             <
0341                 point_type,
0342                 typename geometry::area_result<ring_type, Strategy>::type
0343             >;
0344
0345         // Select all rings which are NOT touched by any intersection point
0346         std::map<ring_identifier, properties> selected_ring_properties;
0347         select_rings<OverlayType>(geometry1, geometry2, turn_info_per_ring,
0348                 selected_ring_properties, strategy);
0349
0350         // Add rings created during traversal
0351         {
0352             ring_identifier id(2, 0, -1);
0353             for (auto const& ring : rings)
0354             {
0355                 selected_ring_properties[id] = properties(ring, strategy);
0356                 selected_ring_properties[id].reversed = ReverseOut;
0357                 id.multi_index++;
0358             }
0359         }
0360
0361         assign_parents<OverlayType>(geometry1, geometry2,
0362             rings, selected_ring_properties, strategy);
0363
0364         // NOTE: There is no need to check result area for union because
0365         // as long as the polygons in the input are valid the resulting
0366         // polygons should be valid as well.
0367         // By default the area is checked (this is old behavior) however this
0368         // can be changed with #define. This may be important in non-cartesian CSes.
0369         // The result may be too big, so the area is negative. In this case either
0370         // it can be returned or an exception can be thrown.
0371         return add_rings<GeometryOut>(selected_ring_properties, geometry1, geometry2, rings, out,
0372                                       strategy,
0373 #if defined(BOOST_GEOMETRY_UNION_THROW_INVALID_OUTPUT_EXCEPTION)
0374                                       OverlayType == overlay_union ?
0375                                       add_rings_throw_if_reversed
0376                                       : add_rings_ignore_unordered
0377 #elif defined(BOOST_GEOMETRY_UNION_RETURN_INVALID)
0378                                       OverlayType == overlay_union ?
0379                                       add_rings_add_unordered
0380                                       : add_rings_ignore_unordered
0381 #else
0382                                       add_rings_ignore_unordered
0383 #endif
0384                                       );
0385     }
0386
0387     template <typename OutputIterator, typename Strategy>
0388     static inline OutputIterator apply(
0389                 Geometry1 const& geometry1, Geometry2 const& geometry2,
0390                 OutputIterator out,
0391                 Strategy const& strategy)
0392     {
0393         overlay_null_visitor visitor;
0394         return apply(geometry1, geometry2, out, strategy, visitor);
0395     }
0396 };
0397
0398
0399 }} // namespace detail::overlay
0400 #endif // DOXYGEN_NO_DETAIL
0401
0402
0403 }} // namespace boost::geometry
0404
0405
0406 #endif // BOOST_GEOMETRY_ALGORITHMS_DETAIL_OVERLAY_OVERLAY_HPP