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, 2018.
   7 // Modifications copyright (c) 2017-2018 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     int 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                                 int 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,
 103                                                  sec2.bounding_box,
 104                                                  m_intersection_strategy.get_disjoint_box_box_strategy())
 105                 && ! sec1.duplicate
 106                 && ! sec2.duplicate)
 107         {
 108             // false if interrupted
 109             return detail::get_turns::get_turns_in_sections
 110                     <
 111                         Geometry, Geometry,
 112                         Reverse, Reverse,
 113                         Section, Section,
 114                         TurnPolicy
 115                     >::apply(m_source_index, m_geometry, sec1,
 116                              m_source_index, m_geometry, sec2,
 117                              false, m_skip_adjacent,
 118                              m_intersection_strategy,
 119                              m_rescale_policy,
 120                              m_turns, m_interrupt_policy);
 121         }
 122
 123         return true;
 124     }
 125
 126 };
 127
 128
 129
 130 template <bool Reverse, typename TurnPolicy>
 131 struct get_turns
 132 {
 133     template <typename Geometry, typename IntersectionStrategy, typename RobustPolicy, typename Turns, typename InterruptPolicy>
 134     static inline bool apply(
 135             Geometry const& geometry,
 136             IntersectionStrategy const& intersection_strategy,
 137             RobustPolicy const& robust_policy,
 138             Turns& turns,
 139             InterruptPolicy& interrupt_policy,
 140             int source_index, bool skip_adjacent)
 141     {
 142         typedef model::box
 143             <
 144                 typename geometry::robust_point_type
 145                 <
 146                     typename geometry::point_type<Geometry>::type,
 147                     RobustPolicy
 148                 >::type
 149             > box_type;
 150
 151         // sectionalize in two dimensions to detect
 152         // all potential spikes correctly
 153         typedef geometry::sections<box_type, 2> sections_type;
 154
 155         typedef boost::mpl::vector_c<std::size_t, 0, 1> dimensions;
 156
 157         sections_type sec;
 158         geometry::sectionalize<Reverse, dimensions>(geometry, robust_policy, sec,
 159                                                     intersection_strategy.get_envelope_strategy(),
 160                                                     intersection_strategy.get_expand_strategy());
 161
 162         self_section_visitor
 163             <
 164                 Reverse, Geometry,
 165                 Turns, TurnPolicy, IntersectionStrategy, RobustPolicy, InterruptPolicy
 166             > visitor(geometry, intersection_strategy, robust_policy, turns, interrupt_policy, source_index, skip_adjacent);
 167
 168         typedef detail::section::get_section_box
 169             <
 170                 typename IntersectionStrategy::expand_box_strategy_type
 171             > get_section_box_type;
 172         typedef detail::section::overlaps_section_box
 173             <
 174                 typename IntersectionStrategy::disjoint_box_box_strategy_type
 175             > overlaps_section_box_type;
 176
 177         // false if interrupted
 178         geometry::partition
 179             <
 180                 box_type
 181             >::apply(sec, visitor,
 182                      get_section_box_type(),
 183                      overlaps_section_box_type());
 184
 185         return ! interrupt_policy.has_intersections;
 186     }
 187 };
 188
 189
 190 }} // namespace detail::self_get_turn_points
 191 #endif // DOXYGEN_NO_DETAIL
 192
 193
 194 #ifndef DOXYGEN_NO_DISPATCH
 195 namespace dispatch
 196 {
 197
 198 template
 199 <
 200     bool Reverse,
 201     typename GeometryTag,
 202     typename Geometry,
 203     typename TurnPolicy
 204 >
 205 struct self_get_turn_points
 206 {
 207 };
 208
 209
 210 template
 211 <
 212     bool Reverse,
 213     typename Ring,
 214     typename TurnPolicy
 215 >
 216 struct self_get_turn_points
 217     <
 218         Reverse, ring_tag, Ring,
 219         TurnPolicy
 220     >
 221     : detail::self_get_turn_points::get_turns<Reverse, TurnPolicy>
 222 {};
 223
 224
 225 template
 226 <
 227     bool Reverse,
 228     typename Box,
 229     typename TurnPolicy
 230 >
 231 struct self_get_turn_points
 232     <
 233         Reverse, box_tag, Box,
 234         TurnPolicy
 235     >
 236 {
 237     template <typename Strategy, typename RobustPolicy, typename Turns, typename InterruptPolicy>
 238     static inline bool apply(
 239             Box const& ,
 240             Strategy const& ,
 241             RobustPolicy const& ,
 242             Turns& ,
 243             InterruptPolicy& ,
 244             int /*source_index*/,
 245             bool /*skip_adjacent*/)
 246     {
 247         return true;
 248     }
 249 };
 250
 251
 252 template
 253 <
 254     bool Reverse,
 255     typename Polygon,
 256     typename TurnPolicy
 257 >
 258 struct self_get_turn_points
 259     <
 260         Reverse, polygon_tag, Polygon,
 261         TurnPolicy
 262     >
 263     : detail::self_get_turn_points::get_turns<Reverse, TurnPolicy>
 264 {};
 265
 266
 267 template
 268 <
 269     bool Reverse,
 270     typename MultiPolygon,
 271     typename TurnPolicy
 272 >
 273 struct self_get_turn_points
 274     <
 275         Reverse, multi_polygon_tag, MultiPolygon,
 276         TurnPolicy
 277     >
 278     : detail::self_get_turn_points::get_turns<Reverse, TurnPolicy>
 279 {};
 280
 281
 282 } // namespace dispatch
 283 #endif // DOXYGEN_NO_DISPATCH
 284
 285
 286 #ifndef DOXYGEN_NO_DETAIL
 287 namespace detail { namespace self_get_turn_points
 288 {
 289
 290 // Version where Reverse can be specified manually. TODO:
 291 // can most probably be merged with self_get_turn_points::get_turn
 292 template
 293 <
 294     bool Reverse,
 295     typename AssignPolicy,
 296     typename Geometry,
 297     typename IntersectionStrategy,
 298     typename RobustPolicy,
 299     typename Turns,
 300     typename InterruptPolicy
 301 >
 302 inline void self_turns(Geometry const& geometry,
 303                        IntersectionStrategy const& strategy,
 304                        RobustPolicy const& robust_policy,
 305                        Turns& turns,
 306                        InterruptPolicy& interrupt_policy,
 307                        int source_index = 0,
 308                        bool skip_adjacent = false)
 309 {
 310     concepts::check<Geometry const>();
 311
 312     typedef detail::overlay::get_turn_info<detail::overlay::assign_null_policy> turn_policy;
 313
 314     dispatch::self_get_turn_points
 315             <
 316                 Reverse,
 317                 typename tag<Geometry>::type,
 318                 Geometry,
 319                 turn_policy
 320             >::apply(geometry, strategy, robust_policy, turns, interrupt_policy,
 321                      source_index, skip_adjacent);
 322 }
 323
 324 }} // namespace detail::self_get_turn_points
 325 #endif // DOXYGEN_NO_DETAIL
 326
 327 /*!
 328     \brief Calculate self intersections of a geometry
 329     \ingroup overlay
 330     \tparam Geometry geometry type
 331     \tparam Turns type of intersection container
 332                 (e.g. vector of "intersection/turn point"'s)
 333     \param geometry geometry
 334     \param strategy strategy to be used
 335     \param robust_policy policy to handle robustness issues
 336     \param turns container which will contain intersection points
 337     \param interrupt_policy policy determining if process is stopped
 338         when intersection is found
 339     \param source_index source index for generated turns
 340     \param skip_adjacent indicates if adjacent turns should be skipped
 341  */
 342 template
 343 <
 344     typename AssignPolicy,
 345     typename Geometry,
 346     typename IntersectionStrategy,
 347     typename RobustPolicy,
 348     typename Turns,
 349     typename InterruptPolicy
 350 >
 351 inline void self_turns(Geometry const& geometry,
 352                        IntersectionStrategy const& strategy,
 353                        RobustPolicy const& robust_policy,
 354                        Turns& turns,
 355                        InterruptPolicy& interrupt_policy,
 356                        int source_index = 0,
 357                        bool skip_adjacent = false)
 358 {
 359     concepts::check<Geometry const>();
 360
 361     static bool const reverse =  detail::overlay::do_reverse
 362         <
 363             geometry::point_order<Geometry>::value
 364         >::value;
 365
 366     detail::self_get_turn_points::self_turns
 367             <
 368                 reverse,
 369                 AssignPolicy
 370             >(geometry, strategy, robust_policy, turns, interrupt_policy,
 371               source_index, skip_adjacent);
 372 }
 373
 374
 375
 376 }} // namespace boost::geometry
 377
 378 #endif // BOOST_GEOMETRY_ALGORITHMS_DETAIL_OVERLAY_SELF_TURN_POINTS_HPP