ceph/src/boost/boost/geometry/algorithms/detail/overlay/pointlike_pointlike.hpp

   1 // Boost.Geometry (aka GGL, Generic Geometry Library)
   2
   3 // Copyright (c) 2014-2017, 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>
  58     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>
  72     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_pl
  91 {};
  92
  93 template <typename PointOut>
  94 struct action_selector_pl_pl<PointOut, overlay_intersection>
  95 {
  96     template
  97     <
  98         typename Point,
  99         typename OutputIterator
 100     >
 101     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_pl<PointOut, overlay_difference>
 116 {
 117     template
 118     <
 119         typename Point,
 120         typename OutputIterator
 121     >
 122     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>
 147     static inline OutputIterator apply(Point1 const& point1,
 148                                        Point2 const& point2,
 149                                        RobustPolicy const& ,
 150                                        OutputIterator oit,
 151                                        Strategy const&)
 152     {
 153         action_selector_pl_pl
 154             <
 155                 PointOut, OverlayType
 156             >::apply(point1,
 157                      detail::equals::equals_point_point(point1, point2),
 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>
 181     static inline OutputIterator apply(MultiPoint const& multipoint,
 182                                        Point const& point,
 183                                        RobustPolicy const& ,
 184                                        OutputIterator oit,
 185                                        Strategy const&)
 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_pl
 194                 <
 195                     PointOut, OverlayType
 196                 >::apply(*it,
 197                          detail::equals::equals_point_point(*it, point),
 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>
 217     static inline OutputIterator apply(Point const& point,
 218                                        MultiPoint const& multipoint,
 219                                        RobustPolicy const& ,
 220                                        OutputIterator oit,
 221                                        Strategy const&)
 222     {
 223         typedef action_selector_pl_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) )
 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>
 254     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         if ( OverlayType != overlay_difference
 261              && boost::size(multipoint1) > boost::size(multipoint2) )
 262         {
 263             return multipoint_multipoint_point
 264                 <
 265                     MultiPoint2, MultiPoint1, PointOut, OverlayType
 266                 >::apply(multipoint2, multipoint1, robust_policy, oit, strategy);
 267         }
 268
 269         typedef typename boost::range_value<MultiPoint2>::type point2_type;
 270
 271         std::vector<point2_type> points2(boost::begin(multipoint2),
 272                                          boost::end(multipoint2));
 273
 274         geometry::less<> const less = geometry::less<>();
 275         std::sort(points2.begin(), points2.end(), less);
 276
 277         for (typename boost::range_iterator<MultiPoint1 const>::type
 278                  it1 = boost::begin(multipoint1);
 279              it1 != boost::end(multipoint1); ++it1)
 280         {
 281             bool found = std::binary_search(points2.begin(), points2.end(),
 282                                             *it1, less);
 283
 284             action_selector_pl_pl
 285                 <
 286                     PointOut, OverlayType
 287                 >::apply(*it1, found, oit);
 288         }
 289         return oit;
 290     }
 291 };
 292
 293 }} // namespace detail::overlay
 294 #endif // DOXYGEN_NO_DETAIL
 295
 296
 297 //===========================================================================
 298
 299
 300 #ifndef DOXYGEN_NO_DISPATCH
 301 namespace detail_dispatch { namespace overlay
 302 {
 303
 304 // dispatch struct for pointlike-pointlike difference/intersection
 305 // computation
 306 template
 307 <
 308     typename PointLike1,
 309     typename PointLike2,
 310     typename PointOut,
 311     overlay_type OverlayType,
 312     typename Tag1,
 313     typename Tag2
 314 >
 315 struct pointlike_pointlike_point
 316     : not_implemented<PointLike1, PointLike2, PointOut>
 317 {};
 318
 319
 320 template
 321 <
 322     typename Point1,
 323     typename Point2,
 324     typename PointOut,
 325     overlay_type OverlayType
 326 >
 327 struct pointlike_pointlike_point
 328     <
 329         Point1, Point2, PointOut, OverlayType,
 330         point_tag, point_tag
 331     > : detail::overlay::point_point_point
 332         <
 333             Point1, Point2, PointOut, OverlayType
 334         >
 335 {};
 336
 337
 338 template
 339 <
 340     typename Point,
 341     typename MultiPoint,
 342     typename PointOut,
 343     overlay_type OverlayType
 344 >
 345 struct pointlike_pointlike_point
 346     <
 347         Point, MultiPoint, PointOut, OverlayType,
 348         point_tag, multi_point_tag
 349     > : detail::overlay::point_multipoint_point
 350         <
 351             Point, MultiPoint, PointOut, OverlayType
 352         >
 353 {};
 354
 355
 356 template
 357 <
 358     typename MultiPoint,
 359     typename Point,
 360     typename PointOut,
 361     overlay_type OverlayType
 362 >
 363 struct pointlike_pointlike_point
 364     <
 365         MultiPoint, Point, PointOut, OverlayType,
 366         multi_point_tag, point_tag
 367     > : detail::overlay::multipoint_point_point
 368         <
 369             MultiPoint, Point, PointOut, OverlayType
 370         >
 371 {};
 372
 373
 374 template
 375 <
 376     typename MultiPoint1,
 377     typename MultiPoint2,
 378     typename PointOut,
 379     overlay_type OverlayType
 380 >
 381 struct pointlike_pointlike_point
 382     <
 383         MultiPoint1, MultiPoint2, PointOut, OverlayType,
 384         multi_point_tag, multi_point_tag
 385     > : detail::overlay::multipoint_multipoint_point
 386         <
 387             MultiPoint1, MultiPoint2, PointOut, OverlayType
 388         >
 389 {};
 390
 391
 392 }} // namespace detail_dispatch::overlay
 393 #endif // DOXYGEN_NO_DISPATCH
 394
 395
 396 //===========================================================================
 397
 398
 399 #ifndef DOXYGEN_NO_DETAIL
 400 namespace detail { namespace overlay
 401 {
 402
 403
 404 // generic pointlike-pointlike union implementation
 405 template
 406 <
 407     typename PointLike1,
 408     typename PointLike2,
 409     typename PointOut
 410 >
 411 struct union_pointlike_pointlike_point
 412 {
 413     template <typename RobustPolicy, typename OutputIterator, typename Strategy>
 414     static inline OutputIterator apply(PointLike1 const& pointlike1,
 415                                        PointLike2 const& pointlike2,
 416                                        RobustPolicy const& robust_policy,
 417                                        OutputIterator oit,
 418                                        Strategy const& strategy)
 419     {
 420         copy_points<PointOut, PointLike1>::apply(pointlike1, oit);
 421
 422         return detail_dispatch::overlay::pointlike_pointlike_point
 423             <
 424                 PointLike2, PointLike1, PointOut, overlay_difference,
 425                 typename tag<PointLike2>::type,
 426                 typename tag<PointLike1>::type
 427             >::apply(pointlike2, pointlike1, robust_policy, oit, strategy);
 428     }
 429
 430 };
 431
 432
 433 }} // namespace detail::overlay
 434 #endif // DOXYGEN_NO_DETAIL
 435
 436
 437 }} // namespace boost::geometry
 438
 439
 440 #endif // BOOST_GEOMETRY_ALGORITHMS_DETAIL_OVERLAY_POINTLIKE_POINTLIKE_HPP