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