1 // Boost.Geometry (aka GGL, Generic Geometry Library)
2 
3 // Copyright (c) 2014-2017, 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_duplicates.hpp>
34 #include <boost/geometry/algorithms/detail/is_valid/has_invalid_coordinate.hpp>
35 #include <boost/geometry/algorithms/detail/is_valid/has_spikes.hpp>
36 #include <boost/geometry/algorithms/detail/is_valid/has_valid_self_turns.hpp>
37 
38 #include <boost/geometry/strategies/area.hpp>
39 
40 #ifdef BOOST_GEOMETRY_TEST_DEBUG
41 #include <boost/geometry/io/dsv/write.hpp>
42 #endif
43 
44 namespace boost { namespace geometry
45 {
46 
47 
48 #ifndef DOXYGEN_NO_DETAIL
49 namespace detail { namespace is_valid
50 {
51 
52 
53 // struct to check whether a ring is topologically closed
54 template <typename Ring, closure_selector Closure /* open */>
55 struct is_topologically_closed
56 {
57     template <typename VisitPolicy>
applyboost::geometry::detail::is_valid::is_topologically_closed58     static inline bool apply(Ring const&, VisitPolicy& visitor)
59     {
60         boost::ignore_unused(visitor);
61 
62         return visitor.template apply<no_failure>();
63     }
64 };
65 
66 template <typename Ring>
67 struct is_topologically_closed<Ring, closed>
68 {
69     template <typename VisitPolicy>
applyboost::geometry::detail::is_valid::is_topologically_closed70     static inline bool apply(Ring const& ring, VisitPolicy& visitor)
71     {
72         boost::ignore_unused(visitor);
73 
74         if (geometry::equals(range::front(ring), range::back(ring)))
75         {
76             return visitor.template apply<no_failure>();
77         }
78         else
79         {
80             return visitor.template apply<failure_not_closed>();
81         }
82     }
83 };
84 
85 
86 
87 template <typename ResultType, bool IsInteriorRing /* false */>
88 struct ring_area_predicate
89 {
90     typedef std::greater<ResultType> type;
91 };
92 
93 template <typename ResultType>
94 struct ring_area_predicate<ResultType, true>
95 {
96     typedef std::less<ResultType> type;
97 };
98 
99 
100 
101 template <typename Ring, bool IsInteriorRing>
102 struct is_properly_oriented
103 {
104     template <typename VisitPolicy, typename Strategy>
applyboost::geometry::detail::is_valid::is_properly_oriented105     static inline bool apply(Ring const& ring, VisitPolicy& visitor,
106                              Strategy const& strategy)
107     {
108         boost::ignore_unused(visitor);
109 
110         typedef typename point_type<Ring>::type point_type;
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                 point_type
121             >::type::return_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<point_type>());
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>
applyboost::geometry::detail::is_valid::is_valid_ring155     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
238