ceph/src/boost/libs/geometry/include/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
   5 // Use, modification and distribution is subject to the Boost Software License,
   6 // Version 1.0. (See accompanying file LICENSE_1_0.txt or copy at
   7 // http://www.boost.org/LICENSE_1_0.txt)
   8
   9 #ifndef BOOST_GEOMETRY_ALGORITHMS_DETAIL_OVERLAY_SELF_TURN_POINTS_HPP
  10 #define BOOST_GEOMETRY_ALGORITHMS_DETAIL_OVERLAY_SELF_TURN_POINTS_HPP
  11
  12
  13 #include <cstddef>
  14
  15 #include <boost/mpl/vector_c.hpp>
  16 #include <boost/range.hpp>
  17
  18 #include <boost/geometry/core/access.hpp>
  19 #include <boost/geometry/core/coordinate_dimension.hpp>
  20 #include <boost/geometry/core/tags.hpp>
  21
  22 #include <boost/geometry/geometries/concepts/check.hpp>
  23
  24 #include <boost/geometry/algorithms/detail/disjoint/box_box.hpp>
  25 #include <boost/geometry/algorithms/detail/partition.hpp>
  26 #include <boost/geometry/algorithms/detail/overlay/get_turns.hpp>
  27 #include <boost/geometry/algorithms/detail/sections/section_box_policies.hpp>
  28
  29 #include <boost/geometry/geometries/box.hpp>
  30
  31 #include <boost/geometry/util/condition.hpp>
  32
  33
  34 namespace boost { namespace geometry
  35 {
  36
  37 #ifndef DOXYGEN_NO_DETAIL
  38 namespace detail { namespace self_get_turn_points
  39 {
  40
  41 struct no_interrupt_policy
  42 {
  43     static bool const enabled = false;
  44     static bool const has_intersections = false;
  45
  46
  47     template <typename Range>
  48     static inline bool apply(Range const&)
  49     {
  50         return false;
  51     }
  52 };
  53
  54
  55
  56
  57 class self_ip_exception : public geometry::exception {};
  58
  59 template
  60 <
  61     typename Geometry,
  62     typename Turns,
  63     typename TurnPolicy,
  64     typename RobustPolicy,
  65     typename InterruptPolicy
  66 >
  67 struct self_section_visitor
  68 {
  69     Geometry const& m_geometry;
  70     RobustPolicy const& m_rescale_policy;
  71     Turns& m_turns;
  72     InterruptPolicy& m_interrupt_policy;
  73
  74     inline self_section_visitor(Geometry const& g,
  75             RobustPolicy const& rp,
  76             Turns& turns, InterruptPolicy& ip)
  77         : m_geometry(g)
  78         , m_rescale_policy(rp)
  79         , m_turns(turns)
  80         , m_interrupt_policy(ip)
  81     {}
  82
  83     template <typename Section>
  84     inline bool apply(Section const& sec1, Section const& sec2)
  85     {
  86         if (! detail::disjoint::disjoint_box_box(sec1.bounding_box, sec2.bounding_box)
  87                 && ! sec1.duplicate
  88                 && ! sec2.duplicate)
  89         {
  90             detail::get_turns::get_turns_in_sections
  91                     <
  92                         Geometry, Geometry,
  93                         false, false,
  94                         Section, Section,
  95                         TurnPolicy
  96                     >::apply(
  97                             0, m_geometry, sec1,
  98                             0, m_geometry, sec2,
  99                             false,
 100                             m_rescale_policy,
 101                             m_turns, m_interrupt_policy);
 102         }
 103         if (BOOST_GEOMETRY_CONDITION(m_interrupt_policy.has_intersections))
 104         {
 105             // TODO: we should give partition an interrupt policy.
 106             // Now we throw, and catch below, to stop the partition loop.
 107             throw self_ip_exception();
 108         }
 109         return true;
 110     }
 111
 112 };
 113
 114
 115
 116 template<typename TurnPolicy>
 117 struct get_turns
 118 {
 119     template <typename Geometry, typename RobustPolicy, typename Turns, typename InterruptPolicy>
 120     static inline bool apply(
 121             Geometry const& geometry,
 122             RobustPolicy const& robust_policy,
 123             Turns& turns,
 124             InterruptPolicy& interrupt_policy)
 125     {
 126         typedef model::box
 127             <
 128                 typename geometry::robust_point_type
 129                 <
 130                     typename geometry::point_type<Geometry>::type,
 131                     RobustPolicy
 132                 >::type
 133             > box_type;
 134
 135         typedef geometry::sections<box_type, 1> sections_type;
 136
 137         typedef boost::mpl::vector_c<std::size_t, 0> dimensions;
 138
 139         sections_type sec;
 140         geometry::sectionalize<false, dimensions>(geometry, robust_policy, sec);
 141
 142         self_section_visitor
 143             <
 144                 Geometry,
 145                 Turns, TurnPolicy, RobustPolicy, InterruptPolicy
 146             > visitor(geometry, robust_policy, turns, interrupt_policy);
 147
 148         try
 149         {
 150             geometry::partition
 151                 <
 152                     box_type,
 153                     detail::section::get_section_box,
 154                     detail::section::overlaps_section_box
 155                 >::apply(sec, visitor);
 156         }
 157         catch(self_ip_exception const& )
 158         {
 159             return false;
 160         }
 161
 162         return true;
 163     }
 164 };
 165
 166
 167 }} // namespace detail::self_get_turn_points
 168 #endif // DOXYGEN_NO_DETAIL
 169
 170
 171 #ifndef DOXYGEN_NO_DISPATCH
 172 namespace dispatch
 173 {
 174
 175 template
 176 <
 177     typename GeometryTag,
 178     typename Geometry,
 179     typename TurnPolicy
 180 >
 181 struct self_get_turn_points
 182 {
 183 };
 184
 185
 186 template
 187 <
 188     typename Ring,
 189     typename TurnPolicy
 190 >
 191 struct self_get_turn_points
 192     <
 193         ring_tag, Ring,
 194         TurnPolicy
 195     >
 196     : detail::self_get_turn_points::get_turns<TurnPolicy>
 197 {};
 198
 199
 200 template
 201 <
 202     typename Box,
 203     typename TurnPolicy
 204 >
 205 struct self_get_turn_points
 206     <
 207         box_tag, Box,
 208         TurnPolicy
 209     >
 210 {
 211     template <typename RobustPolicy, typename Turns, typename InterruptPolicy>
 212     static inline bool apply(
 213             Box const& ,
 214             RobustPolicy const& ,
 215             Turns& ,
 216             InterruptPolicy& )
 217     {
 218         return true;
 219     }
 220 };
 221
 222
 223 template
 224 <
 225     typename Polygon,
 226     typename TurnPolicy
 227 >
 228 struct self_get_turn_points
 229     <
 230         polygon_tag, Polygon,
 231         TurnPolicy
 232     >
 233     : detail::self_get_turn_points::get_turns<TurnPolicy>
 234 {};
 235
 236
 237 template
 238 <
 239     typename MultiPolygon,
 240     typename TurnPolicy
 241 >
 242 struct self_get_turn_points
 243     <
 244         multi_polygon_tag, MultiPolygon,
 245         TurnPolicy
 246     >
 247     : detail::self_get_turn_points::get_turns<TurnPolicy>
 248 {};
 249
 250
 251 } // namespace dispatch
 252 #endif // DOXYGEN_NO_DISPATCH
 253
 254
 255 /*!
 256     \brief Calculate self intersections of a geometry
 257     \ingroup overlay
 258     \tparam Geometry geometry type
 259     \tparam Turns type of intersection container
 260                 (e.g. vector of "intersection/turn point"'s)
 261     \param geometry geometry
 262     \param robust_policy policy to handle robustness issues
 263     \param turns container which will contain intersection points
 264     \param interrupt_policy policy determining if process is stopped
 265         when intersection is found
 266  */
 267 template
 268 <
 269     typename AssignPolicy,
 270     typename Geometry,
 271     typename RobustPolicy,
 272     typename Turns,
 273     typename InterruptPolicy
 274 >
 275 inline void self_turns(Geometry const& geometry,
 276             RobustPolicy const& robust_policy,
 277             Turns& turns, InterruptPolicy& interrupt_policy)
 278 {
 279     concepts::check<Geometry const>();
 280
 281     typedef detail::overlay::get_turn_info<detail::overlay::assign_null_policy> turn_policy;
 282
 283     dispatch::self_get_turn_points
 284             <
 285                 typename tag<Geometry>::type,
 286                 Geometry,
 287                 turn_policy
 288             >::apply(geometry, robust_policy, turns, interrupt_policy);
 289 }
 290
 291
 292
 293 }} // namespace boost::geometry
 294
 295 #endif // BOOST_GEOMETRY_ALGORITHMS_DETAIL_OVERLAY_SELF_TURN_POINTS_HPP