1 // Boost.Geometry (aka GGL, Generic Geometry Library)
2 
3 // Copyright (c) 2007-2012 Barend Gehrels, Amsterdam, the Netherlands.
4 
5 // Use, modification and distribution is subject to the Boost Software License,
6 // Version 1.0. (See accompanying file LICENSE_1_0.txt or copy at
7 // http://www.boost.org/LICENSE_1_0.txt)
8 
9 #ifndef BOOST_GEOMETRY_ALGORITHMS_DETAIL_OVERLAY_SELF_TURN_POINTS_HPP
10 #define BOOST_GEOMETRY_ALGORITHMS_DETAIL_OVERLAY_SELF_TURN_POINTS_HPP
11 
12 
13 #include <cstddef>
14 
15 #include <boost/mpl/vector_c.hpp>
16 #include <boost/range.hpp>
17 
18 #include <boost/geometry/core/access.hpp>
19 #include <boost/geometry/core/coordinate_dimension.hpp>
20 #include <boost/geometry/core/tags.hpp>
21 
22 #include <boost/geometry/geometries/concepts/check.hpp>
23 
24 #include <boost/geometry/algorithms/detail/disjoint/box_box.hpp>
25 #include <boost/geometry/algorithms/detail/partition.hpp>
26 #include <boost/geometry/algorithms/detail/overlay/get_turns.hpp>
27 #include <boost/geometry/algorithms/detail/sections/section_box_policies.hpp>
28 
29 #include <boost/geometry/geometries/box.hpp>
30 
31 #include <boost/geometry/util/condition.hpp>
32 
33 
34 namespace boost { namespace geometry
35 {
36 
37 #ifndef DOXYGEN_NO_DETAIL
38 namespace detail { namespace self_get_turn_points
39 {
40 
41 struct no_interrupt_policy
42 {
43     static bool const enabled = false;
44     static bool const has_intersections = false;
45 
46 
47     template <typename Range>
applyboost::geometry::detail::self_get_turn_points::no_interrupt_policy48     static inline bool apply(Range const&)
49     {
50         return false;
51     }
52 };
53 
54 
55 
56 
57 class self_ip_exception : public geometry::exception {};
58 
59 template
60 <
61     typename Geometry,
62     typename Turns,
63     typename TurnPolicy,
64     typename RobustPolicy,
65     typename InterruptPolicy
66 >
67 struct self_section_visitor
68 {
69     Geometry const& m_geometry;
70     RobustPolicy const& m_rescale_policy;
71     Turns& m_turns;
72     InterruptPolicy& m_interrupt_policy;
73 
self_section_visitorboost::geometry::detail::self_get_turn_points::self_section_visitor74     inline self_section_visitor(Geometry const& g,
75             RobustPolicy const& rp,
76             Turns& turns, InterruptPolicy& ip)
77         : m_geometry(g)
78         , m_rescale_policy(rp)
79         , m_turns(turns)
80         , m_interrupt_policy(ip)
81     {}
82 
83     template <typename Section>
applyboost::geometry::detail::self_get_turn_points::self_section_visitor84     inline bool apply(Section const& sec1, Section const& sec2)
85     {
86         if (! detail::disjoint::disjoint_box_box(sec1.bounding_box, sec2.bounding_box)
87                 && ! sec1.duplicate
88                 && ! sec2.duplicate)
89         {
90             detail::get_turns::get_turns_in_sections
91                     <
92                         Geometry, Geometry,
93                         false, false,
94                         Section, Section,
95                         TurnPolicy
96                     >::apply(
97                             0, m_geometry, sec1,
98                             0, m_geometry, sec2,
99                             false,
100                             m_rescale_policy,
101                             m_turns, m_interrupt_policy);
102         }
103         if (BOOST_GEOMETRY_CONDITION(m_interrupt_policy.has_intersections))
104         {
105             // TODO: we should give partition an interrupt policy.
106             // Now we throw, and catch below, to stop the partition loop.
107             throw self_ip_exception();
108         }
109         return true;
110     }
111 
112 };
113 
114 
115 
116 template<typename TurnPolicy>
117 struct get_turns
118 {
119     template <typename Geometry, typename RobustPolicy, typename Turns, typename InterruptPolicy>
applyboost::geometry::detail::self_get_turn_points::get_turns120     static inline bool apply(
121             Geometry const& geometry,
122             RobustPolicy const& robust_policy,
123             Turns& turns,
124             InterruptPolicy& interrupt_policy)
125     {
126         typedef model::box
127             <
128                 typename geometry::robust_point_type
129                 <
130                     typename geometry::point_type<Geometry>::type,
131                     RobustPolicy
132                 >::type
133             > box_type;
134 
135         typedef geometry::sections<box_type, 1> sections_type;
136 
137         typedef boost::mpl::vector_c<std::size_t, 0> dimensions;
138 
139         sections_type sec;
140         geometry::sectionalize<false, dimensions>(geometry, robust_policy, sec);
141 
142         self_section_visitor
143             <
144                 Geometry,
145                 Turns, TurnPolicy, RobustPolicy, InterruptPolicy
146             > visitor(geometry, robust_policy, turns, interrupt_policy);
147 
148         try
149         {
150             geometry::partition
151                 <
152                     box_type,
153                     detail::section::get_section_box,
154                     detail::section::overlaps_section_box
155                 >::apply(sec, visitor);
156         }
157         catch(self_ip_exception const& )
158         {
159             return false;
160         }
161 
162         return true;
163     }
164 };
165 
166 
167 }} // namespace detail::self_get_turn_points
168 #endif // DOXYGEN_NO_DETAIL
169 
170 
171 #ifndef DOXYGEN_NO_DISPATCH
172 namespace dispatch
173 {
174 
175 template
176 <
177     typename GeometryTag,
178     typename Geometry,
179     typename TurnPolicy
180 >
181 struct self_get_turn_points
182 {
183 };
184 
185 
186 template
187 <
188     typename Ring,
189     typename TurnPolicy
190 >
191 struct self_get_turn_points
192     <
193         ring_tag, Ring,
194         TurnPolicy
195     >
196     : detail::self_get_turn_points::get_turns<TurnPolicy>
197 {};
198 
199 
200 template
201 <
202     typename Box,
203     typename TurnPolicy
204 >
205 struct self_get_turn_points
206     <
207         box_tag, Box,
208         TurnPolicy
209     >
210 {
211     template <typename RobustPolicy, typename Turns, typename InterruptPolicy>
applyboost::geometry::dispatch::self_get_turn_points212     static inline bool apply(
213             Box const& ,
214             RobustPolicy const& ,
215             Turns& ,
216             InterruptPolicy& )
217     {
218         return true;
219     }
220 };
221 
222 
223 template
224 <
225     typename Polygon,
226     typename TurnPolicy
227 >
228 struct self_get_turn_points
229     <
230         polygon_tag, Polygon,
231         TurnPolicy
232     >
233     : detail::self_get_turn_points::get_turns<TurnPolicy>
234 {};
235 
236 
237 template
238 <
239     typename MultiPolygon,
240     typename TurnPolicy
241 >
242 struct self_get_turn_points
243     <
244         multi_polygon_tag, MultiPolygon,
245         TurnPolicy
246     >
247     : detail::self_get_turn_points::get_turns<TurnPolicy>
248 {};
249 
250 
251 } // namespace dispatch
252 #endif // DOXYGEN_NO_DISPATCH
253 
254 
255 /*!
256     \brief Calculate self intersections of a geometry
257     \ingroup overlay
258     \tparam Geometry geometry type
259     \tparam Turns type of intersection container
260                 (e.g. vector of "intersection/turn point"'s)
261     \param geometry geometry
262     \param robust_policy policy to handle robustness issues
263     \param turns container which will contain intersection points
264     \param interrupt_policy policy determining if process is stopped
265         when intersection is found
266  */
267 template
268 <
269     typename AssignPolicy,
270     typename Geometry,
271     typename RobustPolicy,
272     typename Turns,
273     typename InterruptPolicy
274 >
self_turns(Geometry const & geometry,RobustPolicy const & robust_policy,Turns & turns,InterruptPolicy & interrupt_policy)275 inline void self_turns(Geometry const& geometry,
276             RobustPolicy const& robust_policy,
277             Turns& turns, InterruptPolicy& interrupt_policy)
278 {
279     concept::check<Geometry const>();
280 
281     typedef detail::overlay::get_turn_info<detail::overlay::assign_null_policy> turn_policy;
282 
283     dispatch::self_get_turn_points
284             <
285                 typename tag<Geometry>::type,
286                 Geometry,
287                 turn_policy
288             >::apply(geometry, robust_policy, turns, interrupt_policy);
289 }
290 
291 
292 
293 }} // namespace boost::geometry
294 
295 #endif // BOOST_GEOMETRY_ALGORITHMS_DETAIL_OVERLAY_SELF_TURN_POINTS_HPP
296