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

   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>
  56     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>
  70     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     >
  99     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     >
 120     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>
 145     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>
 179     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>
 215     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>
 252     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>
 409     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