1 // Boost.Geometry (aka GGL, Generic Geometry Library)
3 // Copyright (c) 2007-2015 Barend Gehrels, Amsterdam, the Netherlands.
5 // This file was modified by Oracle on 2014.
6 // Modifications copyright (c) 2014-2015, Oracle and/or its affiliates.
8 // Contributed and/or modified by Adam Wulkiewicz, on behalf of Oracle
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)
14 #ifndef BOOST_GEOMETRY_ALGORITHMS_DETAIL_INTERSECTION_MULTI_HPP
15 #define BOOST_GEOMETRY_ALGORITHMS_DETAIL_INTERSECTION_MULTI_HPP
17 #include <boost/geometry/core/closure.hpp>
18 #include <boost/geometry/core/geometry_id.hpp>
19 #include <boost/geometry/core/is_areal.hpp>
20 #include <boost/geometry/core/point_order.hpp>
21 #include <boost/geometry/core/tags.hpp>
22 #include <boost/geometry/geometries/concepts/check.hpp>
24 // TODO: those headers probably may be removed
25 #include <boost/geometry/algorithms/detail/overlay/get_ring.hpp>
26 #include <boost/geometry/algorithms/detail/overlay/get_turns.hpp>
27 #include <boost/geometry/algorithms/detail/overlay/copy_segments.hpp>
28 #include <boost/geometry/algorithms/detail/overlay/copy_segment_point.hpp>
29 #include <boost/geometry/algorithms/detail/overlay/select_rings.hpp>
30 #include <boost/geometry/algorithms/detail/sections/range_by_section.hpp>
31 #include <boost/geometry/algorithms/detail/sections/sectionalize.hpp>
33 #include <boost/geometry/algorithms/detail/intersection/interface.hpp>
35 #include <boost/geometry/algorithms/covered_by.hpp>
36 #include <boost/geometry/algorithms/envelope.hpp>
37 #include <boost/geometry/algorithms/num_points.hpp>
40 namespace boost { namespace geometry
43 #ifndef DOXYGEN_NO_DETAIL
44 namespace detail { namespace intersection
48 template <typename PointOut>
49 struct intersection_multi_linestring_multi_linestring_point
53 typename MultiLinestring1, typename MultiLinestring2,
54 typename RobustPolicy,
55 typename OutputIterator, typename Strategy
57 static inline OutputIterator apply(MultiLinestring1 const& ml1,
58 MultiLinestring2 const& ml2,
59 RobustPolicy const& robust_policy,
61 Strategy const& strategy)
63 // Note, this loop is quadratic w.r.t. number of linestrings per input.
64 // Future Enhancement: first do the sections of each, then intersect.
65 for (typename boost::range_iterator
67 MultiLinestring1 const
68 >::type it1 = boost::begin(ml1);
69 it1 != boost::end(ml1);
72 for (typename boost::range_iterator
74 MultiLinestring2 const
75 >::type it2 = boost::begin(ml2);
76 it2 != boost::end(ml2);
79 out = intersection_linestring_linestring_point<PointOut>
80 ::apply(*it1, *it2, robust_policy, out, strategy);
89 template <typename PointOut>
90 struct intersection_linestring_multi_linestring_point
94 typename Linestring, typename MultiLinestring,
95 typename RobustPolicy,
96 typename OutputIterator, typename Strategy
98 static inline OutputIterator apply(Linestring const& linestring,
99 MultiLinestring const& ml,
100 RobustPolicy const& robust_policy,
102 Strategy const& strategy)
104 for (typename boost::range_iterator
106 MultiLinestring const
107 >::type it = boost::begin(ml);
108 it != boost::end(ml);
111 out = intersection_linestring_linestring_point<PointOut>
112 ::apply(linestring, *it, robust_policy, out, strategy);
120 // This loop is quite similar to the loop above, but beacuse the iterator
121 // is second (above) or first (below) argument, it is not trivial to merge them.
125 typename LineStringOut,
126 overlay_type OverlayType
128 struct intersection_of_multi_linestring_with_areal
132 typename MultiLinestring, typename Areal,
133 typename RobustPolicy,
134 typename OutputIterator, typename Strategy
136 static inline OutputIterator apply(MultiLinestring const& ml, Areal const& areal,
137 RobustPolicy const& robust_policy,
139 Strategy const& strategy)
141 for (typename boost::range_iterator
143 MultiLinestring const
144 >::type it = boost::begin(ml);
145 it != boost::end(ml);
148 out = intersection_of_linestring_with_areal
150 ReverseAreal, LineStringOut, OverlayType
151 >::apply(*it, areal, robust_policy, out, strategy);
159 // This one calls the one above with reversed arguments
163 typename LineStringOut,
164 overlay_type OverlayType
166 struct intersection_of_areal_with_multi_linestring
170 typename Areal, typename MultiLinestring,
171 typename RobustPolicy,
172 typename OutputIterator, typename Strategy
174 static inline OutputIterator apply(Areal const& areal, MultiLinestring const& ml,
175 RobustPolicy const& robust_policy,
177 Strategy const& strategy)
179 return intersection_of_multi_linestring_with_areal
181 ReverseAreal, LineStringOut, OverlayType
182 >::apply(ml, areal, robust_policy, out, strategy);
188 template <typename LinestringOut>
189 struct clip_multi_linestring
193 typename MultiLinestring, typename Box,
194 typename RobustPolicy,
195 typename OutputIterator, typename Strategy
197 static inline OutputIterator apply(MultiLinestring const& multi_linestring,
199 RobustPolicy const& robust_policy,
200 OutputIterator out, Strategy const& )
202 typedef typename point_type<LinestringOut>::type point_type;
203 strategy::intersection::liang_barsky<Box, point_type> lb_strategy;
204 for (typename boost::range_iterator<MultiLinestring const>::type it
205 = boost::begin(multi_linestring);
206 it != boost::end(multi_linestring); ++it)
208 out = detail::intersection::clip_range_with_box
209 <LinestringOut>(box, *it, robust_policy, out, lb_strategy);
216 }} // namespace detail::intersection
217 #endif // DOXYGEN_NO_DETAIL
220 #ifndef DOXYGEN_NO_DISPATCH
228 typename MultiLinestring1, typename MultiLinestring2,
229 typename GeometryOut,
230 overlay_type OverlayType,
231 bool Reverse1, bool Reverse2, bool ReverseOut
233 struct intersection_insert
235 MultiLinestring1, MultiLinestring2,
238 Reverse1, Reverse2, ReverseOut,
239 multi_linestring_tag, multi_linestring_tag, point_tag,
241 > : detail::intersection::intersection_multi_linestring_multi_linestring_point
250 typename Linestring, typename MultiLinestring,
251 typename GeometryOut,
252 overlay_type OverlayType,
253 bool Reverse1, bool Reverse2, bool ReverseOut
255 struct intersection_insert
257 Linestring, MultiLinestring,
260 Reverse1, Reverse2, ReverseOut,
261 linestring_tag, multi_linestring_tag, point_tag,
263 > : detail::intersection::intersection_linestring_multi_linestring_point
272 typename MultiLinestring, typename Box,
273 typename GeometryOut,
274 overlay_type OverlayType,
275 bool Reverse1, bool Reverse2, bool ReverseOut
277 struct intersection_insert
279 MultiLinestring, Box,
282 Reverse1, Reverse2, ReverseOut,
283 multi_linestring_tag, box_tag, linestring_tag,
285 > : detail::intersection::clip_multi_linestring
294 typename Linestring, typename MultiPolygon,
295 typename GeometryOut,
296 overlay_type OverlayType,
297 bool ReverseLinestring, bool ReverseMultiPolygon, bool ReverseOut
299 struct intersection_insert
301 Linestring, MultiPolygon,
304 ReverseLinestring, ReverseMultiPolygon, ReverseOut,
305 linestring_tag, multi_polygon_tag, linestring_tag,
307 > : detail::intersection::intersection_of_linestring_with_areal
316 // Derives from areal/mls because runtime arguments are in that order.
317 // areal/mls reverses it itself to mls/areal
320 typename Polygon, typename MultiLinestring,
321 typename GeometryOut,
322 overlay_type OverlayType,
323 bool ReversePolygon, bool ReverseMultiLinestring, bool ReverseOut
325 struct intersection_insert
327 Polygon, MultiLinestring,
330 ReversePolygon, ReverseMultiLinestring, ReverseOut,
331 polygon_tag, multi_linestring_tag, linestring_tag,
333 > : detail::intersection::intersection_of_areal_with_multi_linestring
344 typename MultiLinestring, typename Ring,
345 typename GeometryOut,
346 overlay_type OverlayType,
347 bool ReverseMultiLinestring, bool ReverseRing, bool ReverseOut
349 struct intersection_insert
351 MultiLinestring, Ring,
354 ReverseMultiLinestring, ReverseRing, ReverseOut,
355 multi_linestring_tag, ring_tag, linestring_tag,
357 > : detail::intersection::intersection_of_multi_linestring_with_areal
367 typename MultiLinestring, typename Polygon,
368 typename GeometryOut,
369 overlay_type OverlayType,
370 bool ReverseMultiLinestring, bool ReverseRing, bool ReverseOut
372 struct intersection_insert
374 MultiLinestring, Polygon,
377 ReverseMultiLinestring, ReverseRing, ReverseOut,
378 multi_linestring_tag, polygon_tag, linestring_tag,
380 > : detail::intersection::intersection_of_multi_linestring_with_areal
392 typename MultiLinestring, typename MultiPolygon,
393 typename GeometryOut,
394 overlay_type OverlayType,
395 bool ReverseMultiLinestring, bool ReverseMultiPolygon, bool ReverseOut
397 struct intersection_insert
399 MultiLinestring, MultiPolygon,
402 ReverseMultiLinestring, ReverseMultiPolygon, ReverseOut,
403 multi_linestring_tag, multi_polygon_tag, linestring_tag,
405 > : detail::intersection::intersection_of_multi_linestring_with_areal
414 } // namespace dispatch
417 }} // namespace boost::geometry
420 #endif // BOOST_GEOMETRY_ALGORITHMS_DETAIL_INTERSECTION_MULTI_HPP