ceph/src/boost/boost/geometry/algorithms/detail/is_valid/ring.hpp

   1 // Boost.Geometry (aka GGL, Generic Geometry Library)
   2
   3 // Copyright (c) 2017 Adam Wulkiewicz, Lodz, Poland.
   4
   5 // Copyright (c) 2014-2017, Oracle and/or its affiliates.
   6
   7 // Contributed and/or modified by Menelaos Karavelas, on behalf of Oracle
   8 // Contributed and/or modified by Adam Wulkiewicz, on behalf of Oracle
   9
  10 // Licensed under the Boost Software License version 1.0.
  11 // http://www.boost.org/users/license.html
  12
  13 #ifndef BOOST_GEOMETRY_ALGORITHMS_DETAIL_IS_VALID_RING_HPP
  14 #define BOOST_GEOMETRY_ALGORITHMS_DETAIL_IS_VALID_RING_HPP
  15
  16 #include <deque>
  17
  18 #include <boost/core/ignore_unused.hpp>
  19
  20 #include <boost/geometry/core/closure.hpp>
  21 #include <boost/geometry/core/cs.hpp>
  22 #include <boost/geometry/core/point_order.hpp>
  23
  24 #include <boost/geometry/util/order_as_direction.hpp>
  25 #include <boost/geometry/util/range.hpp>
  26
  27 #include <boost/geometry/algorithms/equals.hpp>
  28
  29 #include <boost/geometry/views/closeable_view.hpp>
  30
  31 #include <boost/geometry/algorithms/area.hpp>
  32 #include <boost/geometry/algorithms/intersects.hpp>
  33 #include <boost/geometry/algorithms/validity_failure_type.hpp>
  34 #include <boost/geometry/algorithms/detail/num_distinct_consecutive_points.hpp>
  35 #include <boost/geometry/algorithms/detail/is_valid/has_duplicates.hpp>
  36 #include <boost/geometry/algorithms/detail/is_valid/has_invalid_coordinate.hpp>
  37 #include <boost/geometry/algorithms/detail/is_valid/has_spikes.hpp>
  38 #include <boost/geometry/algorithms/detail/is_valid/has_valid_self_turns.hpp>
  39
  40 #include <boost/geometry/strategies/area.hpp>
  41
  42 #ifdef BOOST_GEOMETRY_TEST_DEBUG
  43 #include <boost/geometry/io/dsv/write.hpp>
  44 #endif
  45
  46 namespace boost { namespace geometry
  47 {
  48
  49
  50 #ifndef DOXYGEN_NO_DETAIL
  51 namespace detail { namespace is_valid
  52 {
  53
  54
  55 // struct to check whether a ring is topologically closed
  56 template <typename Ring, closure_selector Closure /* open */>
  57 struct is_topologically_closed
  58 {
  59     template <typename VisitPolicy>
  60     static inline bool apply(Ring const&, VisitPolicy& visitor)
  61     {
  62         boost::ignore_unused(visitor);
  63
  64         return visitor.template apply<no_failure>();
  65     }
  66 };
  67
  68 template <typename Ring>
  69 struct is_topologically_closed<Ring, closed>
  70 {
  71     template <typename VisitPolicy>
  72     static inline bool apply(Ring const& ring, VisitPolicy& visitor)
  73     {
  74         boost::ignore_unused(visitor);
  75
  76         if (geometry::equals(range::front(ring), range::back(ring)))
  77         {
  78             return visitor.template apply<no_failure>();
  79         }
  80         else
  81         {
  82             return visitor.template apply<failure_not_closed>();
  83         }
  84     }
  85 };
  86
  87
  88
  89 template <typename ResultType, bool IsInteriorRing /* false */>
  90 struct ring_area_predicate
  91 {
  92     typedef std::greater<ResultType> type;
  93 };
  94
  95 template <typename ResultType>
  96 struct ring_area_predicate<ResultType, true>
  97 {
  98     typedef std::less<ResultType> type;
  99 };
 100
 101
 102
 103 template <typename Ring, bool IsInteriorRing>
 104 struct is_properly_oriented
 105 {
 106     template <typename VisitPolicy, typename Strategy>
 107     static inline bool apply(Ring const& ring, VisitPolicy& visitor,
 108                              Strategy const& strategy)
 109     {
 110         boost::ignore_unused(visitor);
 111
 112         typedef detail::area::ring_area
 113             <
 114                 order_as_direction<geometry::point_order<Ring>::value>::value,
 115                 geometry::closure<Ring>::value
 116             > ring_area_type;
 117
 118         typedef typename Strategy::template area_strategy
 119             <
 120                 Ring
 121             >::type::template result_type<Ring>::type area_result_type;
 122
 123         typename ring_area_predicate
 124             <
 125                 area_result_type, IsInteriorRing
 126             >::type predicate;
 127
 128         // Check area
 129         area_result_type const zero = 0;
 130         area_result_type const area
 131             = ring_area_type::apply(ring,
 132                                     strategy.template get_area_strategy<Ring>());
 133         if (predicate(area, zero))
 134         {
 135             return visitor.template apply<no_failure>();
 136         }
 137         else
 138         {
 139             return visitor.template apply<failure_wrong_orientation>();
 140         }
 141     }
 142 };
 143
 144
 145
 146 template
 147 <
 148     typename Ring,
 149     bool CheckSelfIntersections = true,
 150     bool IsInteriorRing = false
 151 >
 152 struct is_valid_ring
 153 {
 154     template <typename VisitPolicy, typename Strategy>
 155     static inline bool apply(Ring const& ring, VisitPolicy& visitor,
 156                              Strategy const& strategy)
 157     {
 158         // return invalid if any of the following condition holds:
 159         // (a) the ring's point coordinates are not invalid (e.g., NaN)
 160         // (b) the ring's size is below the minimal one
 161         // (c) the ring consists of at most two distinct points
 162         // (d) the ring is not topologically closed
 163         // (e) the ring has spikes
 164         // (f) the ring has duplicate points (if AllowDuplicates is false)
 165         // (g) the boundary of the ring has self-intersections
 166         // (h) the order of the points is inconsistent with the defined order
 167         //
 168         // Note: no need to check if the area is zero. If this is the
 169         // case, then the ring must have at least two spikes, which is
 170         // checked by condition (d).
 171
 172         if (has_invalid_coordinate<Ring>::apply(ring, visitor))
 173         {
 174             return false;
 175         }
 176
 177         closure_selector const closure = geometry::closure<Ring>::value;
 178         typedef typename closeable_view<Ring const, closure>::type view_type;
 179
 180         if (boost::size(ring)
 181             < core_detail::closure::minimum_ring_size<closure>::value)
 182         {
 183             return visitor.template apply<failure_few_points>();
 184         }
 185
 186         view_type const view(ring);
 187         if (detail::num_distinct_consecutive_points
 188                 <
 189                     view_type, 4u, true,
 190                     not_equal_to<typename point_type<Ring>::type>
 191                 >::apply(view)
 192             < 4u)
 193         {
 194             return
 195                 visitor.template apply<failure_wrong_topological_dimension>();
 196         }
 197
 198         return
 199             is_topologically_closed<Ring, closure>::apply(ring, visitor)
 200             && ! has_duplicates<Ring, closure>::apply(ring, visitor)
 201             && ! has_spikes<Ring, closure>::apply(ring, visitor, strategy.get_side_strategy())
 202             && (! CheckSelfIntersections
 203                 || has_valid_self_turns<Ring>::apply(ring, visitor, strategy))
 204             && is_properly_oriented<Ring, IsInteriorRing>::apply(ring, visitor, strategy);
 205     }
 206 };
 207
 208
 209 }} // namespace detail::is_valid
 210 #endif // DOXYGEN_NO_DETAIL
 211
 212
 213
 214 #ifndef DOXYGEN_NO_DISPATCH
 215 namespace dispatch
 216 {
 217
 218 // A Ring is a Polygon with exterior boundary only.
 219 // The Ring's boundary must be a LinearRing (see OGC 06-103-r4,
 220 // 6.1.7.1, for the definition of LinearRing)
 221 //
 222 // Reference (for polygon validity): OGC 06-103r4 (6.1.11.1)
 223 template <typename Ring, bool AllowEmptyMultiGeometries>
 224 struct is_valid
 225     <
 226         Ring, ring_tag, AllowEmptyMultiGeometries
 227     > : detail::is_valid::is_valid_ring<Ring>
 228 {};
 229
 230
 231 } // namespace dispatch
 232 #endif // DOXYGEN_NO_DISPATCH
 233
 234
 235 }} // namespace boost::geometry
 236
 237 #endif // BOOST_GEOMETRY_ALGORITHMS_DETAIL_IS_VALID_RING_HPP