detail/overlay/self_turn_points.hpp

0001 // Boost.Geometry (aka GGL, Generic Geometry Library)
0002
0003 // Copyright (c) 2007-2012 Barend Gehrels, Amsterdam, the Netherlands.
0004 // Copyright (c) 2017 Adam Wulkiewicz, Lodz, Poland.
0005
0006 // This file was modified by Oracle on 2017-2024.
0007 // Modifications copyright (c) 2017-2024 Oracle and/or its affiliates.
0008 // Contributed and/or modified by Vissarion Fysikopoulos, on behalf of Oracle
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_SELF_TURN_POINTS_HPP
0016 #define BOOST_GEOMETRY_ALGORITHMS_DETAIL_OVERLAY_SELF_TURN_POINTS_HPP
0017
0018
0019 #include <cstddef>
0020
0021
0022 #include <boost/geometry/algorithms/detail/disjoint/box_box.hpp>
0023 #include <boost/geometry/algorithms/detail/partition.hpp>
0024 #include <boost/geometry/algorithms/detail/overlay/do_reverse.hpp>
0025 #include <boost/geometry/algorithms/detail/overlay/get_turns.hpp>
0026 #include <boost/geometry/algorithms/detail/sections/section_box_policies.hpp>
0027
0028 #include <boost/geometry/core/coordinate_dimension.hpp>
0029 #include <boost/geometry/core/point_order.hpp>
0030 #include <boost/geometry/core/tags.hpp>
0031
0032 #include <boost/geometry/geometries/box.hpp>
0033 #include <boost/geometry/geometries/concepts/check.hpp>
0034
0035 #include <boost/geometry/strategies/detail.hpp>
0036 #include <boost/geometry/strategies/relate/services.hpp>
0037
0038 #include <boost/geometry/util/condition.hpp>
0039
0040 namespace boost { namespace geometry
0041 {
0042
0043 #ifndef DOXYGEN_NO_DETAIL
0044 namespace detail { namespace self_get_turn_points
0045 {
0046
0047 struct no_interrupt_policy
0048 {
0049     static bool const enabled = false;
0050     static bool const has_intersections = false;
0051
0052
0053     template <typename Range>
0054     static inline bool apply(Range const&)
0055     {
0056         return false;
0057     }
0058 };
0059
0060
0061 template
0062 <
0063     bool Reverse,
0064     typename Geometry,
0065     typename Turns,
0066     typename TurnPolicy,
0067     typename Strategy,
0068     typename InterruptPolicy
0069 >
0070 struct self_section_visitor
0071 {
0072     Geometry const& m_geometry;
0073     Strategy const& m_strategy;
0074     Turns& m_turns;
0075     InterruptPolicy& m_interrupt_policy;
0076     int m_source_index;
0077     bool m_skip_adjacent;
0078
0079     inline self_section_visitor(Geometry const& g,
0080                                 Strategy const& s,
0081                                 Turns& turns,
0082                                 InterruptPolicy& ip,
0083                                 int source_index,
0084                                 bool skip_adjacent)
0085         : m_geometry(g)
0086         , m_strategy(s)
0087         , m_turns(turns)
0088         , m_interrupt_policy(ip)
0089         , m_source_index(source_index)
0090         , m_skip_adjacent(skip_adjacent)
0091     {}
0092
0093     template <typename Section>
0094     inline bool apply(Section const& sec1, Section const& sec2)
0095     {
0096         if (! detail::disjoint::disjoint_box_box(sec1.bounding_box,
0097                                                  sec2.bounding_box,
0098                                                  m_strategy)
0099                 && ! sec1.duplicate
0100                 && ! sec2.duplicate)
0101         {
0102             // false if interrupted
0103             return detail::get_turns::get_turns_in_sections
0104                     <
0105                         Geometry, Geometry,
0106                         Reverse, Reverse,
0107                         Section, Section,
0108                         TurnPolicy
0109                     >::apply(m_source_index, m_geometry, sec1,
0110                              m_source_index, m_geometry, sec2,
0111                              false, m_skip_adjacent,
0112                              m_strategy,
0113                              m_turns, m_interrupt_policy);
0114         }
0115
0116         return true;
0117     }
0118
0119 };
0120
0121
0122
0123 template <bool Reverse, typename TurnPolicy>
0124 struct get_turns
0125 {
0126     template <typename Geometry, typename Strategy, typename Turns, typename InterruptPolicy>
0127     static inline bool apply(
0128             Geometry const& geometry,
0129             Strategy const& strategy,
0130             Turns& turns,
0131             InterruptPolicy& interrupt_policy,
0132             int source_index, bool skip_adjacent)
0133     {
0134         using box_type = model::box<geometry::point_type_t<Geometry>>;
0135
0136         // sectionalize in two dimensions to detect
0137         // all potential spikes correctly
0138         using sections_type = geometry::sections<box_type, 2>;
0139
0140         using dimensions = std::integer_sequence<std::size_t, 0, 1>;
0141
0142         sections_type sec;
0143         geometry::sectionalize<Reverse, dimensions>(geometry,
0144                                                     sec, strategy);
0145
0146         self_section_visitor
0147             <
0148                 Reverse, Geometry,
0149                 Turns, TurnPolicy, Strategy, InterruptPolicy
0150             > visitor(geometry, strategy, turns, interrupt_policy,
0151                       source_index, skip_adjacent);
0152
0153         // false if interrupted
0154         geometry::partition
0155             <
0156                 box_type
0157             >::apply(sec, visitor,
0158                      detail::section::get_section_box<Strategy>(strategy),
0159                      detail::section::overlaps_section_box<Strategy>(strategy));
0160
0161         return ! interrupt_policy.has_intersections;
0162     }
0163 };
0164
0165
0166 }} // namespace detail::self_get_turn_points
0167 #endif // DOXYGEN_NO_DETAIL
0168
0169
0170 #ifndef DOXYGEN_NO_DISPATCH
0171 namespace dispatch
0172 {
0173
0174 template
0175 <
0176     bool Reverse,
0177     typename GeometryTag,
0178     typename Geometry,
0179     typename TurnPolicy
0180 >
0181 struct self_get_turn_points
0182 {
0183 };
0184
0185
0186 template
0187 <
0188     bool Reverse,
0189     typename Ring,
0190     typename TurnPolicy
0191 >
0192 struct self_get_turn_points
0193     <
0194         Reverse, ring_tag, Ring,
0195         TurnPolicy
0196     >
0197     : detail::self_get_turn_points::get_turns<Reverse, TurnPolicy>
0198 {};
0199
0200
0201 template
0202 <
0203     bool Reverse,
0204     typename Box,
0205     typename TurnPolicy
0206 >
0207 struct self_get_turn_points
0208     <
0209         Reverse, box_tag, Box,
0210         TurnPolicy
0211     >
0212 {
0213     template <typename Strategy, typename Turns, typename InterruptPolicy>
0214     static inline bool apply(
0215             Box const& ,
0216             Strategy const& ,
0217             Turns& ,
0218             InterruptPolicy& ,
0219             int /*source_index*/,
0220             bool /*skip_adjacent*/)
0221     {
0222         return true;
0223     }
0224 };
0225
0226
0227 template
0228 <
0229     bool Reverse,
0230     typename Polygon,
0231     typename TurnPolicy
0232 >
0233 struct self_get_turn_points
0234     <
0235         Reverse, polygon_tag, Polygon,
0236         TurnPolicy
0237     >
0238     : detail::self_get_turn_points::get_turns<Reverse, TurnPolicy>
0239 {};
0240
0241
0242 template
0243 <
0244     bool Reverse,
0245     typename MultiPolygon,
0246     typename TurnPolicy
0247 >
0248 struct self_get_turn_points
0249     <
0250         Reverse, multi_polygon_tag, MultiPolygon,
0251         TurnPolicy
0252     >
0253     : detail::self_get_turn_points::get_turns<Reverse, TurnPolicy>
0254 {};
0255
0256
0257 } // namespace dispatch
0258 #endif // DOXYGEN_NO_DISPATCH
0259
0260
0261 namespace resolve_strategy
0262 {
0263
0264 template
0265 <
0266     bool Reverse,
0267     typename AssignPolicy,
0268     typename Strategies,
0269     bool IsUmbrella = strategies::detail::is_umbrella_strategy<Strategies>::value
0270 >
0271 struct self_get_turn_points
0272 {
0273     template
0274     <
0275         typename Geometry,
0276         typename Turns,
0277         typename InterruptPolicy
0278     >
0279     static inline void apply(Geometry const& geometry,
0280                              Strategies const& strategies,
0281                              Turns& turns,
0282                              InterruptPolicy& interrupt_policy,
0283                              int source_index,
0284                              bool skip_adjacent)
0285     {
0286         using turn_policy = detail::overlay::get_turn_info<AssignPolicy>;
0287
0288         dispatch::self_get_turn_points
0289                 <
0290                     Reverse,
0291                     tag_t<Geometry>,
0292                     Geometry,
0293                     turn_policy
0294                 >::apply(geometry, strategies, turns, interrupt_policy,
0295                          source_index, skip_adjacent);
0296     }
0297 };
0298
0299 template <bool Reverse, typename AssignPolicy, typename Strategy>
0300 struct self_get_turn_points<Reverse, AssignPolicy, Strategy, false>
0301 {
0302     template
0303     <
0304         typename Geometry,
0305         typename Turns,
0306         typename InterruptPolicy
0307     >
0308     static inline void apply(Geometry const& geometry,
0309                              Strategy const& strategy,
0310                              Turns& turns,
0311                              InterruptPolicy& interrupt_policy,
0312                              int source_index,
0313                              bool skip_adjacent)
0314     {
0315         using strategies::relate::services::strategy_converter;
0316
0317         self_get_turn_points
0318             <
0319                 Reverse,
0320                 AssignPolicy,
0321                 decltype(strategy_converter<Strategy>::get(strategy))
0322             >::apply(geometry,
0323                      strategy_converter<Strategy>::get(strategy),
0324                      turns,
0325                      interrupt_policy,
0326                      source_index,
0327                      skip_adjacent);
0328     }
0329 };
0330
0331
0332 } // namespace resolve_strategy
0333
0334
0335 #ifndef DOXYGEN_NO_DETAIL
0336 namespace detail { namespace self_get_turn_points
0337 {
0338
0339 // Version where Reverse can be specified manually. TODO:
0340 // can most probably be merged with self_get_turn_points::get_turn
0341 template
0342 <
0343     bool Reverse,
0344     typename AssignPolicy,
0345     typename Geometry,
0346     typename Strategy,
0347     typename Turns,
0348     typename InterruptPolicy
0349 >
0350 inline void self_turns(Geometry const& geometry,
0351                        Strategy const& strategy,
0352                        Turns& turns,
0353                        InterruptPolicy& interrupt_policy,
0354                        int source_index = 0,
0355                        bool skip_adjacent = false)
0356 {
0357     concepts::check<Geometry const>();
0358
0359     resolve_strategy::self_get_turn_points
0360             <
0361                 Reverse, AssignPolicy, Strategy
0362             >::apply(geometry, strategy, turns, interrupt_policy,
0363                      source_index, skip_adjacent);
0364 }
0365
0366 }} // namespace detail::self_get_turn_points
0367 #endif // DOXYGEN_NO_DETAIL
0368
0369 /*!
0370     \brief Calculate self intersections of a geometry
0371     \ingroup overlay
0372     \tparam Geometry geometry type
0373     \tparam Turns type of intersection container
0374                 (e.g. vector of "intersection/turn point"'s)
0375     \param geometry geometry
0376     \param strategy strategy to be used
0377     \param turns container which will contain intersection points
0378     \param interrupt_policy policy determining if process is stopped
0379         when intersection is found
0380     \param source_index source index for generated turns
0381     \param skip_adjacent indicates if adjacent turns should be skipped
0382  */
0383 template
0384 <
0385     typename AssignPolicy,
0386     typename Geometry,
0387     typename Strategy,
0388     typename Turns,
0389     typename InterruptPolicy
0390 >
0391 inline void self_turns(Geometry const& geometry,
0392                        Strategy const& strategy,
0393                        Turns& turns,
0394                        InterruptPolicy& interrupt_policy,
0395                        int source_index = 0,
0396                        bool skip_adjacent = false)
0397 {
0398     concepts::check<Geometry const>();
0399
0400     static bool const reverse =  detail::overlay::do_reverse
0401         <
0402             geometry::point_order<Geometry>::value
0403         >::value;
0404
0405     resolve_strategy::self_get_turn_points
0406             <
0407                 reverse, AssignPolicy, Strategy
0408             >::apply(geometry, strategy, turns, interrupt_policy,
0409                      source_index, skip_adjacent);
0410 }
0411
0412
0413
0414 }} // namespace boost::geometry
0415
0416 #endif // BOOST_GEOMETRY_ALGORITHMS_DETAIL_OVERLAY_SELF_TURN_POINTS_HPP