detail/overlay/handle_self_turns.hpp

0001 // Boost.Geometry (aka GGL, Generic Geometry Library)
0002
0003 // Copyright (c) 2017 Barend Gehrels, Amsterdam, the Netherlands.
0004 // Copyright (c) 2017-2023 Adam Wulkiewicz, Lodz, Poland.
0005
0006 // This file was modified by Oracle on 2019-2022.
0007 // Modifications copyright (c) 2019-2022 Oracle and/or its affiliates.
0008
0009 // Contributed and/or modified by Adam Wulkiewicz, on behalf of Oracle
0010
0011 // Use, modification and distribution is subject to the Boost Software License,
0012 // Version 1.0. (See accompanying file LICENSE_1_0.txt or copy at
0013 // http://www.boost.org/LICENSE_1_0.txt)
0014
0015 #ifndef BOOST_GEOMETRY_ALGORITHMS_DETAIL_OVERLAY_HANDLE_SELF_TURNS_HPP
0016 #define BOOST_GEOMETRY_ALGORITHMS_DETAIL_OVERLAY_HANDLE_SELF_TURNS_HPP
0017
0018 #include <boost/range/begin.hpp>
0019 #include <boost/range/end.hpp>
0020 #include <boost/range/value_type.hpp>
0021
0022 #include <boost/geometry/algorithms/detail/covered_by/implementation.hpp>
0023 #include <boost/geometry/algorithms/detail/overlay/cluster_info.hpp>
0024 #include <boost/geometry/algorithms/detail/overlay/is_self_turn.hpp>
0025 #include <boost/geometry/algorithms/detail/overlay/overlay_type.hpp>
0026 #include <boost/geometry/algorithms/detail/within/implementation.hpp>
0027
0028 namespace boost { namespace geometry
0029 {
0030
0031 #ifndef DOXYGEN_NO_DETAIL
0032 namespace detail { namespace overlay
0033 {
0034
0035 template <overlay_type OverlayType>
0036 struct check_within
0037 {
0038     template
0039     <
0040         typename Turn, typename Geometry0, typename Geometry1,
0041         typename UmbrellaStrategy
0042     >
0043     static inline
0044     bool apply(Turn const& turn, Geometry0 const& geometry0,
0045                Geometry1 const& geometry1, UmbrellaStrategy const& strategy)
0046     {
0047         // Operations 0 and 1 have the same source index in self-turns
0048         return turn.operations[0].seg_id.source_index == 0
0049             ? geometry::within(turn.point, geometry1, strategy)
0050             : geometry::within(turn.point, geometry0, strategy);
0051     }
0052
0053 };
0054
0055 template <>
0056 struct check_within<overlay_difference>
0057 {
0058     template
0059     <
0060         typename Turn, typename Geometry0, typename Geometry1,
0061         typename UmbrellaStrategy
0062     >
0063     static inline
0064     bool apply(Turn const& turn, Geometry0 const& geometry0,
0065                Geometry1 const& geometry1, UmbrellaStrategy const& strategy)
0066     {
0067         // difference = intersection(a, reverse(b))
0068         // therefore we should reverse the meaning of within for geometry1
0069         return turn.operations[0].seg_id.source_index == 0
0070             ? ! geometry::covered_by(turn.point, geometry1, strategy)
0071             : geometry::within(turn.point, geometry0, strategy);
0072     }
0073 };
0074
0075 struct discard_turns
0076 {
0077     template
0078     <
0079         typename Turns, typename Clusters,
0080         typename Geometry0, typename Geometry1,
0081         typename Strategy
0082     >
0083     static inline
0084     void apply(Turns& , Clusters const& ,
0085                Geometry0 const& , Geometry1 const& ,
0086                Strategy const& )
0087     {}
0088 };
0089
0090 template <overlay_type OverlayType, operation_type OperationType>
0091 struct discard_closed_turns : discard_turns {};
0092
0093 // It is only implemented for operation_union, not in buffer
0094 template <>
0095 struct discard_closed_turns<overlay_union, operation_union>
0096 {
0097     // Point in Geometry Strategy
0098     template
0099     <
0100         typename Turns, typename Clusters,
0101         typename Geometry0, typename Geometry1,
0102         typename Strategy
0103     >
0104     static inline
0105     void apply(Turns& turns, Clusters const& /*clusters*/,
0106                Geometry0 const& geometry0, Geometry1 const& geometry1,
0107                Strategy const& strategy)
0108     {
0109         for (auto& turn : turns)
0110         {
0111             if (! turn.discarded
0112                 && is_self_turn<overlay_union>(turn)
0113                 && check_within<overlay_union>::apply(turn, geometry0,
0114                                                       geometry1, strategy))
0115             {
0116                 // Turn is in the interior of other geometry
0117                 turn.discarded = true;
0118             }
0119         }
0120     }
0121 };
0122
0123 template <overlay_type OverlayType>
0124 struct discard_self_intersection_turns
0125 {
0126 private :
0127
0128     template <typename Turns, typename Clusters>
0129     static inline
0130     bool is_self_cluster(signed_size_type cluster_id,
0131             Turns const& turns, Clusters const& clusters)
0132     {
0133         auto cit = clusters.find(cluster_id);
0134         if (cit == clusters.end())
0135         {
0136             return false;
0137         }
0138
0139         cluster_info const& cinfo = cit->second;
0140         for (auto index : cinfo.turn_indices)
0141         {
0142             if (! is_self_turn<OverlayType>(turns[index]))
0143             {
0144                 return false;
0145             }
0146         }
0147
0148         return true;
0149     }
0150
0151     template <typename Turns, typename Clusters,
0152               typename Geometry0, typename Geometry1, typename Strategy>
0153     static inline
0154     void discard_clusters(Turns& turns, Clusters const& clusters,
0155             Geometry0 const& geometry0, Geometry1 const& geometry1,
0156             Strategy const& strategy)
0157     {
0158         for (auto const& pair : clusters)
0159         {
0160             signed_size_type const cluster_id = pair.first;
0161             cluster_info const& cinfo = pair.second;
0162
0163             // If there are only self-turns in the cluster, the cluster should
0164             // be located within the other geometry, for intersection
0165             if (! cinfo.turn_indices.empty()
0166                 && is_self_cluster(cluster_id, turns, clusters))
0167             {
0168                 signed_size_type const first_index = *cinfo.turn_indices.begin();
0169                 if (! check_within<OverlayType>::apply(turns[first_index],
0170                                                        geometry0, geometry1,
0171                                                        strategy))
0172                 {
0173                     // Discard all turns in cluster
0174                     for (auto index : cinfo.turn_indices)
0175                     {
0176                         turns[index].discarded = true;
0177                     }
0178                 }
0179             }
0180         }
0181     }
0182
0183 public :
0184
0185     template <typename Turns, typename Clusters,
0186               typename Geometry0, typename Geometry1, typename Strategy>
0187     static inline
0188     void apply(Turns& turns, Clusters const& clusters,
0189             Geometry0 const& geometry0, Geometry1 const& geometry1,
0190             Strategy const& strategy)
0191     {
0192         discard_clusters(turns, clusters, geometry0, geometry1, strategy);
0193
0194         for (auto& turn : turns)
0195         {
0196             // It is a ii self-turn
0197             // Check if it is within the other geometry
0198             if (! turn.discarded
0199                 && is_self_turn<overlay_intersection>(turn)
0200                 && ! check_within<OverlayType>::apply(turn, geometry0,
0201                                                       geometry1, strategy))
0202             {
0203                 // It is not within another geometry, set it as non startable.
0204                 // It still might be traveled (#case_recursive_boxes_70)
0205                 turn.operations[0].enriched.startable = false;
0206                 turn.operations[1].enriched.startable = false;
0207             }
0208         }
0209     }
0210 };
0211
0212
0213 template <overlay_type OverlayType, operation_type OperationType>
0214 struct discard_open_turns : discard_turns {};
0215
0216 // Handler for intersection
0217 template <>
0218 struct discard_open_turns<overlay_intersection, operation_intersection>
0219         : discard_self_intersection_turns<overlay_intersection> {};
0220
0221 // Handler for difference, with different meaning of 'within'
0222 template <>
0223 struct discard_open_turns<overlay_difference, operation_intersection>
0224         : discard_self_intersection_turns<overlay_difference> {};
0225
0226 }} // namespace detail::overlay
0227 #endif //DOXYGEN_NO_DETAIL
0228
0229
0230 }} // namespace boost::geometry
0231
0232 #endif // BOOST_GEOMETRY_ALGORITHMS_DETAIL_OVERLAY_HANDLE_SELF_TURNS_HPP