detail/is_valid/ring.hpp

0001 // Boost.Geometry (aka GGL, Generic Geometry Library)
0002
0003 // Copyright (c) 2017 Adam Wulkiewicz, Lodz, Poland.
0004
0005 // Copyright (c) 2014-2021, Oracle and/or its affiliates.
0006
0007 // Contributed and/or modified by Menelaos Karavelas, on behalf of Oracle
0008 // Contributed and/or modified by Adam Wulkiewicz, on behalf of Oracle
0009
0010 // Licensed under the Boost Software License version 1.0.
0011 // http://www.boost.org/users/license.html
0012
0013 #ifndef BOOST_GEOMETRY_ALGORITHMS_DETAIL_IS_VALID_RING_HPP
0014 #define BOOST_GEOMETRY_ALGORITHMS_DETAIL_IS_VALID_RING_HPP
0015
0016 #include <deque>
0017
0018 #include <boost/range/size.hpp>
0019
0020 #include <boost/core/ignore_unused.hpp>
0021
0022 #include <boost/geometry/core/closure.hpp>
0023 #include <boost/geometry/core/cs.hpp>
0024 #include <boost/geometry/core/point_order.hpp>
0025 #include <boost/geometry/core/tags.hpp>
0026
0027 #include <boost/geometry/util/order_as_direction.hpp>
0028 #include <boost/geometry/util/range.hpp>
0029
0030 #include <boost/geometry/views/closeable_view.hpp>
0031
0032 #include <boost/geometry/algorithms/area.hpp>
0033 #include <boost/geometry/algorithms/intersects.hpp>
0034 #include <boost/geometry/algorithms/validity_failure_type.hpp>
0035 #include <boost/geometry/algorithms/detail/equals/point_point.hpp>
0036 #include <boost/geometry/algorithms/detail/num_distinct_consecutive_points.hpp>
0037 #include <boost/geometry/algorithms/detail/is_valid/has_duplicates.hpp>
0038 #include <boost/geometry/algorithms/detail/is_valid/has_invalid_coordinate.hpp>
0039 #include <boost/geometry/algorithms/detail/is_valid/has_spikes.hpp>
0040 #include <boost/geometry/algorithms/detail/is_valid/has_valid_self_turns.hpp>
0041 #include <boost/geometry/algorithms/dispatch/is_valid.hpp>
0042
0043 // TEMP - with UmbrellaStrategy this will be not needed
0044 #include <boost/geometry/strategy/area.hpp>
0045 #include <boost/geometry/strategies/area/services.hpp>
0046 // TODO: use point_order instead of area
0047
0048 #ifdef BOOST_GEOMETRY_TEST_DEBUG
0049 #include <boost/geometry/io/dsv/write.hpp>
0050 #endif
0051
0052 namespace boost { namespace geometry
0053 {
0054
0055
0056 #ifndef DOXYGEN_NO_DETAIL
0057 namespace detail { namespace is_valid
0058 {
0059
0060
0061 // struct to check whether a ring is topologically closed
0062 template <typename Ring, closure_selector Closure = geometry::closure<Ring>::value>
0063 struct is_topologically_closed
0064 {
0065     template <typename VisitPolicy, typename Strategy>
0066     static inline bool apply(Ring const&, VisitPolicy& visitor, Strategy const&)
0067     {
0068         boost::ignore_unused(visitor);
0069
0070         return visitor.template apply<no_failure>();
0071     }
0072 };
0073
0074 template <typename Ring>
0075 struct is_topologically_closed<Ring, closed>
0076 {
0077     template <typename VisitPolicy, typename Strategy>
0078     static inline bool apply(Ring const& ring, VisitPolicy& visitor, Strategy const& strategy)
0079     {
0080         boost::ignore_unused(visitor);
0081
0082         using geometry::detail::equals::equals_point_point;
0083         if (equals_point_point(range::front(ring), range::back(ring), strategy))
0084         {
0085             return visitor.template apply<no_failure>();
0086         }
0087         else
0088         {
0089             return visitor.template apply<failure_not_closed>();
0090         }
0091     }
0092 };
0093
0094
0095 // TODO: use calculate_point_order here
0096 template <typename Ring, bool IsInteriorRing>
0097 struct is_properly_oriented
0098 {
0099     template <typename VisitPolicy, typename Strategy>
0100     static inline bool apply(Ring const& ring, VisitPolicy& visitor,
0101                              Strategy const& strategy)
0102     {
0103         boost::ignore_unused(visitor);
0104
0105         // Check area
0106         auto const area = detail::area::ring_area::apply(ring, strategy);
0107         decltype(area) const zero = 0;
0108
0109         if (IsInteriorRing ? (area < zero) : (area > zero))
0110         {
0111             return visitor.template apply<no_failure>();
0112         }
0113         else
0114         {
0115             return visitor.template apply<failure_wrong_orientation>();
0116         }
0117     }
0118 };
0119
0120
0121
0122 template
0123 <
0124     typename Ring,
0125     bool CheckSelfIntersections = true,
0126     bool IsInteriorRing = false
0127 >
0128 struct is_valid_ring
0129 {
0130     template <typename VisitPolicy, typename Strategy>
0131     static inline bool apply(Ring const& ring, VisitPolicy& visitor,
0132                              Strategy const& strategy)
0133     {
0134         // return invalid if any of the following condition holds:
0135         // (a) the ring's point coordinates are not invalid (e.g., NaN)
0136         // (b) the ring's size is below the minimal one
0137         // (c) the ring consists of at most two distinct points
0138         // (d) the ring is not topologically closed
0139         // (e) the ring has spikes
0140         // (f) the ring has duplicate points (if AllowDuplicates is false)
0141         // (g) the boundary of the ring has self-intersections
0142         // (h) the order of the points is inconsistent with the defined order
0143         //
0144         // Note: no need to check if the area is zero. If this is the
0145         // case, then the ring must have at least two spikes, which is
0146         // checked by condition (d).
0147
0148         if (has_invalid_coordinate<Ring>::apply(ring, visitor))
0149         {
0150             return false;
0151         }
0152
0153         if (boost::size(ring) < detail::minimum_ring_size<Ring>::value)
0154         {
0155             return visitor.template apply<failure_few_points>();
0156         }
0157
0158         detail::closed_view<Ring const> const view(ring);
0159
0160         if (detail::num_distinct_consecutive_points
0161                 <
0162                     decltype(view), 4u, true
0163                 >::apply(view, strategy)
0164             < 4u)
0165         {
0166             return
0167                 visitor.template apply<failure_wrong_topological_dimension>();
0168         }
0169
0170         return
0171             is_topologically_closed<Ring>::apply(ring, visitor, strategy)
0172             && ! has_duplicates<Ring>::apply(ring, visitor, strategy)
0173             && ! has_spikes<Ring>::apply(ring, visitor, strategy)
0174             && (! CheckSelfIntersections
0175                 || has_valid_self_turns<Ring, typename Strategy::cs_tag>::apply(ring, visitor, strategy))
0176             && is_properly_oriented<Ring, IsInteriorRing>::apply(ring, visitor, strategy);
0177     }
0178 };
0179
0180
0181 }} // namespace detail::is_valid
0182 #endif // DOXYGEN_NO_DETAIL
0183
0184
0185
0186 #ifndef DOXYGEN_NO_DISPATCH
0187 namespace dispatch
0188 {
0189
0190 // A Ring is a Polygon with exterior boundary only.
0191 // The Ring's boundary must be a LinearRing (see OGC 06-103-r4,
0192 // 6.1.7.1, for the definition of LinearRing)
0193 //
0194 // Reference (for polygon validity): OGC 06-103r4 (6.1.11.1)
0195 template <typename Ring, bool AllowEmptyMultiGeometries>
0196 struct is_valid
0197     <
0198         Ring, ring_tag, AllowEmptyMultiGeometries
0199     > : detail::is_valid::is_valid_ring<Ring>
0200 {};
0201
0202
0203 } // namespace dispatch
0204 #endif // DOXYGEN_NO_DISPATCH
0205
0206
0207 }} // namespace boost::geometry
0208
0209 #endif // BOOST_GEOMETRY_ALGORITHMS_DETAIL_IS_VALID_RING_HPP