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