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