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