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

   1 // Boost.Geometry (aka GGL, Generic Geometry Library)
   2
   3 // Copyright (c) 2007-2012 Barend Gehrels, Amsterdam, the Netherlands.
   4 // Copyright (c) 2017 Adam Wulkiewicz, Lodz, Poland.
   5
   6 // This file was modified by Oracle on 2017-2020.
   7 // Modifications copyright (c) 2017-2020 Oracle and/or its affiliates.
   8
   9 // Contributed and/or modified by Adam Wulkiewicz, on behalf of Oracle
  10
  11 // Use, modification and distribution is subject to the Boost Software License,
  12 // Version 1.0. (See accompanying file LICENSE_1_0.txt or copy at
  13 // http://www.boost.org/LICENSE_1_0.txt)
  14
  15 #ifndef BOOST_GEOMETRY_ALGORITHMS_DETAIL_OVERLAY_SELF_TURN_POINTS_HPP
  16 #define BOOST_GEOMETRY_ALGORITHMS_DETAIL_OVERLAY_SELF_TURN_POINTS_HPP
  17
  18
  19 #include <cstddef>
  20
  21
  22 #include <boost/geometry/algorithms/detail/disjoint/box_box.hpp>
  23 #include <boost/geometry/algorithms/detail/partition.hpp>
  24 #include <boost/geometry/algorithms/detail/overlay/do_reverse.hpp>
  25 #include <boost/geometry/algorithms/detail/overlay/get_turns.hpp>
  26 #include <boost/geometry/algorithms/detail/sections/section_box_policies.hpp>
  27
  28 #include <boost/geometry/core/access.hpp>
  29 #include <boost/geometry/core/coordinate_dimension.hpp>
  30 #include <boost/geometry/core/point_order.hpp>
  31 #include <boost/geometry/core/tags.hpp>
  32
  33 #include <boost/geometry/geometries/box.hpp>
  34 #include <boost/geometry/geometries/concepts/check.hpp>
  35
  36 #include <boost/geometry/util/condition.hpp>
  37
  38
  39 namespace boost { namespace geometry
  40 {
  41
  42 #ifndef DOXYGEN_NO_DETAIL
  43 namespace detail { namespace self_get_turn_points
  44 {
  45
  46 struct no_interrupt_policy
  47 {
  48     static bool const enabled = false;
  49     static bool const has_intersections = false;
  50
  51
  52     template <typename Range>
  53     static inline bool apply(Range const&)
  54     {
  55         return false;
  56     }
  57 };
  58
  59
  60 template
  61 <
  62     bool Reverse,
  63     typename Geometry,
  64     typename Turns,
  65     typename TurnPolicy,
  66     typename IntersectionStrategy,
  67     typename RobustPolicy,
  68     typename InterruptPolicy
  69 >
  70 struct self_section_visitor
  71 {
  72     Geometry const& m_geometry;
  73     IntersectionStrategy const& m_intersection_strategy;
  74     RobustPolicy const& m_rescale_policy;
  75     Turns& m_turns;
  76     InterruptPolicy& m_interrupt_policy;
  77     int m_source_index;
  78     bool m_skip_adjacent;
  79
  80     inline self_section_visitor(Geometry const& g,
  81                                 IntersectionStrategy const& is,
  82                                 RobustPolicy const& rp,
  83                                 Turns& turns,
  84                                 InterruptPolicy& ip,
  85                                 int source_index,
  86                                 bool skip_adjacent)
  87         : m_geometry(g)
  88         , m_intersection_strategy(is)
  89         , m_rescale_policy(rp)
  90         , m_turns(turns)
  91         , m_interrupt_policy(ip)
  92         , m_source_index(source_index)
  93         , m_skip_adjacent(skip_adjacent)
  94     {}
  95
  96     template <typename Section>
  97     inline bool apply(Section const& sec1, Section const& sec2)
  98     {
  99         if (! detail::disjoint::disjoint_box_box(sec1.bounding_box,
 100                                                  sec2.bounding_box,
 101                                                  m_intersection_strategy.get_disjoint_box_box_strategy())
 102                 && ! sec1.duplicate
 103                 && ! sec2.duplicate)
 104         {
 105             // false if interrupted
 106             return detail::get_turns::get_turns_in_sections
 107                     <
 108                         Geometry, Geometry,
 109                         Reverse, Reverse,
 110                         Section, Section,
 111                         TurnPolicy
 112                     >::apply(m_source_index, m_geometry, sec1,
 113                              m_source_index, m_geometry, sec2,
 114                              false, m_skip_adjacent,
 115                              m_intersection_strategy,
 116                              m_rescale_policy,
 117                              m_turns, m_interrupt_policy);
 118         }
 119
 120         return true;
 121     }
 122
 123 };
 124
 125
 126
 127 template <bool Reverse, typename TurnPolicy>
 128 struct get_turns
 129 {
 130     template <typename Geometry, typename IntersectionStrategy, typename RobustPolicy, typename Turns, typename InterruptPolicy>
 131     static inline bool apply(
 132             Geometry const& geometry,
 133             IntersectionStrategy const& intersection_strategy,
 134             RobustPolicy const& robust_policy,
 135             Turns& turns,
 136             InterruptPolicy& interrupt_policy,
 137             int source_index, bool skip_adjacent)
 138     {
 139         typedef model::box
 140             <
 141                 typename geometry::robust_point_type
 142                 <
 143                     typename geometry::point_type<Geometry>::type,
 144                     RobustPolicy
 145                 >::type
 146             > box_type;
 147
 148         // sectionalize in two dimensions to detect
 149         // all potential spikes correctly
 150         typedef geometry::sections<box_type, 2> sections_type;
 151
 152         typedef std::integer_sequence<std::size_t, 0, 1> dimensions;
 153
 154         sections_type sec;
 155         geometry::sectionalize<Reverse, dimensions>(geometry, robust_policy, sec,
 156                                                     intersection_strategy.get_envelope_strategy(),
 157                                                     intersection_strategy.get_expand_strategy());
 158
 159         self_section_visitor
 160             <
 161                 Reverse, Geometry,
 162                 Turns, TurnPolicy, IntersectionStrategy, RobustPolicy, InterruptPolicy
 163             > visitor(geometry, intersection_strategy, robust_policy, turns, interrupt_policy, source_index, skip_adjacent);
 164
 165         typedef detail::section::get_section_box
 166             <
 167                 typename IntersectionStrategy::expand_box_strategy_type
 168             > get_section_box_type;
 169         typedef detail::section::overlaps_section_box
 170             <
 171                 typename IntersectionStrategy::disjoint_box_box_strategy_type
 172             > overlaps_section_box_type;
 173
 174         // false if interrupted
 175         geometry::partition
 176             <
 177                 box_type
 178             >::apply(sec, visitor,
 179                      get_section_box_type(),
 180                      overlaps_section_box_type());
 181
 182         return ! interrupt_policy.has_intersections;
 183     }
 184 };
 185
 186
 187 }} // namespace detail::self_get_turn_points
 188 #endif // DOXYGEN_NO_DETAIL
 189
 190
 191 #ifndef DOXYGEN_NO_DISPATCH
 192 namespace dispatch
 193 {
 194
 195 template
 196 <
 197     bool Reverse,
 198     typename GeometryTag,
 199     typename Geometry,
 200     typename TurnPolicy
 201 >
 202 struct self_get_turn_points
 203 {
 204 };
 205
 206
 207 template
 208 <
 209     bool Reverse,
 210     typename Ring,
 211     typename TurnPolicy
 212 >
 213 struct self_get_turn_points
 214     <
 215         Reverse, ring_tag, Ring,
 216         TurnPolicy
 217     >
 218     : detail::self_get_turn_points::get_turns<Reverse, TurnPolicy>
 219 {};
 220
 221
 222 template
 223 <
 224     bool Reverse,
 225     typename Box,
 226     typename TurnPolicy
 227 >
 228 struct self_get_turn_points
 229     <
 230         Reverse, box_tag, Box,
 231         TurnPolicy
 232     >
 233 {
 234     template <typename Strategy, typename RobustPolicy, typename Turns, typename InterruptPolicy>
 235     static inline bool apply(
 236             Box const& ,
 237             Strategy const& ,
 238             RobustPolicy const& ,
 239             Turns& ,
 240             InterruptPolicy& ,
 241             int /*source_index*/,
 242             bool /*skip_adjacent*/)
 243     {
 244         return true;
 245     }
 246 };
 247
 248
 249 template
 250 <
 251     bool Reverse,
 252     typename Polygon,
 253     typename TurnPolicy
 254 >
 255 struct self_get_turn_points
 256     <
 257         Reverse, polygon_tag, Polygon,
 258         TurnPolicy
 259     >
 260     : detail::self_get_turn_points::get_turns<Reverse, TurnPolicy>
 261 {};
 262
 263
 264 template
 265 <
 266     bool Reverse,
 267     typename MultiPolygon,
 268     typename TurnPolicy
 269 >
 270 struct self_get_turn_points
 271     <
 272         Reverse, multi_polygon_tag, MultiPolygon,
 273         TurnPolicy
 274     >
 275     : detail::self_get_turn_points::get_turns<Reverse, TurnPolicy>
 276 {};
 277
 278
 279 } // namespace dispatch
 280 #endif // DOXYGEN_NO_DISPATCH
 281
 282
 283 #ifndef DOXYGEN_NO_DETAIL
 284 namespace detail { namespace self_get_turn_points
 285 {
 286
 287 // Version where Reverse can be specified manually. TODO:
 288 // can most probably be merged with self_get_turn_points::get_turn
 289 template
 290 <
 291     bool Reverse,
 292     typename AssignPolicy,
 293     typename Geometry,
 294     typename IntersectionStrategy,
 295     typename RobustPolicy,
 296     typename Turns,
 297     typename InterruptPolicy
 298 >
 299 inline void self_turns(Geometry const& geometry,
 300                        IntersectionStrategy const& strategy,
 301                        RobustPolicy const& robust_policy,
 302                        Turns& turns,
 303                        InterruptPolicy& interrupt_policy,
 304                        int source_index = 0,
 305                        bool skip_adjacent = false)
 306 {
 307     concepts::check<Geometry const>();
 308
 309     typedef detail::overlay::get_turn_info<detail::overlay::assign_null_policy> turn_policy;
 310
 311     dispatch::self_get_turn_points
 312             <
 313                 Reverse,
 314                 typename tag<Geometry>::type,
 315                 Geometry,
 316                 turn_policy
 317             >::apply(geometry, strategy, robust_policy, turns, interrupt_policy,
 318                      source_index, skip_adjacent);
 319 }
 320
 321 }} // namespace detail::self_get_turn_points
 322 #endif // DOXYGEN_NO_DETAIL
 323
 324 /*!
 325     \brief Calculate self intersections of a geometry
 326     \ingroup overlay
 327     \tparam Geometry geometry type
 328     \tparam Turns type of intersection container
 329                 (e.g. vector of "intersection/turn point"'s)
 330     \param geometry geometry
 331     \param strategy strategy to be used
 332     \param robust_policy policy to handle robustness issues
 333     \param turns container which will contain intersection points
 334     \param interrupt_policy policy determining if process is stopped
 335         when intersection is found
 336     \param source_index source index for generated turns
 337     \param skip_adjacent indicates if adjacent turns should be skipped
 338  */
 339 template
 340 <
 341     typename AssignPolicy,
 342     typename Geometry,
 343     typename IntersectionStrategy,
 344     typename RobustPolicy,
 345     typename Turns,
 346     typename InterruptPolicy
 347 >
 348 inline void self_turns(Geometry const& geometry,
 349                        IntersectionStrategy const& strategy,
 350                        RobustPolicy const& robust_policy,
 351                        Turns& turns,
 352                        InterruptPolicy& interrupt_policy,
 353                        int source_index = 0,
 354                        bool skip_adjacent = false)
 355 {
 356     concepts::check<Geometry const>();
 357
 358     static bool const reverse =  detail::overlay::do_reverse
 359         <
 360             geometry::point_order<Geometry>::value
 361         >::value;
 362
 363     detail::self_get_turn_points::self_turns
 364             <
 365                 reverse,
 366                 AssignPolicy
 367             >(geometry, strategy, robust_policy, turns, interrupt_policy,
 368               source_index, skip_adjacent);
 369 }
 370
 371
 372
 373 }} // namespace boost::geometry
 374
 375 #endif // BOOST_GEOMETRY_ALGORITHMS_DETAIL_OVERLAY_SELF_TURN_POINTS_HPP