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.
7 // Modifications copyright (c) 2017 Oracle and/or its affiliates.
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>
applyboost::geometry::detail::self_get_turn_points::no_interrupt_policy56     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;
80     std::size_t m_source_index;
81 
self_section_visitorboost::geometry::detail::self_get_turn_points::self_section_visitor82     inline self_section_visitor(Geometry const& g,
83                                 IntersectionStrategy const& is,
84                                 RobustPolicy const& rp,
85                                 Turns& turns,
86                                 InterruptPolicy& ip,
87                                 std::size_t source_index)
88         : m_geometry(g)
89         , m_intersection_strategy(is)
90         , m_rescale_policy(rp)
91         , m_turns(turns)
92         , m_interrupt_policy(ip)
93         , m_source_index(source_index)
94     {}
95 
96     template <typename Section>
applyboost::geometry::detail::self_get_turn_points::self_section_visitor97     inline bool apply(Section const& sec1, Section const& sec2)
98     {
99         if (! detail::disjoint::disjoint_box_box(sec1.bounding_box, sec2.bounding_box)
100                 && ! sec1.duplicate
101                 && ! sec2.duplicate)
102         {
103             // false if interrupted
104             return detail::get_turns::get_turns_in_sections
105                     <
106                         Geometry, Geometry,
107                         Reverse, Reverse,
108                         Section, Section,
109                         TurnPolicy
110                     >::apply(m_source_index, m_geometry, sec1,
111                              m_source_index, m_geometry, sec2,
112                              false,
113                              m_intersection_strategy,
114                              m_rescale_policy,
115                              m_turns, m_interrupt_policy);
116         }
117 
118         return true;
119     }
120 
121 };
122 
123 
124 
125 template <bool Reverse, typename TurnPolicy>
126 struct get_turns
127 {
128     template <typename Geometry, typename IntersectionStrategy, typename RobustPolicy, typename Turns, typename InterruptPolicy>
applyboost::geometry::detail::self_get_turn_points::get_turns129     static inline bool apply(
130             Geometry const& geometry,
131             IntersectionStrategy const& intersection_strategy,
132             RobustPolicy const& robust_policy,
133             Turns& turns,
134             InterruptPolicy& interrupt_policy,
135             std::size_t source_index)
136     {
137         typedef model::box
138             <
139                 typename geometry::robust_point_type
140                 <
141                     typename geometry::point_type<Geometry>::type,
142                     RobustPolicy
143                 >::type
144             > box_type;
145 
146         typedef geometry::sections<box_type, 1> sections_type;
147 
148         typedef boost::mpl::vector_c<std::size_t, 0> dimensions;
149 
150         sections_type sec;
151         geometry::sectionalize<Reverse, dimensions>(geometry, robust_policy, sec,
152                                                   intersection_strategy.get_envelope_strategy());
153 
154         self_section_visitor
155             <
156                 Reverse, Geometry,
157                 Turns, TurnPolicy, IntersectionStrategy, RobustPolicy, InterruptPolicy
158             > visitor(geometry, intersection_strategy, robust_policy, turns, interrupt_policy, source_index);
159 
160         // false if interrupted
161         geometry::partition
162             <
163                 box_type
164             >::apply(sec, visitor,
165                      detail::section::get_section_box(),
166                      detail::section::overlaps_section_box());
167 
168         return ! interrupt_policy.has_intersections;
169     }
170 };
171 
172 
173 }} // namespace detail::self_get_turn_points
174 #endif // DOXYGEN_NO_DETAIL
175 
176 
177 #ifndef DOXYGEN_NO_DISPATCH
178 namespace dispatch
179 {
180 
181 template
182 <
183     bool Reverse,
184     typename GeometryTag,
185     typename Geometry,
186     typename TurnPolicy
187 >
188 struct self_get_turn_points
189 {
190 };
191 
192 
193 template
194 <
195     bool Reverse,
196     typename Ring,
197     typename TurnPolicy
198 >
199 struct self_get_turn_points
200     <
201         Reverse, ring_tag, Ring,
202         TurnPolicy
203     >
204     : detail::self_get_turn_points::get_turns<Reverse, TurnPolicy>
205 {};
206 
207 
208 template
209 <
210     bool Reverse,
211     typename Box,
212     typename TurnPolicy
213 >
214 struct self_get_turn_points
215     <
216         Reverse, box_tag, Box,
217         TurnPolicy
218     >
219 {
220     template <typename Strategy, typename RobustPolicy, typename Turns, typename InterruptPolicy>
applyboost::geometry::dispatch::self_get_turn_points221     static inline bool apply(
222             Box const& ,
223             Strategy const& ,
224             RobustPolicy const& ,
225             Turns& ,
226             InterruptPolicy& ,
227             std::size_t)
228     {
229         return true;
230     }
231 };
232 
233 
234 template
235 <
236     bool Reverse,
237     typename Polygon,
238     typename TurnPolicy
239 >
240 struct self_get_turn_points
241     <
242         Reverse, polygon_tag, Polygon,
243         TurnPolicy
244     >
245     : detail::self_get_turn_points::get_turns<Reverse, TurnPolicy>
246 {};
247 
248 
249 template
250 <
251     bool Reverse,
252     typename MultiPolygon,
253     typename TurnPolicy
254 >
255 struct self_get_turn_points
256     <
257         Reverse, multi_polygon_tag, MultiPolygon,
258         TurnPolicy
259     >
260     : detail::self_get_turn_points::get_turns<Reverse, TurnPolicy>
261 {};
262 
263 
264 } // namespace dispatch
265 #endif // DOXYGEN_NO_DISPATCH
266 
267 
268 #ifndef DOXYGEN_NO_DETAIL
269 namespace detail { namespace self_get_turn_points
270 {
271 
272 // Version where Reverse can be specified manually. TODO:
273 // can most probably be merged with self_get_turn_points::get_turn
274 template
275 <
276     bool Reverse,
277     typename AssignPolicy,
278     typename Geometry,
279     typename IntersectionStrategy,
280     typename RobustPolicy,
281     typename Turns,
282     typename InterruptPolicy
283 >
self_turns(Geometry const & geometry,IntersectionStrategy const & strategy,RobustPolicy const & robust_policy,Turns & turns,InterruptPolicy & interrupt_policy,std::size_t source_index=0)284 inline void self_turns(Geometry const& geometry,
285                        IntersectionStrategy const& strategy,
286                        RobustPolicy const& robust_policy,
287                        Turns& turns,
288                        InterruptPolicy& interrupt_policy,
289                        std::size_t source_index = 0)
290 {
291     concepts::check<Geometry const>();
292 
293     typedef detail::overlay::get_turn_info<detail::overlay::assign_null_policy> turn_policy;
294 
295     dispatch::self_get_turn_points
296             <
297                 Reverse,
298                 typename tag<Geometry>::type,
299                 Geometry,
300                 turn_policy
301             >::apply(geometry, strategy, robust_policy, turns, interrupt_policy, source_index);
302 }
303 
304 }} // namespace detail::self_get_turn_points
305 #endif // DOXYGEN_NO_DETAIL
306 
307 /*!
308     \brief Calculate self intersections of a geometry
309     \ingroup overlay
310     \tparam Geometry geometry type
311     \tparam Turns type of intersection container
312                 (e.g. vector of "intersection/turn point"'s)
313     \param geometry geometry
314     \param strategy strategy to be used
315     \param robust_policy policy to handle robustness issues
316     \param turns container which will contain intersection points
317     \param interrupt_policy policy determining if process is stopped
318         when intersection is found
319  */
320 template
321 <
322     typename AssignPolicy,
323     typename Geometry,
324     typename IntersectionStrategy,
325     typename RobustPolicy,
326     typename Turns,
327     typename InterruptPolicy
328 >
self_turns(Geometry const & geometry,IntersectionStrategy const & strategy,RobustPolicy const & robust_policy,Turns & turns,InterruptPolicy & interrupt_policy,std::size_t source_index=0)329 inline void self_turns(Geometry const& geometry,
330                        IntersectionStrategy const& strategy,
331                        RobustPolicy const& robust_policy,
332                        Turns& turns,
333                        InterruptPolicy& interrupt_policy,
334                        std::size_t source_index = 0)
335 {
336     concepts::check<Geometry const>();
337 
338     static bool const reverse =  detail::overlay::do_reverse
339         <
340             geometry::point_order<Geometry>::value
341         >::value;
342 
343     detail::self_get_turn_points::self_turns
344             <
345                 reverse,
346                 AssignPolicy
347             >(geometry, strategy, robust_policy, turns, interrupt_policy, source_index);
348 }
349 
350 
351 
352 }} // namespace boost::geometry
353 
354 #endif // BOOST_GEOMETRY_ALGORITHMS_DETAIL_OVERLAY_SELF_TURN_POINTS_HPP
355