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