]>
Commit | Line | Data |
---|---|---|
7c673cae FG |
1 | // Boost.Geometry (aka GGL, Generic Geometry Library) |
2 | ||
11fdf7f2 TL |
3 | // Copyright (c) 2017 Adam Wulkiewicz, Lodz, Poland. |
4 | ||
1e59de90 | 5 | // Copyright (c) 2014-2021, Oracle and/or its affiliates. |
7c673cae FG |
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> | |
92f5a8d4 | 23 | #include <boost/geometry/core/tags.hpp> |
7c673cae FG |
24 | |
25 | #include <boost/geometry/util/order_as_direction.hpp> | |
26 | #include <boost/geometry/util/range.hpp> | |
27 | ||
7c673cae FG |
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> | |
92f5a8d4 | 33 | #include <boost/geometry/algorithms/detail/equals/point_point.hpp> |
7c673cae FG |
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> | |
92f5a8d4 | 39 | #include <boost/geometry/algorithms/dispatch/is_valid.hpp> |
7c673cae | 40 | |
20effc67 TL |
41 | // TEMP - with UmberllaStrategy this will be not needed |
42 | #include <boost/geometry/strategy/area.hpp> | |
43 | #include <boost/geometry/strategies/area/services.hpp> | |
44 | // TODO: use point_order instead of area | |
45 | ||
7c673cae FG |
46 | |
47 | #ifdef BOOST_GEOMETRY_TEST_DEBUG | |
48 | #include <boost/geometry/io/dsv/write.hpp> | |
49 | #endif | |
50 | ||
51 | namespace boost { namespace geometry | |
52 | { | |
53 | ||
54 | ||
55 | #ifndef DOXYGEN_NO_DETAIL | |
56 | namespace detail { namespace is_valid | |
57 | { | |
58 | ||
59 | ||
60 | // struct to check whether a ring is topologically closed | |
1e59de90 | 61 | template <typename Ring, closure_selector Closure = geometry::closure<Ring>::value> |
7c673cae FG |
62 | struct is_topologically_closed |
63 | { | |
1e59de90 TL |
64 | template <typename VisitPolicy, typename Strategy> |
65 | static inline bool apply(Ring const&, VisitPolicy& visitor, Strategy const&) | |
7c673cae FG |
66 | { |
67 | boost::ignore_unused(visitor); | |
68 | ||
69 | return visitor.template apply<no_failure>(); | |
70 | } | |
71 | }; | |
72 | ||
73 | template <typename Ring> | |
74 | struct is_topologically_closed<Ring, closed> | |
75 | { | |
1e59de90 TL |
76 | template <typename VisitPolicy, typename Strategy> |
77 | static inline bool apply(Ring const& ring, VisitPolicy& visitor, Strategy const& strategy) | |
7c673cae FG |
78 | { |
79 | boost::ignore_unused(visitor); | |
80 | ||
1e59de90 TL |
81 | using geometry::detail::equals::equals_point_point; |
82 | if (equals_point_point(range::front(ring), range::back(ring), strategy)) | |
7c673cae FG |
83 | { |
84 | return visitor.template apply<no_failure>(); | |
85 | } | |
86 | else | |
87 | { | |
88 | return visitor.template apply<failure_not_closed>(); | |
89 | } | |
90 | } | |
91 | }; | |
92 | ||
93 | ||
1e59de90 | 94 | // TODO: use calculate_point_order here |
7c673cae FG |
95 | template <typename Ring, bool IsInteriorRing> |
96 | struct is_properly_oriented | |
97 | { | |
b32b8144 FG |
98 | template <typename VisitPolicy, typename Strategy> |
99 | static inline bool apply(Ring const& ring, VisitPolicy& visitor, | |
100 | Strategy const& strategy) | |
101 | { | |
102 | boost::ignore_unused(visitor); | |
7c673cae | 103 | |
7c673cae | 104 | // Check area |
1e59de90 TL |
105 | auto const area = detail::area::ring_area::apply(ring, strategy); |
106 | decltype(area) const zero = 0; | |
107 | ||
108 | if (IsInteriorRing ? (area < zero) : (area > zero)) | |
7c673cae FG |
109 | { |
110 | return visitor.template apply<no_failure>(); | |
111 | } | |
112 | else | |
113 | { | |
114 | return visitor.template apply<failure_wrong_orientation>(); | |
115 | } | |
116 | } | |
117 | }; | |
118 | ||
119 | ||
120 | ||
121 | template | |
122 | < | |
123 | typename Ring, | |
124 | bool CheckSelfIntersections = true, | |
125 | bool IsInteriorRing = false | |
126 | > | |
127 | struct is_valid_ring | |
128 | { | |
b32b8144 FG |
129 | template <typename VisitPolicy, typename Strategy> |
130 | static inline bool apply(Ring const& ring, VisitPolicy& visitor, | |
131 | Strategy const& strategy) | |
7c673cae FG |
132 | { |
133 | // return invalid if any of the following condition holds: | |
134 | // (a) the ring's point coordinates are not invalid (e.g., NaN) | |
135 | // (b) the ring's size is below the minimal one | |
136 | // (c) the ring consists of at most two distinct points | |
137 | // (d) the ring is not topologically closed | |
138 | // (e) the ring has spikes | |
139 | // (f) the ring has duplicate points (if AllowDuplicates is false) | |
140 | // (g) the boundary of the ring has self-intersections | |
141 | // (h) the order of the points is inconsistent with the defined order | |
142 | // | |
143 | // Note: no need to check if the area is zero. If this is the | |
144 | // case, then the ring must have at least two spikes, which is | |
145 | // checked by condition (d). | |
146 | ||
147 | if (has_invalid_coordinate<Ring>::apply(ring, visitor)) | |
148 | { | |
149 | return false; | |
150 | } | |
151 | ||
1e59de90 | 152 | if (boost::size(ring) < detail::minimum_ring_size<Ring>::value) |
7c673cae FG |
153 | { |
154 | return visitor.template apply<failure_few_points>(); | |
155 | } | |
156 | ||
1e59de90 TL |
157 | detail::closed_view<Ring const> const view(ring); |
158 | ||
7c673cae FG |
159 | if (detail::num_distinct_consecutive_points |
160 | < | |
1e59de90 TL |
161 | decltype(view), 4u, true |
162 | >::apply(view, strategy) | |
7c673cae FG |
163 | < 4u) |
164 | { | |
165 | return | |
166 | visitor.template apply<failure_wrong_topological_dimension>(); | |
167 | } | |
168 | ||
169 | return | |
1e59de90 TL |
170 | is_topologically_closed<Ring>::apply(ring, visitor, strategy) |
171 | && ! has_duplicates<Ring>::apply(ring, visitor, strategy) | |
172 | && ! has_spikes<Ring>::apply(ring, visitor, strategy) | |
7c673cae | 173 | && (! CheckSelfIntersections |
92f5a8d4 | 174 | || has_valid_self_turns<Ring, typename Strategy::cs_tag>::apply(ring, visitor, strategy)) |
b32b8144 | 175 | && is_properly_oriented<Ring, IsInteriorRing>::apply(ring, visitor, strategy); |
7c673cae FG |
176 | } |
177 | }; | |
178 | ||
179 | ||
180 | }} // namespace detail::is_valid | |
181 | #endif // DOXYGEN_NO_DETAIL | |
182 | ||
183 | ||
184 | ||
185 | #ifndef DOXYGEN_NO_DISPATCH | |
186 | namespace dispatch | |
187 | { | |
188 | ||
189 | // A Ring is a Polygon with exterior boundary only. | |
190 | // The Ring's boundary must be a LinearRing (see OGC 06-103-r4, | |
191 | // 6.1.7.1, for the definition of LinearRing) | |
192 | // | |
193 | // Reference (for polygon validity): OGC 06-103r4 (6.1.11.1) | |
194 | template <typename Ring, bool AllowEmptyMultiGeometries> | |
195 | struct is_valid | |
196 | < | |
197 | Ring, ring_tag, AllowEmptyMultiGeometries | |
198 | > : detail::is_valid::is_valid_ring<Ring> | |
199 | {}; | |
200 | ||
201 | ||
202 | } // namespace dispatch | |
203 | #endif // DOXYGEN_NO_DISPATCH | |
204 | ||
205 | ||
206 | }} // namespace boost::geometry | |
207 | ||
208 | #endif // BOOST_GEOMETRY_ALGORITHMS_DETAIL_IS_VALID_RING_HPP |