]>
Commit | Line | Data |
---|---|---|
7c673cae FG |
1 | // Boost.Geometry (aka GGL, Generic Geometry Library) |
2 | ||
3 | // Copyright (c) 2007-2015 Barend Gehrels, Amsterdam, the Netherlands. | |
4 | ||
5 | // This file was modified by Oracle on 2014. | |
6 | // Modifications copyright (c) 2014-2015, Oracle and/or its affiliates. | |
7 | ||
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_INTERSECTION_MULTI_HPP | |
15 | #define BOOST_GEOMETRY_ALGORITHMS_DETAIL_INTERSECTION_MULTI_HPP | |
16 | ||
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> | |
23 | ||
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> | |
32 | ||
33 | #include <boost/geometry/algorithms/detail/intersection/interface.hpp> | |
34 | ||
35 | #include <boost/geometry/algorithms/covered_by.hpp> | |
36 | #include <boost/geometry/algorithms/envelope.hpp> | |
37 | #include <boost/geometry/algorithms/num_points.hpp> | |
38 | ||
39 | ||
40 | namespace boost { namespace geometry | |
41 | { | |
42 | ||
43 | #ifndef DOXYGEN_NO_DETAIL | |
44 | namespace detail { namespace intersection | |
45 | { | |
46 | ||
47 | ||
48 | template <typename PointOut> | |
49 | struct intersection_multi_linestring_multi_linestring_point | |
50 | { | |
51 | template | |
52 | < | |
53 | typename MultiLinestring1, typename MultiLinestring2, | |
54 | typename RobustPolicy, | |
55 | typename OutputIterator, typename Strategy | |
56 | > | |
57 | static inline OutputIterator apply(MultiLinestring1 const& ml1, | |
58 | MultiLinestring2 const& ml2, | |
59 | RobustPolicy const& robust_policy, | |
60 | OutputIterator out, | |
61 | Strategy const& strategy) | |
62 | { | |
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 | |
66 | < | |
67 | MultiLinestring1 const | |
68 | >::type it1 = boost::begin(ml1); | |
69 | it1 != boost::end(ml1); | |
70 | ++it1) | |
71 | { | |
72 | for (typename boost::range_iterator | |
73 | < | |
74 | MultiLinestring2 const | |
75 | >::type it2 = boost::begin(ml2); | |
76 | it2 != boost::end(ml2); | |
77 | ++it2) | |
78 | { | |
79 | out = intersection_linestring_linestring_point<PointOut> | |
80 | ::apply(*it1, *it2, robust_policy, out, strategy); | |
81 | } | |
82 | } | |
83 | ||
84 | return out; | |
85 | } | |
86 | }; | |
87 | ||
88 | ||
89 | template <typename PointOut> | |
90 | struct intersection_linestring_multi_linestring_point | |
91 | { | |
92 | template | |
93 | < | |
94 | typename Linestring, typename MultiLinestring, | |
95 | typename RobustPolicy, | |
96 | typename OutputIterator, typename Strategy | |
97 | > | |
98 | static inline OutputIterator apply(Linestring const& linestring, | |
99 | MultiLinestring const& ml, | |
100 | RobustPolicy const& robust_policy, | |
101 | OutputIterator out, | |
102 | Strategy const& strategy) | |
103 | { | |
104 | for (typename boost::range_iterator | |
105 | < | |
106 | MultiLinestring const | |
107 | >::type it = boost::begin(ml); | |
108 | it != boost::end(ml); | |
109 | ++it) | |
110 | { | |
111 | out = intersection_linestring_linestring_point<PointOut> | |
112 | ::apply(linestring, *it, robust_policy, out, strategy); | |
113 | } | |
114 | ||
115 | return out; | |
116 | } | |
117 | }; | |
118 | ||
119 | ||
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. | |
122 | template | |
123 | < | |
124 | bool ReverseAreal, | |
125 | typename LineStringOut, | |
126 | overlay_type OverlayType | |
127 | > | |
128 | struct intersection_of_multi_linestring_with_areal | |
129 | { | |
130 | template | |
131 | < | |
132 | typename MultiLinestring, typename Areal, | |
133 | typename RobustPolicy, | |
134 | typename OutputIterator, typename Strategy | |
135 | > | |
136 | static inline OutputIterator apply(MultiLinestring const& ml, Areal const& areal, | |
137 | RobustPolicy const& robust_policy, | |
138 | OutputIterator out, | |
139 | Strategy const& strategy) | |
140 | { | |
141 | for (typename boost::range_iterator | |
142 | < | |
143 | MultiLinestring const | |
144 | >::type it = boost::begin(ml); | |
145 | it != boost::end(ml); | |
146 | ++it) | |
147 | { | |
148 | out = intersection_of_linestring_with_areal | |
149 | < | |
150 | ReverseAreal, LineStringOut, OverlayType | |
151 | >::apply(*it, areal, robust_policy, out, strategy); | |
152 | } | |
153 | ||
154 | return out; | |
155 | ||
156 | } | |
157 | }; | |
158 | ||
159 | // This one calls the one above with reversed arguments | |
160 | template | |
161 | < | |
162 | bool ReverseAreal, | |
163 | typename LineStringOut, | |
164 | overlay_type OverlayType | |
165 | > | |
166 | struct intersection_of_areal_with_multi_linestring | |
167 | { | |
168 | template | |
169 | < | |
170 | typename Areal, typename MultiLinestring, | |
171 | typename RobustPolicy, | |
172 | typename OutputIterator, typename Strategy | |
173 | > | |
174 | static inline OutputIterator apply(Areal const& areal, MultiLinestring const& ml, | |
175 | RobustPolicy const& robust_policy, | |
176 | OutputIterator out, | |
177 | Strategy const& strategy) | |
178 | { | |
179 | return intersection_of_multi_linestring_with_areal | |
180 | < | |
181 | ReverseAreal, LineStringOut, OverlayType | |
182 | >::apply(ml, areal, robust_policy, out, strategy); | |
183 | } | |
184 | }; | |
185 | ||
186 | ||
187 | ||
188 | template <typename LinestringOut> | |
189 | struct clip_multi_linestring | |
190 | { | |
191 | template | |
192 | < | |
193 | typename MultiLinestring, typename Box, | |
194 | typename RobustPolicy, | |
195 | typename OutputIterator, typename Strategy | |
196 | > | |
197 | static inline OutputIterator apply(MultiLinestring const& multi_linestring, | |
198 | Box const& box, | |
199 | RobustPolicy const& robust_policy, | |
200 | OutputIterator out, Strategy const& ) | |
201 | { | |
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) | |
207 | { | |
208 | out = detail::intersection::clip_range_with_box | |
209 | <LinestringOut>(box, *it, robust_policy, out, lb_strategy); | |
210 | } | |
211 | return out; | |
212 | } | |
213 | }; | |
214 | ||
215 | ||
216 | }} // namespace detail::intersection | |
217 | #endif // DOXYGEN_NO_DETAIL | |
218 | ||
219 | ||
220 | #ifndef DOXYGEN_NO_DISPATCH | |
221 | namespace dispatch | |
222 | { | |
223 | ||
224 | ||
225 | // Linear | |
226 | template | |
227 | < | |
228 | typename MultiLinestring1, typename MultiLinestring2, | |
229 | typename GeometryOut, | |
230 | overlay_type OverlayType, | |
231 | bool Reverse1, bool Reverse2, bool ReverseOut | |
232 | > | |
233 | struct intersection_insert | |
234 | < | |
235 | MultiLinestring1, MultiLinestring2, | |
236 | GeometryOut, | |
237 | OverlayType, | |
238 | Reverse1, Reverse2, ReverseOut, | |
239 | multi_linestring_tag, multi_linestring_tag, point_tag, | |
240 | false, false, false | |
241 | > : detail::intersection::intersection_multi_linestring_multi_linestring_point | |
242 | < | |
243 | GeometryOut | |
244 | > | |
245 | {}; | |
246 | ||
247 | ||
248 | template | |
249 | < | |
250 | typename Linestring, typename MultiLinestring, | |
251 | typename GeometryOut, | |
252 | overlay_type OverlayType, | |
253 | bool Reverse1, bool Reverse2, bool ReverseOut | |
254 | > | |
255 | struct intersection_insert | |
256 | < | |
257 | Linestring, MultiLinestring, | |
258 | GeometryOut, | |
259 | OverlayType, | |
260 | Reverse1, Reverse2, ReverseOut, | |
261 | linestring_tag, multi_linestring_tag, point_tag, | |
262 | false, false, false | |
263 | > : detail::intersection::intersection_linestring_multi_linestring_point | |
264 | < | |
265 | GeometryOut | |
266 | > | |
267 | {}; | |
268 | ||
269 | ||
270 | template | |
271 | < | |
272 | typename MultiLinestring, typename Box, | |
273 | typename GeometryOut, | |
274 | overlay_type OverlayType, | |
275 | bool Reverse1, bool Reverse2, bool ReverseOut | |
276 | > | |
277 | struct intersection_insert | |
278 | < | |
279 | MultiLinestring, Box, | |
280 | GeometryOut, | |
281 | OverlayType, | |
282 | Reverse1, Reverse2, ReverseOut, | |
283 | multi_linestring_tag, box_tag, linestring_tag, | |
284 | false, true, false | |
285 | > : detail::intersection::clip_multi_linestring | |
286 | < | |
287 | GeometryOut | |
288 | > | |
289 | {}; | |
290 | ||
291 | ||
292 | template | |
293 | < | |
294 | typename Linestring, typename MultiPolygon, | |
295 | typename GeometryOut, | |
296 | overlay_type OverlayType, | |
297 | bool ReverseLinestring, bool ReverseMultiPolygon, bool ReverseOut | |
298 | > | |
299 | struct intersection_insert | |
300 | < | |
301 | Linestring, MultiPolygon, | |
302 | GeometryOut, | |
303 | OverlayType, | |
304 | ReverseLinestring, ReverseMultiPolygon, ReverseOut, | |
305 | linestring_tag, multi_polygon_tag, linestring_tag, | |
306 | false, true, false | |
307 | > : detail::intersection::intersection_of_linestring_with_areal | |
308 | < | |
309 | ReverseMultiPolygon, | |
310 | GeometryOut, | |
311 | OverlayType | |
312 | > | |
313 | {}; | |
314 | ||
315 | ||
316 | // Derives from areal/mls because runtime arguments are in that order. | |
317 | // areal/mls reverses it itself to mls/areal | |
318 | template | |
319 | < | |
320 | typename Polygon, typename MultiLinestring, | |
321 | typename GeometryOut, | |
322 | overlay_type OverlayType, | |
323 | bool ReversePolygon, bool ReverseMultiLinestring, bool ReverseOut | |
324 | > | |
325 | struct intersection_insert | |
326 | < | |
327 | Polygon, MultiLinestring, | |
328 | GeometryOut, | |
329 | OverlayType, | |
330 | ReversePolygon, ReverseMultiLinestring, ReverseOut, | |
331 | polygon_tag, multi_linestring_tag, linestring_tag, | |
332 | true, false, false | |
333 | > : detail::intersection::intersection_of_areal_with_multi_linestring | |
334 | < | |
335 | ReversePolygon, | |
336 | GeometryOut, | |
337 | OverlayType | |
338 | > | |
339 | {}; | |
340 | ||
341 | ||
342 | template | |
343 | < | |
344 | typename MultiLinestring, typename Ring, | |
345 | typename GeometryOut, | |
346 | overlay_type OverlayType, | |
347 | bool ReverseMultiLinestring, bool ReverseRing, bool ReverseOut | |
348 | > | |
349 | struct intersection_insert | |
350 | < | |
351 | MultiLinestring, Ring, | |
352 | GeometryOut, | |
353 | OverlayType, | |
354 | ReverseMultiLinestring, ReverseRing, ReverseOut, | |
355 | multi_linestring_tag, ring_tag, linestring_tag, | |
356 | false, true, false | |
357 | > : detail::intersection::intersection_of_multi_linestring_with_areal | |
358 | < | |
359 | ReverseRing, | |
360 | GeometryOut, | |
361 | OverlayType | |
362 | > | |
363 | {}; | |
364 | ||
365 | template | |
366 | < | |
367 | typename MultiLinestring, typename Polygon, | |
368 | typename GeometryOut, | |
369 | overlay_type OverlayType, | |
370 | bool ReverseMultiLinestring, bool ReverseRing, bool ReverseOut | |
371 | > | |
372 | struct intersection_insert | |
373 | < | |
374 | MultiLinestring, Polygon, | |
375 | GeometryOut, | |
376 | OverlayType, | |
377 | ReverseMultiLinestring, ReverseRing, ReverseOut, | |
378 | multi_linestring_tag, polygon_tag, linestring_tag, | |
379 | false, true, false | |
380 | > : detail::intersection::intersection_of_multi_linestring_with_areal | |
381 | < | |
382 | ReverseRing, | |
383 | GeometryOut, | |
384 | OverlayType | |
385 | > | |
386 | {}; | |
387 | ||
388 | ||
389 | ||
390 | template | |
391 | < | |
392 | typename MultiLinestring, typename MultiPolygon, | |
393 | typename GeometryOut, | |
394 | overlay_type OverlayType, | |
395 | bool ReverseMultiLinestring, bool ReverseMultiPolygon, bool ReverseOut | |
396 | > | |
397 | struct intersection_insert | |
398 | < | |
399 | MultiLinestring, MultiPolygon, | |
400 | GeometryOut, | |
401 | OverlayType, | |
402 | ReverseMultiLinestring, ReverseMultiPolygon, ReverseOut, | |
403 | multi_linestring_tag, multi_polygon_tag, linestring_tag, | |
404 | false, true, false | |
405 | > : detail::intersection::intersection_of_multi_linestring_with_areal | |
406 | < | |
407 | ReverseMultiPolygon, | |
408 | GeometryOut, | |
409 | OverlayType | |
410 | > | |
411 | {}; | |
412 | ||
413 | ||
414 | } // namespace dispatch | |
415 | #endif | |
416 | ||
417 | }} // namespace boost::geometry | |
418 | ||
419 | ||
420 | #endif // BOOST_GEOMETRY_ALGORITHMS_DETAIL_INTERSECTION_MULTI_HPP | |
421 |