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