ceph/src/boost/libs/geometry/include/boost/geometry/algorithms/detail/is_simple/linear.hpp

   1 // Boost.Geometry (aka GGL, Generic Geometry Library)
   2
   3 // Copyright (c) 2014-2015, Oracle and/or its affiliates.
   4
   5 // Contributed and/or modified by Menelaos Karavelas, on behalf of Oracle
   6
   7 // Licensed under the Boost Software License version 1.0.
   8 // http://www.boost.org/users/license.html
   9
  10 #ifndef BOOST_GEOMETRY_ALGORITHMS_DETAIL_IS_SIMPLE_LINEAR_HPP
  11 #define BOOST_GEOMETRY_ALGORITHMS_DETAIL_IS_SIMPLE_LINEAR_HPP
  12
  13 #include <algorithm>
  14 #include <deque>
  15
  16 #include <boost/range.hpp>
  17
  18 #include <boost/geometry/core/assert.hpp>
  19 #include <boost/geometry/core/closure.hpp>
  20 #include <boost/geometry/core/coordinate_type.hpp>
  21 #include <boost/geometry/core/point_type.hpp>
  22 #include <boost/geometry/core/tag.hpp>
  23 #include <boost/geometry/core/tags.hpp>
  24
  25 #include <boost/geometry/util/range.hpp>
  26
  27 #include <boost/geometry/policies/predicate_based_interrupt_policy.hpp>
  28 #include <boost/geometry/policies/robustness/no_rescale_policy.hpp>
  29 #include <boost/geometry/policies/robustness/segment_ratio.hpp>
  30
  31 #include <boost/geometry/algorithms/equals.hpp>
  32 #include <boost/geometry/algorithms/intersects.hpp>
  33 #include <boost/geometry/algorithms/not_implemented.hpp>
  34
  35 #include <boost/geometry/algorithms/detail/check_iterator_range.hpp>
  36 #include <boost/geometry/algorithms/detail/signed_size_type.hpp>
  37
  38 #include <boost/geometry/algorithms/detail/disjoint/linear_linear.hpp>
  39 #include <boost/geometry/algorithms/detail/overlay/get_turn_info.hpp>
  40 #include <boost/geometry/algorithms/detail/overlay/turn_info.hpp>
  41 #include <boost/geometry/algorithms/detail/overlay/self_turn_points.hpp>
  42 #include <boost/geometry/algorithms/detail/is_valid/has_duplicates.hpp>
  43 #include <boost/geometry/algorithms/detail/is_valid/has_spikes.hpp>
  44
  45 #include <boost/geometry/algorithms/detail/is_simple/debug_print_boundary_points.hpp>
  46 #include <boost/geometry/algorithms/detail/is_simple/failure_policy.hpp>
  47 #include <boost/geometry/algorithms/detail/is_valid/debug_print_turns.hpp>
  48
  49 #include <boost/geometry/algorithms/dispatch/is_simple.hpp>
  50
  51
  52 namespace boost { namespace geometry
  53 {
  54
  55
  56 #ifndef DOXYGEN_NO_DETAIL
  57 namespace detail { namespace is_simple
  58 {
  59
  60
  61 template <typename Turn>
  62 inline bool check_segment_indices(Turn const& turn,
  63                                   signed_size_type last_index)
  64 {
  65     return
  66         (turn.operations[0].seg_id.segment_index == 0
  67          && turn.operations[1].seg_id.segment_index == last_index)
  68         ||
  69         (turn.operations[0].seg_id.segment_index == 0
  70          && turn.operations[1].seg_id.segment_index == last_index);
  71 }
  72
  73
  74 template <typename Geometry, typename Tag = typename tag<Geometry>::type>
  75 class is_acceptable_turn
  76     : not_implemented<Geometry>
  77 {};
  78
  79 template <typename Linestring>
  80 class is_acceptable_turn<Linestring, linestring_tag>
  81 {
  82 public:
  83     is_acceptable_turn(Linestring const& linestring)
  84         : m_linestring(linestring)
  85         , m_is_closed(geometry::equals(range::front(linestring),
  86                                        range::back(linestring)))
  87     {}
  88
  89     template <typename Turn>
  90     inline bool apply(Turn const& turn) const
  91     {
  92         BOOST_GEOMETRY_ASSERT(boost::size(m_linestring) > 1);
  93         return m_is_closed
  94             && turn.method == overlay::method_none
  95             && check_segment_indices(turn, boost::size(m_linestring) - 2)
  96             && turn.operations[0].fraction.is_zero();
  97     }
  98
  99 private:
 100     Linestring const& m_linestring;
 101     bool const m_is_closed;
 102 };
 103
 104 template <typename MultiLinestring>
 105 class is_acceptable_turn<MultiLinestring, multi_linestring_tag>
 106 {
 107 private:
 108     typedef typename boost::range_value<MultiLinestring>::type linestring_type;
 109     typedef is_acceptable_turn<linestring_type> base_type;
 110
 111     template <typename Point, typename Linestring>
 112     static inline bool is_boundary_point_of(Point const& point,
 113                                             Linestring const& linestring)
 114     {
 115         BOOST_GEOMETRY_ASSERT(boost::size(linestring) > 1);
 116         return
 117             ! geometry::equals(range::front(linestring),
 118                                range::back(linestring))
 119             &&
 120             (geometry::equals(point, range::front(linestring))
 121              || geometry::equals(point, range::back(linestring)));
 122     }
 123
 124     template <typename Turn, typename Linestring>
 125     static inline bool is_closing_point_of(Turn const& turn,
 126                                            Linestring const& linestring)
 127     {
 128         BOOST_GEOMETRY_ASSERT(boost::size(linestring) > 1);
 129         return
 130             turn.method == overlay::method_none
 131             &&
 132             check_segment_indices(turn, boost::size(linestring) - 2)
 133             &&
 134             geometry::equals(range::front(linestring), range::back(linestring))
 135             &&
 136             turn.operations[0].fraction.is_zero();
 137             ;
 138     }
 139
 140     template <typename Linestring1, typename Linestring2>
 141     static inline bool have_same_boundary_points(Linestring1 const& ls1,
 142                                                  Linestring2 const& ls2)
 143     {
 144         return
 145             geometry::equals(range::front(ls1), range::front(ls2))
 146             ?
 147             geometry::equals(range::back(ls1), range::back(ls2))
 148             :
 149             (geometry::equals(range::front(ls1), range::back(ls2))
 150              &&
 151              geometry::equals(range::back(ls1), range::front(ls2)))
 152             ;
 153     }
 154
 155 public:
 156     is_acceptable_turn(MultiLinestring const& multilinestring)
 157         : m_multilinestring(multilinestring)
 158     {}
 159
 160     template <typename Turn>
 161     inline bool apply(Turn const& turn) const
 162     {
 163         linestring_type const& ls1 =
 164             range::at(m_multilinestring, turn.operations[0].seg_id.multi_index);
 165
 166         linestring_type const& ls2 =
 167             range::at(m_multilinestring, turn.operations[1].seg_id.multi_index);
 168
 169         if (turn.operations[0].seg_id.multi_index
 170             == turn.operations[1].seg_id.multi_index)
 171         {
 172             return is_closing_point_of(turn, ls1);
 173         }
 174
 175         return
 176             is_boundary_point_of(turn.point, ls1)
 177             && is_boundary_point_of(turn.point, ls2)
 178             &&
 179             ( boost::size(ls1) != 2
 180               || boost::size(ls2) != 2
 181               || ! have_same_boundary_points(ls1, ls2) );
 182     }
 183
 184 private:
 185     MultiLinestring const& m_multilinestring;
 186 };
 187
 188
 189 template <typename Linear>
 190 inline bool has_self_intersections(Linear const& linear)
 191 {
 192     typedef typename point_type<Linear>::type point_type;
 193
 194     // compute self turns
 195     typedef detail::overlay::turn_info
 196         <
 197             point_type,
 198             geometry::segment_ratio
 199                 <
 200                     typename geometry::coordinate_type<point_type>::type
 201                 >
 202         > turn_info;
 203
 204     std::deque<turn_info> turns;
 205
 206     typedef detail::overlay::get_turn_info
 207         <
 208             detail::disjoint::assign_disjoint_policy
 209         > turn_policy;
 210
 211     is_acceptable_turn<Linear> predicate(linear);
 212     detail::overlay::predicate_based_interrupt_policy
 213         <
 214             is_acceptable_turn<Linear>
 215         > interrupt_policy(predicate);
 216
 217     detail::self_get_turn_points::get_turns
 218         <
 219             turn_policy
 220         >::apply(linear,
 221                  detail::no_rescale_policy(),
 222                  turns,
 223                  interrupt_policy);
 224
 225     detail::is_valid::debug_print_turns(turns.begin(), turns.end());
 226     debug_print_boundary_points(linear);
 227
 228     return interrupt_policy.has_intersections;
 229 }
 230
 231
 232 template <typename Linestring, bool CheckSelfIntersections = true>
 233 struct is_simple_linestring
 234 {
 235     static inline bool apply(Linestring const& linestring)
 236     {
 237         simplicity_failure_policy policy;
 238         return ! boost::empty(linestring)
 239             && ! detail::is_valid::has_duplicates
 240                     <
 241                         Linestring, closed
 242                     >::apply(linestring, policy)
 243             && ! detail::is_valid::has_spikes
 244                     <
 245                         Linestring, closed
 246                     >::apply(linestring, policy)
 247             && ! (CheckSelfIntersections && has_self_intersections(linestring));
 248     }
 249 };
 250
 251
 252 template <typename MultiLinestring>
 253 struct is_simple_multilinestring
 254 {
 255     static inline bool apply(MultiLinestring const& multilinestring)
 256     {
 257         // check each of the linestrings for simplicity
 258         // but do not compute self-intersections yet; these will be
 259         // computed for the entire multilinestring
 260         if ( ! detail::check_iterator_range
 261                  <
 262                      is_simple_linestring
 263                          <
 264                              typename boost::range_value<MultiLinestring>::type,
 265                              false // do not compute self-intersections
 266                          >,
 267                      true // allow empty multilinestring
 268                  >::apply(boost::begin(multilinestring),
 269                           boost::end(multilinestring))
 270              )
 271         {
 272             return false;
 273         }
 274
 275         return ! has_self_intersections(multilinestring);
 276     }
 277 };
 278
 279
 280
 281 }} // namespace detail::is_simple
 282 #endif // DOXYGEN_NO_DETAIL
 283
 284
 285
 286 #ifndef DOXYGEN_NO_DISPATCH
 287 namespace dispatch
 288 {
 289
 290 // A linestring is a curve.
 291 // A curve is simple if it does not pass through the same point twice,
 292 // with the possible exception of its two endpoints
 293 //
 294 // Reference: OGC 06-103r4 (6.1.6.1)
 295 template <typename Linestring>
 296 struct is_simple<Linestring, linestring_tag>
 297     : detail::is_simple::is_simple_linestring<Linestring>
 298 {};
 299
 300
 301 // A MultiLinestring is a MultiCurve
 302 // A MultiCurve is simple if all of its elements are simple and the
 303 // only intersections between any two elements occur at Points that
 304 // are on the boundaries of both elements.
 305 //
 306 // Reference: OGC 06-103r4 (6.1.8.1; Fig. 9)
 307 template <typename MultiLinestring>
 308 struct is_simple<MultiLinestring, multi_linestring_tag>
 309     : detail::is_simple::is_simple_multilinestring<MultiLinestring>
 310 {};
 311
 312
 313 } // namespace dispatch
 314 #endif // DOXYGEN_NO_DISPATCH
 315
 316
 317 }} // namespace boost::geometry
 318
 319
 320 #endif // BOOST_GEOMETRY_ALGORITHMS_DETAIL_IS_SIMPLE_LINEAR_HPP