]>
Commit | Line | Data |
---|---|---|
7c673cae FG |
1 | // Boost.Geometry (aka GGL, Generic Geometry Library) |
2 | ||
3 | // Copyright (c) 2014-2015, Oracle and/or its affiliates. | |
4 | ||
5 | // Licensed under the Boost Software License version 1.0. | |
6 | // http://www.boost.org/users/license.html | |
7 | ||
8 | // Contributed and/or modified by Menelaos Karavelas, on behalf of Oracle | |
9 | ||
10 | ||
11 | #ifndef BOOST_GEOMETRY_ALGORITHMS_DETAIL_OVERLAY_POINTLIKE_POINTLIKE_HPP | |
12 | #define BOOST_GEOMETRY_ALGORITHMS_DETAIL_OVERLAY_POINTLIKE_POINTLIKE_HPP | |
13 | ||
14 | #include <algorithm> | |
15 | #include <vector> | |
16 | ||
17 | #include <boost/range.hpp> | |
18 | ||
19 | #include <boost/geometry/core/assert.hpp> | |
20 | #include <boost/geometry/core/point_type.hpp> | |
21 | #include <boost/geometry/core/tag.hpp> | |
22 | #include <boost/geometry/core/tags.hpp> | |
23 | ||
24 | #include <boost/geometry/algorithms/convert.hpp> | |
25 | #include <boost/geometry/algorithms/not_implemented.hpp> | |
26 | ||
27 | #include <boost/geometry/algorithms/detail/relate/less.hpp> | |
28 | #include <boost/geometry/algorithms/detail/equals/point_point.hpp> | |
29 | #include <boost/geometry/algorithms/detail/overlay/overlay_type.hpp> | |
30 | ||
31 | ||
32 | namespace boost { namespace geometry | |
33 | { | |
34 | ||
35 | ||
36 | #ifndef DOXYGEN_NO_DETAIL | |
37 | namespace detail { namespace overlay | |
38 | { | |
39 | ||
40 | ||
41 | // struct for copying points of the pointlike geometries to output | |
42 | template | |
43 | < | |
44 | typename PointOut, | |
45 | typename GeometryIn, | |
46 | typename TagIn = typename tag<GeometryIn>::type | |
47 | > | |
48 | struct copy_points | |
49 | : not_implemented<PointOut, GeometryIn> | |
50 | {}; | |
51 | ||
52 | template <typename PointOut, typename PointIn> | |
53 | struct copy_points<PointOut, PointIn, point_tag> | |
54 | { | |
55 | template <typename OutputIterator> | |
56 | static inline void apply(PointIn const& point_in, | |
57 | OutputIterator& oit) | |
58 | { | |
59 | PointOut point_out; | |
60 | geometry::convert(point_in, point_out); | |
61 | *oit++ = point_out; | |
62 | } | |
63 | }; | |
64 | ||
65 | ||
66 | template <typename PointOut, typename MultiPointIn> | |
67 | struct copy_points<PointOut, MultiPointIn, multi_point_tag> | |
68 | { | |
69 | template <typename OutputIterator> | |
70 | static inline void apply(MultiPointIn const& multi_point_in, | |
71 | OutputIterator& oit) | |
72 | { | |
73 | for (typename boost::range_iterator<MultiPointIn const>::type | |
74 | it = boost::begin(multi_point_in); | |
75 | it != boost::end(multi_point_in); ++it) | |
76 | { | |
77 | PointOut point_out; | |
78 | geometry::convert(*it, point_out); | |
79 | *oit++ = point_out; | |
80 | } | |
81 | } | |
82 | }; | |
83 | ||
84 | ||
85 | ||
86 | // action struct for difference/intersection | |
87 | template <typename PointOut, overlay_type OverlayType> | |
88 | struct action_selector_pl_pl | |
89 | {}; | |
90 | ||
91 | template <typename PointOut> | |
92 | struct action_selector_pl_pl<PointOut, overlay_intersection> | |
93 | { | |
94 | template | |
95 | < | |
96 | typename Point, | |
97 | typename OutputIterator | |
98 | > | |
99 | static inline void apply(Point const& point, | |
100 | bool is_common, | |
101 | OutputIterator& oit) | |
102 | { | |
103 | if ( is_common ) | |
104 | { | |
105 | copy_points<PointOut, Point>::apply(point, oit); | |
106 | } | |
107 | } | |
108 | }; | |
109 | ||
110 | ||
111 | ||
112 | template <typename PointOut> | |
113 | struct action_selector_pl_pl<PointOut, overlay_difference> | |
114 | { | |
115 | template | |
116 | < | |
117 | typename Point, | |
118 | typename OutputIterator | |
119 | > | |
120 | static inline void apply(Point const& point, | |
121 | bool is_common, | |
122 | OutputIterator& oit) | |
123 | { | |
124 | if ( !is_common ) | |
125 | { | |
126 | copy_points<PointOut, Point>::apply(point, oit); | |
127 | } | |
128 | } | |
129 | }; | |
130 | ||
131 | ||
132 | //=========================================================================== | |
133 | ||
134 | // difference/intersection of point-point | |
135 | template | |
136 | < | |
137 | typename Point1, | |
138 | typename Point2, | |
139 | typename PointOut, | |
140 | overlay_type OverlayType | |
141 | > | |
142 | struct point_point_point | |
143 | { | |
144 | template <typename RobustPolicy, typename OutputIterator, typename Strategy> | |
145 | static inline OutputIterator apply(Point1 const& point1, | |
146 | Point2 const& point2, | |
147 | RobustPolicy const& , | |
148 | OutputIterator oit, | |
149 | Strategy const&) | |
150 | { | |
151 | action_selector_pl_pl | |
152 | < | |
153 | PointOut, OverlayType | |
154 | >::apply(point1, | |
155 | detail::equals::equals_point_point(point1, point2), | |
156 | oit); | |
157 | ||
158 | return oit; | |
159 | } | |
160 | }; | |
161 | ||
162 | ||
163 | ||
164 | // difference of multipoint-point | |
165 | // | |
166 | // the apply method in the following struct is called only for | |
167 | // difference; for intersection the reversal will | |
168 | // always call the point-multipoint version | |
169 | template | |
170 | < | |
171 | typename MultiPoint, | |
172 | typename Point, | |
173 | typename PointOut, | |
174 | overlay_type OverlayType | |
175 | > | |
176 | struct multipoint_point_point | |
177 | { | |
178 | template <typename RobustPolicy, typename OutputIterator, typename Strategy> | |
179 | static inline OutputIterator apply(MultiPoint const& multipoint, | |
180 | Point const& point, | |
181 | RobustPolicy const& , | |
182 | OutputIterator oit, | |
183 | Strategy const&) | |
184 | { | |
185 | BOOST_GEOMETRY_ASSERT( OverlayType == overlay_difference ); | |
186 | ||
187 | for (typename boost::range_iterator<MultiPoint const>::type | |
188 | it = boost::begin(multipoint); | |
189 | it != boost::end(multipoint); ++it) | |
190 | { | |
191 | action_selector_pl_pl | |
192 | < | |
193 | PointOut, OverlayType | |
194 | >::apply(*it, | |
195 | detail::equals::equals_point_point(*it, point), | |
196 | oit); | |
197 | } | |
198 | ||
199 | return oit; | |
200 | } | |
201 | }; | |
202 | ||
203 | ||
204 | // difference/intersection of point-multipoint | |
205 | template | |
206 | < | |
207 | typename Point, | |
208 | typename MultiPoint, | |
209 | typename PointOut, | |
210 | overlay_type OverlayType | |
211 | > | |
212 | struct point_multipoint_point | |
213 | { | |
214 | template <typename RobustPolicy, typename OutputIterator, typename Strategy> | |
215 | static inline OutputIterator apply(Point const& point, | |
216 | MultiPoint const& multipoint, | |
217 | RobustPolicy const& , | |
218 | OutputIterator oit, | |
219 | Strategy const&) | |
220 | { | |
221 | typedef action_selector_pl_pl<PointOut, OverlayType> action; | |
222 | ||
223 | for (typename boost::range_iterator<MultiPoint const>::type | |
224 | it = boost::begin(multipoint); | |
225 | it != boost::end(multipoint); ++it) | |
226 | { | |
227 | if ( detail::equals::equals_point_point(*it, point) ) | |
228 | { | |
229 | action::apply(point, true, oit); | |
230 | return oit; | |
231 | } | |
232 | } | |
233 | ||
234 | action::apply(point, false, oit); | |
235 | return oit; | |
236 | } | |
237 | }; | |
238 | ||
239 | ||
240 | ||
241 | // difference/intersection of multipoint-multipoint | |
242 | template | |
243 | < | |
244 | typename MultiPoint1, | |
245 | typename MultiPoint2, | |
246 | typename PointOut, | |
247 | overlay_type OverlayType | |
248 | > | |
249 | struct multipoint_multipoint_point | |
250 | { | |
251 | template <typename RobustPolicy, typename OutputIterator, typename Strategy> | |
252 | static inline OutputIterator apply(MultiPoint1 const& multipoint1, | |
253 | MultiPoint2 const& multipoint2, | |
254 | RobustPolicy const& robust_policy, | |
255 | OutputIterator oit, | |
256 | Strategy const& strategy) | |
257 | { | |
258 | if ( OverlayType != overlay_difference | |
259 | && boost::size(multipoint1) > boost::size(multipoint2) ) | |
260 | { | |
261 | return multipoint_multipoint_point | |
262 | < | |
263 | MultiPoint2, MultiPoint1, PointOut, OverlayType | |
264 | >::apply(multipoint2, multipoint1, robust_policy, oit, strategy); | |
265 | } | |
266 | ||
267 | std::vector<typename boost::range_value<MultiPoint2>::type> | |
268 | points2(boost::begin(multipoint2), boost::end(multipoint2)); | |
269 | ||
270 | std::sort(points2.begin(), points2.end(), detail::relate::less()); | |
271 | ||
272 | for (typename boost::range_iterator<MultiPoint1 const>::type | |
273 | it1 = boost::begin(multipoint1); | |
274 | it1 != boost::end(multipoint1); ++it1) | |
275 | { | |
276 | bool found = std::binary_search(points2.begin(), points2.end(), | |
277 | *it1, detail::relate::less()); | |
278 | ||
279 | action_selector_pl_pl | |
280 | < | |
281 | PointOut, OverlayType | |
282 | >::apply(*it1, found, oit); | |
283 | } | |
284 | return oit; | |
285 | } | |
286 | }; | |
287 | ||
288 | }} // namespace detail::overlay | |
289 | #endif // DOXYGEN_NO_DETAIL | |
290 | ||
291 | ||
292 | //=========================================================================== | |
293 | ||
294 | ||
295 | #ifndef DOXYGEN_NO_DISPATCH | |
296 | namespace detail_dispatch { namespace overlay | |
297 | { | |
298 | ||
299 | // dispatch struct for pointlike-pointlike difference/intersection | |
300 | // computation | |
301 | template | |
302 | < | |
303 | typename PointLike1, | |
304 | typename PointLike2, | |
305 | typename PointOut, | |
306 | overlay_type OverlayType, | |
307 | typename Tag1, | |
308 | typename Tag2 | |
309 | > | |
310 | struct pointlike_pointlike_point | |
311 | : not_implemented<PointLike1, PointLike2, PointOut> | |
312 | {}; | |
313 | ||
314 | ||
315 | template | |
316 | < | |
317 | typename Point1, | |
318 | typename Point2, | |
319 | typename PointOut, | |
320 | overlay_type OverlayType | |
321 | > | |
322 | struct pointlike_pointlike_point | |
323 | < | |
324 | Point1, Point2, PointOut, OverlayType, | |
325 | point_tag, point_tag | |
326 | > : detail::overlay::point_point_point | |
327 | < | |
328 | Point1, Point2, PointOut, OverlayType | |
329 | > | |
330 | {}; | |
331 | ||
332 | ||
333 | template | |
334 | < | |
335 | typename Point, | |
336 | typename MultiPoint, | |
337 | typename PointOut, | |
338 | overlay_type OverlayType | |
339 | > | |
340 | struct pointlike_pointlike_point | |
341 | < | |
342 | Point, MultiPoint, PointOut, OverlayType, | |
343 | point_tag, multi_point_tag | |
344 | > : detail::overlay::point_multipoint_point | |
345 | < | |
346 | Point, MultiPoint, PointOut, OverlayType | |
347 | > | |
348 | {}; | |
349 | ||
350 | ||
351 | template | |
352 | < | |
353 | typename MultiPoint, | |
354 | typename Point, | |
355 | typename PointOut, | |
356 | overlay_type OverlayType | |
357 | > | |
358 | struct pointlike_pointlike_point | |
359 | < | |
360 | MultiPoint, Point, PointOut, OverlayType, | |
361 | multi_point_tag, point_tag | |
362 | > : detail::overlay::multipoint_point_point | |
363 | < | |
364 | MultiPoint, Point, PointOut, OverlayType | |
365 | > | |
366 | {}; | |
367 | ||
368 | ||
369 | template | |
370 | < | |
371 | typename MultiPoint1, | |
372 | typename MultiPoint2, | |
373 | typename PointOut, | |
374 | overlay_type OverlayType | |
375 | > | |
376 | struct pointlike_pointlike_point | |
377 | < | |
378 | MultiPoint1, MultiPoint2, PointOut, OverlayType, | |
379 | multi_point_tag, multi_point_tag | |
380 | > : detail::overlay::multipoint_multipoint_point | |
381 | < | |
382 | MultiPoint1, MultiPoint2, PointOut, OverlayType | |
383 | > | |
384 | {}; | |
385 | ||
386 | ||
387 | }} // namespace detail_dispatch::overlay | |
388 | #endif // DOXYGEN_NO_DISPATCH | |
389 | ||
390 | ||
391 | //=========================================================================== | |
392 | ||
393 | ||
394 | #ifndef DOXYGEN_NO_DETAIL | |
395 | namespace detail { namespace overlay | |
396 | { | |
397 | ||
398 | ||
399 | // generic pointlike-pointlike union implementation | |
400 | template | |
401 | < | |
402 | typename PointLike1, | |
403 | typename PointLike2, | |
404 | typename PointOut | |
405 | > | |
406 | struct union_pointlike_pointlike_point | |
407 | { | |
408 | template <typename RobustPolicy, typename OutputIterator, typename Strategy> | |
409 | static inline OutputIterator apply(PointLike1 const& pointlike1, | |
410 | PointLike2 const& pointlike2, | |
411 | RobustPolicy const& robust_policy, | |
412 | OutputIterator oit, | |
413 | Strategy const& strategy) | |
414 | { | |
415 | copy_points<PointOut, PointLike1>::apply(pointlike1, oit); | |
416 | ||
417 | return detail_dispatch::overlay::pointlike_pointlike_point | |
418 | < | |
419 | PointLike2, PointLike1, PointOut, overlay_difference, | |
420 | typename tag<PointLike2>::type, | |
421 | typename tag<PointLike1>::type | |
422 | >::apply(pointlike2, pointlike1, robust_policy, oit, strategy); | |
423 | } | |
424 | ||
425 | }; | |
426 | ||
427 | ||
428 | }} // namespace detail::overlay | |
429 | #endif // DOXYGEN_NO_DETAIL | |
430 | ||
431 | ||
432 | }} // namespace boost::geometry | |
433 | ||
434 | ||
435 | #endif // BOOST_GEOMETRY_ALGORITHMS_DETAIL_OVERLAY_POINTLIKE_POINTLIKE_HPP |