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