1 // Boost.Geometry (aka GGL, Generic Geometry Library)
3 // Copyright (c) 2014-2015, Oracle and/or its affiliates.
5 // Licensed under the Boost Software License version 1.0.
6 // http://www.boost.org/users/license.html
8 // Contributed and/or modified by Menelaos Karavelas, on behalf of Oracle
11 #ifndef BOOST_GEOMETRY_ALGORITHMS_DETAIL_OVERLAY_POINTLIKE_POINTLIKE_HPP
12 #define BOOST_GEOMETRY_ALGORITHMS_DETAIL_OVERLAY_POINTLIKE_POINTLIKE_HPP
17 #include <boost/range.hpp>
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>
24 #include <boost/geometry/algorithms/convert.hpp>
25 #include <boost/geometry/algorithms/not_implemented.hpp>
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>
32 namespace boost { namespace geometry
36 #ifndef DOXYGEN_NO_DETAIL
37 namespace detail { namespace overlay
41 // struct for copying points of the pointlike geometries to output
46 typename TagIn = typename tag<GeometryIn>::type
49 : not_implemented<PointOut, GeometryIn>
52 template <typename PointOut, typename PointIn>
53 struct copy_points<PointOut, PointIn, point_tag>
55 template <typename OutputIterator>
56 static inline void apply(PointIn const& point_in,
60 geometry::convert(point_in, point_out);
66 template <typename PointOut, typename MultiPointIn>
67 struct copy_points<PointOut, MultiPointIn, multi_point_tag>
69 template <typename OutputIterator>
70 static inline void apply(MultiPointIn const& multi_point_in,
73 for (typename boost::range_iterator<MultiPointIn const>::type
74 it = boost::begin(multi_point_in);
75 it != boost::end(multi_point_in); ++it)
78 geometry::convert(*it, point_out);
86 // action struct for difference/intersection
87 template <typename PointOut, overlay_type OverlayType>
88 struct action_selector_pl_pl
91 template <typename PointOut>
92 struct action_selector_pl_pl<PointOut, overlay_intersection>
97 typename OutputIterator
99 static inline void apply(Point const& point,
105 copy_points<PointOut, Point>::apply(point, oit);
112 template <typename PointOut>
113 struct action_selector_pl_pl<PointOut, overlay_difference>
118 typename OutputIterator
120 static inline void apply(Point const& point,
126 copy_points<PointOut, Point>::apply(point, oit);
132 //===========================================================================
134 // difference/intersection of point-point
140 overlay_type OverlayType
142 struct point_point_point
144 template <typename RobustPolicy, typename OutputIterator, typename Strategy>
145 static inline OutputIterator apply(Point1 const& point1,
146 Point2 const& point2,
147 RobustPolicy const& ,
151 action_selector_pl_pl
153 PointOut, OverlayType
155 detail::equals::equals_point_point(point1, point2),
164 // difference of multipoint-point
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
174 overlay_type OverlayType
176 struct multipoint_point_point
178 template <typename RobustPolicy, typename OutputIterator, typename Strategy>
179 static inline OutputIterator apply(MultiPoint const& multipoint,
181 RobustPolicy const& ,
185 BOOST_GEOMETRY_ASSERT( OverlayType == overlay_difference );
187 for (typename boost::range_iterator<MultiPoint const>::type
188 it = boost::begin(multipoint);
189 it != boost::end(multipoint); ++it)
191 action_selector_pl_pl
193 PointOut, OverlayType
195 detail::equals::equals_point_point(*it, point),
204 // difference/intersection of point-multipoint
210 overlay_type OverlayType
212 struct point_multipoint_point
214 template <typename RobustPolicy, typename OutputIterator, typename Strategy>
215 static inline OutputIterator apply(Point const& point,
216 MultiPoint const& multipoint,
217 RobustPolicy const& ,
221 typedef action_selector_pl_pl<PointOut, OverlayType> action;
223 for (typename boost::range_iterator<MultiPoint const>::type
224 it = boost::begin(multipoint);
225 it != boost::end(multipoint); ++it)
227 if ( detail::equals::equals_point_point(*it, point) )
229 action::apply(point, true, oit);
234 action::apply(point, false, oit);
241 // difference/intersection of multipoint-multipoint
244 typename MultiPoint1,
245 typename MultiPoint2,
247 overlay_type OverlayType
249 struct multipoint_multipoint_point
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,
256 Strategy const& strategy)
258 if ( OverlayType != overlay_difference
259 && boost::size(multipoint1) > boost::size(multipoint2) )
261 return multipoint_multipoint_point
263 MultiPoint2, MultiPoint1, PointOut, OverlayType
264 >::apply(multipoint2, multipoint1, robust_policy, oit, strategy);
267 std::vector<typename boost::range_value<MultiPoint2>::type>
268 points2(boost::begin(multipoint2), boost::end(multipoint2));
270 std::sort(points2.begin(), points2.end(), detail::relate::less());
272 for (typename boost::range_iterator<MultiPoint1 const>::type
273 it1 = boost::begin(multipoint1);
274 it1 != boost::end(multipoint1); ++it1)
276 bool found = std::binary_search(points2.begin(), points2.end(),
277 *it1, detail::relate::less());
279 action_selector_pl_pl
281 PointOut, OverlayType
282 >::apply(*it1, found, oit);
288 }} // namespace detail::overlay
289 #endif // DOXYGEN_NO_DETAIL
292 //===========================================================================
295 #ifndef DOXYGEN_NO_DISPATCH
296 namespace detail_dispatch { namespace overlay
299 // dispatch struct for pointlike-pointlike difference/intersection
306 overlay_type OverlayType,
310 struct pointlike_pointlike_point
311 : not_implemented<PointLike1, PointLike2, PointOut>
320 overlay_type OverlayType
322 struct pointlike_pointlike_point
324 Point1, Point2, PointOut, OverlayType,
326 > : detail::overlay::point_point_point
328 Point1, Point2, PointOut, OverlayType
338 overlay_type OverlayType
340 struct pointlike_pointlike_point
342 Point, MultiPoint, PointOut, OverlayType,
343 point_tag, multi_point_tag
344 > : detail::overlay::point_multipoint_point
346 Point, MultiPoint, PointOut, OverlayType
356 overlay_type OverlayType
358 struct pointlike_pointlike_point
360 MultiPoint, Point, PointOut, OverlayType,
361 multi_point_tag, point_tag
362 > : detail::overlay::multipoint_point_point
364 MultiPoint, Point, PointOut, OverlayType
371 typename MultiPoint1,
372 typename MultiPoint2,
374 overlay_type OverlayType
376 struct pointlike_pointlike_point
378 MultiPoint1, MultiPoint2, PointOut, OverlayType,
379 multi_point_tag, multi_point_tag
380 > : detail::overlay::multipoint_multipoint_point
382 MultiPoint1, MultiPoint2, PointOut, OverlayType
387 }} // namespace detail_dispatch::overlay
388 #endif // DOXYGEN_NO_DISPATCH
391 //===========================================================================
394 #ifndef DOXYGEN_NO_DETAIL
395 namespace detail { namespace overlay
399 // generic pointlike-pointlike union implementation
406 struct union_pointlike_pointlike_point
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,
413 Strategy const& strategy)
415 copy_points<PointOut, PointLike1>::apply(pointlike1, oit);
417 return detail_dispatch::overlay::pointlike_pointlike_point
419 PointLike2, PointLike1, PointOut, overlay_difference,
420 typename tag<PointLike2>::type,
421 typename tag<PointLike1>::type
422 >::apply(pointlike2, pointlike1, robust_policy, oit, strategy);
428 }} // namespace detail::overlay
429 #endif // DOXYGEN_NO_DETAIL
432 }} // namespace boost::geometry
435 #endif // BOOST_GEOMETRY_ALGORITHMS_DETAIL_OVERLAY_POINTLIKE_POINTLIKE_HPP