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