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>
applyboost::geometry::detail::overlay::copy_points56     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>
applyboost::geometry::detail::overlay::copy_points70     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     >
applyboost::geometry::detail::overlay::action_selector_pl_pl99     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     >
applyboost::geometry::detail::overlay::action_selector_pl_pl120     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>
applyboost::geometry::detail::overlay::point_point_point145     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>
applyboost::geometry::detail::overlay::multipoint_point_point179     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>
applyboost::geometry::detail::overlay::point_multipoint_point215     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>
applyboost::geometry::detail::overlay::multipoint_multipoint_point252     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>
applyboost::geometry::detail::overlay::union_pointlike_pointlike_point409     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
436