]>
Commit | Line | Data |
---|---|---|
7c673cae FG |
1 | // Boost.Geometry (aka GGL, Generic Geometry Library) |
2 | ||
1e59de90 | 3 | // Copyright (c) 2014-2021, Oracle and/or its affiliates. |
7c673cae | 4 | |
1e59de90 | 5 | // Contributed and/or modified by Vissarion Fysikopoulos, on behalf of Oracle |
7c673cae | 6 | // Contributed and/or modified by Menelaos Karavelas, on behalf of Oracle |
b32b8144 | 7 | // Contributed and/or modified by Adam Wulkiewicz, on behalf of Oracle |
7c673cae FG |
8 | |
9 | // Licensed under the Boost Software License version 1.0. | |
10 | // http://www.boost.org/users/license.html | |
11 | ||
12 | #ifndef BOOST_GEOMETRY_ALGORITHMS_DETAIL_IS_SIMPLE_LINEAR_HPP | |
13 | #define BOOST_GEOMETRY_ALGORITHMS_DETAIL_IS_SIMPLE_LINEAR_HPP | |
14 | ||
15 | #include <algorithm> | |
16 | #include <deque> | |
17 | ||
20effc67 TL |
18 | #include <boost/range/begin.hpp> |
19 | #include <boost/range/empty.hpp> | |
20 | #include <boost/range/end.hpp> | |
21 | #include <boost/range/size.hpp> | |
22 | #include <boost/range/value_type.hpp> | |
7c673cae FG |
23 | |
24 | #include <boost/geometry/core/assert.hpp> | |
25 | #include <boost/geometry/core/closure.hpp> | |
26 | #include <boost/geometry/core/coordinate_type.hpp> | |
27 | #include <boost/geometry/core/point_type.hpp> | |
28 | #include <boost/geometry/core/tag.hpp> | |
29 | #include <boost/geometry/core/tags.hpp> | |
30 | ||
31 | #include <boost/geometry/util/range.hpp> | |
32 | ||
33 | #include <boost/geometry/policies/predicate_based_interrupt_policy.hpp> | |
34 | #include <boost/geometry/policies/robustness/no_rescale_policy.hpp> | |
35 | #include <boost/geometry/policies/robustness/segment_ratio.hpp> | |
36 | ||
7c673cae FG |
37 | #include <boost/geometry/algorithms/intersects.hpp> |
38 | #include <boost/geometry/algorithms/not_implemented.hpp> | |
39 | ||
7c673cae FG |
40 | #include <boost/geometry/algorithms/detail/signed_size_type.hpp> |
41 | ||
42 | #include <boost/geometry/algorithms/detail/disjoint/linear_linear.hpp> | |
92f5a8d4 | 43 | #include <boost/geometry/algorithms/detail/equals/point_point.hpp> |
7c673cae FG |
44 | #include <boost/geometry/algorithms/detail/overlay/get_turn_info.hpp> |
45 | #include <boost/geometry/algorithms/detail/overlay/turn_info.hpp> | |
46 | #include <boost/geometry/algorithms/detail/overlay/self_turn_points.hpp> | |
47 | #include <boost/geometry/algorithms/detail/is_valid/has_duplicates.hpp> | |
48 | #include <boost/geometry/algorithms/detail/is_valid/has_spikes.hpp> | |
49 | ||
50 | #include <boost/geometry/algorithms/detail/is_simple/debug_print_boundary_points.hpp> | |
51 | #include <boost/geometry/algorithms/detail/is_simple/failure_policy.hpp> | |
52 | #include <boost/geometry/algorithms/detail/is_valid/debug_print_turns.hpp> | |
53 | ||
54 | #include <boost/geometry/algorithms/dispatch/is_simple.hpp> | |
55 | ||
b32b8144 FG |
56 | #include <boost/geometry/strategies/intersection.hpp> |
57 | ||
7c673cae FG |
58 | |
59 | namespace boost { namespace geometry | |
60 | { | |
61 | ||
62 | ||
63 | #ifndef DOXYGEN_NO_DETAIL | |
64 | namespace detail { namespace is_simple | |
65 | { | |
66 | ||
67 | ||
68 | template <typename Turn> | |
69 | inline bool check_segment_indices(Turn const& turn, | |
70 | signed_size_type last_index) | |
71 | { | |
72 | return | |
73 | (turn.operations[0].seg_id.segment_index == 0 | |
74 | && turn.operations[1].seg_id.segment_index == last_index) | |
75 | || | |
76 | (turn.operations[0].seg_id.segment_index == 0 | |
77 | && turn.operations[1].seg_id.segment_index == last_index); | |
78 | } | |
79 | ||
80 | ||
92f5a8d4 TL |
81 | template |
82 | < | |
83 | typename Geometry, | |
1e59de90 | 84 | typename Strategy, |
92f5a8d4 TL |
85 | typename Tag = typename tag<Geometry>::type |
86 | > | |
7c673cae FG |
87 | class is_acceptable_turn |
88 | : not_implemented<Geometry> | |
89 | {}; | |
90 | ||
1e59de90 TL |
91 | template <typename Linestring, typename Strategy> |
92 | class is_acceptable_turn<Linestring, Strategy, linestring_tag> | |
7c673cae FG |
93 | { |
94 | public: | |
1e59de90 | 95 | is_acceptable_turn(Linestring const& linestring, Strategy const& strategy) |
7c673cae | 96 | : m_linestring(linestring) |
1e59de90 TL |
97 | , m_is_closed(geometry::detail::equals::equals_point_point( |
98 | range::front(linestring), range::back(linestring), strategy)) | |
7c673cae FG |
99 | {} |
100 | ||
101 | template <typename Turn> | |
102 | inline bool apply(Turn const& turn) const | |
103 | { | |
104 | BOOST_GEOMETRY_ASSERT(boost::size(m_linestring) > 1); | |
105 | return m_is_closed | |
106 | && turn.method == overlay::method_none | |
107 | && check_segment_indices(turn, boost::size(m_linestring) - 2) | |
108 | && turn.operations[0].fraction.is_zero(); | |
109 | } | |
110 | ||
111 | private: | |
112 | Linestring const& m_linestring; | |
113 | bool const m_is_closed; | |
114 | }; | |
115 | ||
1e59de90 TL |
116 | template <typename MultiLinestring, typename Strategy> |
117 | class is_acceptable_turn<MultiLinestring, Strategy, multi_linestring_tag> | |
7c673cae FG |
118 | { |
119 | private: | |
7c673cae | 120 | template <typename Point, typename Linestring> |
1e59de90 | 121 | inline bool is_boundary_point_of(Point const& point, Linestring const& linestring) const |
7c673cae FG |
122 | { |
123 | BOOST_GEOMETRY_ASSERT(boost::size(linestring) > 1); | |
1e59de90 TL |
124 | using geometry::detail::equals::equals_point_point; |
125 | return ! equals_point_point(range::front(linestring), range::back(linestring), m_strategy) | |
126 | && (equals_point_point(point, range::front(linestring), m_strategy) | |
127 | || equals_point_point(point, range::back(linestring), m_strategy)); | |
7c673cae FG |
128 | } |
129 | ||
130 | template <typename Turn, typename Linestring> | |
1e59de90 | 131 | inline bool is_closing_point_of(Turn const& turn, Linestring const& linestring) const |
7c673cae FG |
132 | { |
133 | BOOST_GEOMETRY_ASSERT(boost::size(linestring) > 1); | |
1e59de90 TL |
134 | using geometry::detail::equals::equals_point_point; |
135 | return turn.method == overlay::method_none | |
136 | && check_segment_indices(turn, boost::size(linestring) - 2) | |
137 | && equals_point_point(range::front(linestring), range::back(linestring), m_strategy) | |
138 | && turn.operations[0].fraction.is_zero(); | |
7c673cae FG |
139 | } |
140 | ||
141 | template <typename Linestring1, typename Linestring2> | |
1e59de90 | 142 | inline bool have_same_boundary_points(Linestring1 const& ls1, Linestring2 const& ls2) const |
7c673cae | 143 | { |
1e59de90 TL |
144 | using geometry::detail::equals::equals_point_point; |
145 | return equals_point_point(range::front(ls1), range::front(ls2), m_strategy) | |
146 | ? equals_point_point(range::back(ls1), range::back(ls2), m_strategy) | |
147 | : (equals_point_point(range::front(ls1), range::back(ls2), m_strategy) | |
148 | && equals_point_point(range::back(ls1), range::front(ls2), m_strategy)); | |
7c673cae FG |
149 | } |
150 | ||
151 | public: | |
1e59de90 | 152 | is_acceptable_turn(MultiLinestring const& multilinestring, Strategy const& strategy) |
7c673cae | 153 | : m_multilinestring(multilinestring) |
1e59de90 | 154 | , m_strategy(strategy) |
7c673cae FG |
155 | {} |
156 | ||
157 | template <typename Turn> | |
158 | inline bool apply(Turn const& turn) const | |
159 | { | |
92f5a8d4 TL |
160 | typedef typename boost::range_value<MultiLinestring>::type linestring_type; |
161 | ||
7c673cae FG |
162 | linestring_type const& ls1 = |
163 | range::at(m_multilinestring, turn.operations[0].seg_id.multi_index); | |
164 | ||
165 | linestring_type const& ls2 = | |
166 | range::at(m_multilinestring, turn.operations[1].seg_id.multi_index); | |
167 | ||
168 | if (turn.operations[0].seg_id.multi_index | |
169 | == turn.operations[1].seg_id.multi_index) | |
170 | { | |
171 | return is_closing_point_of(turn, ls1); | |
172 | } | |
173 | ||
174 | return | |
175 | is_boundary_point_of(turn.point, ls1) | |
176 | && is_boundary_point_of(turn.point, ls2) | |
177 | && | |
178 | ( boost::size(ls1) != 2 | |
179 | || boost::size(ls2) != 2 | |
180 | || ! have_same_boundary_points(ls1, ls2) ); | |
181 | } | |
182 | ||
183 | private: | |
184 | MultiLinestring const& m_multilinestring; | |
1e59de90 | 185 | Strategy const& m_strategy; |
7c673cae FG |
186 | }; |
187 | ||
188 | ||
b32b8144 FG |
189 | template <typename Linear, typename Strategy> |
190 | inline bool has_self_intersections(Linear const& linear, Strategy const& strategy) | |
7c673cae FG |
191 | { |
192 | typedef typename point_type<Linear>::type point_type; | |
193 | ||
194 | // compute self turns | |
92f5a8d4 | 195 | typedef detail::overlay::turn_info<point_type> turn_info; |
7c673cae FG |
196 | |
197 | std::deque<turn_info> turns; | |
198 | ||
199 | typedef detail::overlay::get_turn_info | |
200 | < | |
201 | detail::disjoint::assign_disjoint_policy | |
202 | > turn_policy; | |
203 | ||
92f5a8d4 TL |
204 | typedef is_acceptable_turn |
205 | < | |
1e59de90 | 206 | Linear, Strategy |
92f5a8d4 TL |
207 | > is_acceptable_turn_type; |
208 | ||
1e59de90 | 209 | is_acceptable_turn_type predicate(linear, strategy); |
7c673cae FG |
210 | detail::overlay::predicate_based_interrupt_policy |
211 | < | |
92f5a8d4 | 212 | is_acceptable_turn_type |
7c673cae FG |
213 | > interrupt_policy(predicate); |
214 | ||
b32b8144 | 215 | // TODO: skip_adjacent should be set to false |
7c673cae FG |
216 | detail::self_get_turn_points::get_turns |
217 | < | |
b32b8144 | 218 | false, turn_policy |
7c673cae | 219 | >::apply(linear, |
b32b8144 | 220 | strategy, |
7c673cae FG |
221 | detail::no_rescale_policy(), |
222 | turns, | |
b32b8144 | 223 | interrupt_policy, 0, true); |
7c673cae FG |
224 | |
225 | detail::is_valid::debug_print_turns(turns.begin(), turns.end()); | |
226 | debug_print_boundary_points(linear); | |
227 | ||
228 | return interrupt_policy.has_intersections; | |
229 | } | |
230 | ||
231 | ||
232 | template <typename Linestring, bool CheckSelfIntersections = true> | |
233 | struct is_simple_linestring | |
234 | { | |
b32b8144 FG |
235 | template <typename Strategy> |
236 | static inline bool apply(Linestring const& linestring, | |
237 | Strategy const& strategy) | |
7c673cae FG |
238 | { |
239 | simplicity_failure_policy policy; | |
240 | return ! boost::empty(linestring) | |
1e59de90 TL |
241 | && ! detail::is_valid::has_duplicates<Linestring>::apply(linestring, policy, strategy) |
242 | && ! detail::is_valid::has_spikes<Linestring>::apply(linestring, policy, strategy); | |
b32b8144 FG |
243 | } |
244 | }; | |
245 | ||
246 | template <typename Linestring> | |
247 | struct is_simple_linestring<Linestring, true> | |
248 | { | |
249 | template <typename Strategy> | |
250 | static inline bool apply(Linestring const& linestring, | |
251 | Strategy const& strategy) | |
252 | { | |
1e59de90 | 253 | return is_simple_linestring<Linestring, false>::apply(linestring, strategy) |
b32b8144 | 254 | && ! has_self_intersections(linestring, strategy); |
7c673cae FG |
255 | } |
256 | }; | |
257 | ||
258 | ||
259 | template <typename MultiLinestring> | |
260 | struct is_simple_multilinestring | |
261 | { | |
b32b8144 FG |
262 | private: |
263 | template <typename Strategy> | |
1e59de90 | 264 | struct not_simple |
7c673cae | 265 | { |
1e59de90 | 266 | not_simple(Strategy const& strategy) |
b32b8144 FG |
267 | : m_strategy(strategy) |
268 | {} | |
269 | ||
270 | template <typename Linestring> | |
1e59de90 | 271 | inline bool operator()(Linestring const& linestring) const |
b32b8144 | 272 | { |
1e59de90 | 273 | return ! detail::is_simple::is_simple_linestring |
b32b8144 FG |
274 | < |
275 | Linestring, | |
276 | false // do not compute self-intersections | |
277 | >::apply(linestring, m_strategy); | |
278 | } | |
279 | ||
280 | Strategy const& m_strategy; | |
281 | }; | |
282 | ||
283 | public: | |
284 | template <typename Strategy> | |
285 | static inline bool apply(MultiLinestring const& multilinestring, | |
286 | Strategy const& strategy) | |
287 | { | |
7c673cae FG |
288 | // check each of the linestrings for simplicity |
289 | // but do not compute self-intersections yet; these will be | |
290 | // computed for the entire multilinestring | |
1e59de90 TL |
291 | // return true for empty multilinestring |
292 | ||
293 | using not_simple = not_simple<Strategy>; // do not compute self-intersections | |
294 | ||
295 | if (std::any_of(boost::begin(multilinestring), | |
296 | boost::end(multilinestring), | |
297 | not_simple(strategy))) | |
7c673cae FG |
298 | { |
299 | return false; | |
300 | } | |
301 | ||
b32b8144 | 302 | return ! has_self_intersections(multilinestring, strategy); |
7c673cae FG |
303 | } |
304 | }; | |
305 | ||
306 | ||
307 | ||
308 | }} // namespace detail::is_simple | |
309 | #endif // DOXYGEN_NO_DETAIL | |
310 | ||
311 | ||
312 | ||
313 | #ifndef DOXYGEN_NO_DISPATCH | |
314 | namespace dispatch | |
315 | { | |
316 | ||
317 | // A linestring is a curve. | |
318 | // A curve is simple if it does not pass through the same point twice, | |
319 | // with the possible exception of its two endpoints | |
320 | // | |
321 | // Reference: OGC 06-103r4 (6.1.6.1) | |
322 | template <typename Linestring> | |
323 | struct is_simple<Linestring, linestring_tag> | |
324 | : detail::is_simple::is_simple_linestring<Linestring> | |
325 | {}; | |
326 | ||
327 | ||
328 | // A MultiLinestring is a MultiCurve | |
329 | // A MultiCurve is simple if all of its elements are simple and the | |
330 | // only intersections between any two elements occur at Points that | |
331 | // are on the boundaries of both elements. | |
332 | // | |
333 | // Reference: OGC 06-103r4 (6.1.8.1; Fig. 9) | |
334 | template <typename MultiLinestring> | |
335 | struct is_simple<MultiLinestring, multi_linestring_tag> | |
336 | : detail::is_simple::is_simple_multilinestring<MultiLinestring> | |
337 | {}; | |
338 | ||
339 | ||
340 | } // namespace dispatch | |
341 | #endif // DOXYGEN_NO_DISPATCH | |
342 | ||
343 | ||
344 | }} // namespace boost::geometry | |
345 | ||
346 | ||
347 | #endif // BOOST_GEOMETRY_ALGORITHMS_DETAIL_IS_SIMPLE_LINEAR_HPP |