]>
Commit | Line | Data |
---|---|---|
b32b8144 FG |
1 | // Boost.Geometry (aka GGL, Generic Geometry Library) |
2 | ||
3 | // Copyright (c) 2007-2012 Barend Gehrels, Amsterdam, the Netherlands. | |
4 | // Copyright (c) 2017 Adam Wulkiewicz, Lodz, Poland. | |
5 | ||
92f5a8d4 TL |
6 | // This file was modified by Oracle on 2017, 2018. |
7 | // Modifications copyright (c) 2017-2018 Oracle and/or its affiliates. | |
b32b8144 FG |
8 | |
9 | // Contributed and/or modified by Adam Wulkiewicz, on behalf of Oracle | |
10 | ||
11 | // Use, modification and distribution is subject to the Boost Software License, | |
12 | // Version 1.0. (See accompanying file LICENSE_1_0.txt or copy at | |
13 | // http://www.boost.org/LICENSE_1_0.txt) | |
14 | ||
15 | #ifndef BOOST_GEOMETRY_ALGORITHMS_DETAIL_OVERLAY_SELF_TURN_POINTS_HPP | |
16 | #define BOOST_GEOMETRY_ALGORITHMS_DETAIL_OVERLAY_SELF_TURN_POINTS_HPP | |
17 | ||
18 | ||
19 | #include <cstddef> | |
20 | ||
21 | #include <boost/mpl/vector_c.hpp> | |
22 | #include <boost/range.hpp> | |
23 | ||
24 | #include <boost/geometry/core/access.hpp> | |
25 | #include <boost/geometry/core/coordinate_dimension.hpp> | |
26 | #include <boost/geometry/core/point_order.hpp> | |
27 | #include <boost/geometry/core/tags.hpp> | |
28 | ||
29 | #include <boost/geometry/geometries/concepts/check.hpp> | |
30 | ||
31 | #include <boost/geometry/algorithms/detail/disjoint/box_box.hpp> | |
32 | #include <boost/geometry/algorithms/detail/partition.hpp> | |
33 | #include <boost/geometry/algorithms/detail/overlay/do_reverse.hpp> | |
34 | #include <boost/geometry/algorithms/detail/overlay/get_turns.hpp> | |
35 | #include <boost/geometry/algorithms/detail/sections/section_box_policies.hpp> | |
36 | ||
37 | #include <boost/geometry/geometries/box.hpp> | |
38 | ||
39 | #include <boost/geometry/util/condition.hpp> | |
40 | ||
41 | ||
42 | namespace boost { namespace geometry | |
43 | { | |
44 | ||
45 | #ifndef DOXYGEN_NO_DETAIL | |
46 | namespace detail { namespace self_get_turn_points | |
47 | { | |
48 | ||
49 | struct no_interrupt_policy | |
50 | { | |
51 | static bool const enabled = false; | |
52 | static bool const has_intersections = false; | |
53 | ||
54 | ||
55 | template <typename Range> | |
56 | static inline bool apply(Range const&) | |
57 | { | |
58 | return false; | |
59 | } | |
60 | }; | |
61 | ||
62 | ||
63 | template | |
64 | < | |
65 | bool Reverse, | |
66 | typename Geometry, | |
67 | typename Turns, | |
68 | typename TurnPolicy, | |
69 | typename IntersectionStrategy, | |
70 | typename RobustPolicy, | |
71 | typename InterruptPolicy | |
72 | > | |
73 | struct self_section_visitor | |
74 | { | |
75 | Geometry const& m_geometry; | |
76 | IntersectionStrategy const& m_intersection_strategy; | |
77 | RobustPolicy const& m_rescale_policy; | |
78 | Turns& m_turns; | |
79 | InterruptPolicy& m_interrupt_policy; | |
11fdf7f2 | 80 | int m_source_index; |
b32b8144 FG |
81 | bool m_skip_adjacent; |
82 | ||
83 | inline self_section_visitor(Geometry const& g, | |
84 | IntersectionStrategy const& is, | |
85 | RobustPolicy const& rp, | |
86 | Turns& turns, | |
87 | InterruptPolicy& ip, | |
11fdf7f2 | 88 | int source_index, |
b32b8144 FG |
89 | bool skip_adjacent) |
90 | : m_geometry(g) | |
91 | , m_intersection_strategy(is) | |
92 | , m_rescale_policy(rp) | |
93 | , m_turns(turns) | |
94 | , m_interrupt_policy(ip) | |
95 | , m_source_index(source_index) | |
96 | , m_skip_adjacent(skip_adjacent) | |
97 | {} | |
98 | ||
99 | template <typename Section> | |
100 | inline bool apply(Section const& sec1, Section const& sec2) | |
101 | { | |
92f5a8d4 TL |
102 | if (! detail::disjoint::disjoint_box_box(sec1.bounding_box, |
103 | sec2.bounding_box, | |
104 | m_intersection_strategy.get_disjoint_box_box_strategy()) | |
b32b8144 FG |
105 | && ! sec1.duplicate |
106 | && ! sec2.duplicate) | |
107 | { | |
108 | // false if interrupted | |
109 | return detail::get_turns::get_turns_in_sections | |
110 | < | |
111 | Geometry, Geometry, | |
112 | Reverse, Reverse, | |
113 | Section, Section, | |
114 | TurnPolicy | |
115 | >::apply(m_source_index, m_geometry, sec1, | |
116 | m_source_index, m_geometry, sec2, | |
117 | false, m_skip_adjacent, | |
118 | m_intersection_strategy, | |
119 | m_rescale_policy, | |
120 | m_turns, m_interrupt_policy); | |
121 | } | |
122 | ||
123 | return true; | |
124 | } | |
125 | ||
126 | }; | |
127 | ||
128 | ||
129 | ||
130 | template <bool Reverse, typename TurnPolicy> | |
131 | struct get_turns | |
132 | { | |
133 | template <typename Geometry, typename IntersectionStrategy, typename RobustPolicy, typename Turns, typename InterruptPolicy> | |
134 | static inline bool apply( | |
135 | Geometry const& geometry, | |
136 | IntersectionStrategy const& intersection_strategy, | |
137 | RobustPolicy const& robust_policy, | |
138 | Turns& turns, | |
139 | InterruptPolicy& interrupt_policy, | |
11fdf7f2 | 140 | int source_index, bool skip_adjacent) |
b32b8144 FG |
141 | { |
142 | typedef model::box | |
143 | < | |
144 | typename geometry::robust_point_type | |
145 | < | |
146 | typename geometry::point_type<Geometry>::type, | |
147 | RobustPolicy | |
148 | >::type | |
149 | > box_type; | |
150 | ||
151 | // sectionalize in two dimensions to detect | |
152 | // all potential spikes correctly | |
153 | typedef geometry::sections<box_type, 2> sections_type; | |
154 | ||
155 | typedef boost::mpl::vector_c<std::size_t, 0, 1> dimensions; | |
156 | ||
157 | sections_type sec; | |
158 | geometry::sectionalize<Reverse, dimensions>(geometry, robust_policy, sec, | |
92f5a8d4 TL |
159 | intersection_strategy.get_envelope_strategy(), |
160 | intersection_strategy.get_expand_strategy()); | |
b32b8144 FG |
161 | |
162 | self_section_visitor | |
163 | < | |
164 | Reverse, Geometry, | |
165 | Turns, TurnPolicy, IntersectionStrategy, RobustPolicy, InterruptPolicy | |
166 | > visitor(geometry, intersection_strategy, robust_policy, turns, interrupt_policy, source_index, skip_adjacent); | |
167 | ||
92f5a8d4 TL |
168 | typedef detail::section::get_section_box |
169 | < | |
170 | typename IntersectionStrategy::expand_box_strategy_type | |
171 | > get_section_box_type; | |
172 | typedef detail::section::overlaps_section_box | |
173 | < | |
174 | typename IntersectionStrategy::disjoint_box_box_strategy_type | |
175 | > overlaps_section_box_type; | |
176 | ||
b32b8144 FG |
177 | // false if interrupted |
178 | geometry::partition | |
179 | < | |
180 | box_type | |
181 | >::apply(sec, visitor, | |
92f5a8d4 TL |
182 | get_section_box_type(), |
183 | overlaps_section_box_type()); | |
b32b8144 FG |
184 | |
185 | return ! interrupt_policy.has_intersections; | |
186 | } | |
187 | }; | |
188 | ||
189 | ||
190 | }} // namespace detail::self_get_turn_points | |
191 | #endif // DOXYGEN_NO_DETAIL | |
192 | ||
193 | ||
194 | #ifndef DOXYGEN_NO_DISPATCH | |
195 | namespace dispatch | |
196 | { | |
197 | ||
198 | template | |
199 | < | |
200 | bool Reverse, | |
201 | typename GeometryTag, | |
202 | typename Geometry, | |
203 | typename TurnPolicy | |
204 | > | |
205 | struct self_get_turn_points | |
206 | { | |
207 | }; | |
208 | ||
209 | ||
210 | template | |
211 | < | |
212 | bool Reverse, | |
213 | typename Ring, | |
214 | typename TurnPolicy | |
215 | > | |
216 | struct self_get_turn_points | |
217 | < | |
218 | Reverse, ring_tag, Ring, | |
219 | TurnPolicy | |
220 | > | |
221 | : detail::self_get_turn_points::get_turns<Reverse, TurnPolicy> | |
222 | {}; | |
223 | ||
224 | ||
225 | template | |
226 | < | |
227 | bool Reverse, | |
228 | typename Box, | |
229 | typename TurnPolicy | |
230 | > | |
231 | struct self_get_turn_points | |
232 | < | |
233 | Reverse, box_tag, Box, | |
234 | TurnPolicy | |
235 | > | |
236 | { | |
237 | template <typename Strategy, typename RobustPolicy, typename Turns, typename InterruptPolicy> | |
238 | static inline bool apply( | |
239 | Box const& , | |
240 | Strategy const& , | |
241 | RobustPolicy const& , | |
242 | Turns& , | |
243 | InterruptPolicy& , | |
11fdf7f2 | 244 | int /*source_index*/, |
b32b8144 FG |
245 | bool /*skip_adjacent*/) |
246 | { | |
247 | return true; | |
248 | } | |
249 | }; | |
250 | ||
251 | ||
252 | template | |
253 | < | |
254 | bool Reverse, | |
255 | typename Polygon, | |
256 | typename TurnPolicy | |
257 | > | |
258 | struct self_get_turn_points | |
259 | < | |
260 | Reverse, polygon_tag, Polygon, | |
261 | TurnPolicy | |
262 | > | |
263 | : detail::self_get_turn_points::get_turns<Reverse, TurnPolicy> | |
264 | {}; | |
265 | ||
266 | ||
267 | template | |
268 | < | |
269 | bool Reverse, | |
270 | typename MultiPolygon, | |
271 | typename TurnPolicy | |
272 | > | |
273 | struct self_get_turn_points | |
274 | < | |
275 | Reverse, multi_polygon_tag, MultiPolygon, | |
276 | TurnPolicy | |
277 | > | |
278 | : detail::self_get_turn_points::get_turns<Reverse, TurnPolicy> | |
279 | {}; | |
280 | ||
281 | ||
282 | } // namespace dispatch | |
283 | #endif // DOXYGEN_NO_DISPATCH | |
284 | ||
285 | ||
286 | #ifndef DOXYGEN_NO_DETAIL | |
287 | namespace detail { namespace self_get_turn_points | |
288 | { | |
289 | ||
290 | // Version where Reverse can be specified manually. TODO: | |
291 | // can most probably be merged with self_get_turn_points::get_turn | |
292 | template | |
293 | < | |
294 | bool Reverse, | |
295 | typename AssignPolicy, | |
296 | typename Geometry, | |
297 | typename IntersectionStrategy, | |
298 | typename RobustPolicy, | |
299 | typename Turns, | |
300 | typename InterruptPolicy | |
301 | > | |
302 | inline void self_turns(Geometry const& geometry, | |
303 | IntersectionStrategy const& strategy, | |
304 | RobustPolicy const& robust_policy, | |
305 | Turns& turns, | |
306 | InterruptPolicy& interrupt_policy, | |
11fdf7f2 | 307 | int source_index = 0, |
b32b8144 FG |
308 | bool skip_adjacent = false) |
309 | { | |
310 | concepts::check<Geometry const>(); | |
311 | ||
312 | typedef detail::overlay::get_turn_info<detail::overlay::assign_null_policy> turn_policy; | |
313 | ||
314 | dispatch::self_get_turn_points | |
315 | < | |
316 | Reverse, | |
317 | typename tag<Geometry>::type, | |
318 | Geometry, | |
319 | turn_policy | |
320 | >::apply(geometry, strategy, robust_policy, turns, interrupt_policy, | |
321 | source_index, skip_adjacent); | |
322 | } | |
323 | ||
324 | }} // namespace detail::self_get_turn_points | |
325 | #endif // DOXYGEN_NO_DETAIL | |
326 | ||
327 | /*! | |
328 | \brief Calculate self intersections of a geometry | |
329 | \ingroup overlay | |
330 | \tparam Geometry geometry type | |
331 | \tparam Turns type of intersection container | |
332 | (e.g. vector of "intersection/turn point"'s) | |
333 | \param geometry geometry | |
334 | \param strategy strategy to be used | |
335 | \param robust_policy policy to handle robustness issues | |
336 | \param turns container which will contain intersection points | |
337 | \param interrupt_policy policy determining if process is stopped | |
338 | when intersection is found | |
92f5a8d4 TL |
339 | \param source_index source index for generated turns |
340 | \param skip_adjacent indicates if adjacent turns should be skipped | |
b32b8144 FG |
341 | */ |
342 | template | |
343 | < | |
344 | typename AssignPolicy, | |
345 | typename Geometry, | |
346 | typename IntersectionStrategy, | |
347 | typename RobustPolicy, | |
348 | typename Turns, | |
349 | typename InterruptPolicy | |
350 | > | |
351 | inline void self_turns(Geometry const& geometry, | |
352 | IntersectionStrategy const& strategy, | |
353 | RobustPolicy const& robust_policy, | |
354 | Turns& turns, | |
355 | InterruptPolicy& interrupt_policy, | |
11fdf7f2 | 356 | int source_index = 0, |
b32b8144 FG |
357 | bool skip_adjacent = false) |
358 | { | |
359 | concepts::check<Geometry const>(); | |
360 | ||
361 | static bool const reverse = detail::overlay::do_reverse | |
362 | < | |
363 | geometry::point_order<Geometry>::value | |
364 | >::value; | |
365 | ||
366 | detail::self_get_turn_points::self_turns | |
367 | < | |
368 | reverse, | |
369 | AssignPolicy | |
370 | >(geometry, strategy, robust_policy, turns, interrupt_policy, | |
371 | source_index, skip_adjacent); | |
372 | } | |
373 | ||
374 | ||
375 | ||
376 | }} // namespace boost::geometry | |
377 | ||
378 | #endif // BOOST_GEOMETRY_ALGORITHMS_DETAIL_OVERLAY_SELF_TURN_POINTS_HPP |