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

   1 // Boost.Geometry (aka GGL, Generic Geometry Library)
   2
   3 // Copyright (c) 2017 Adam Wulkiewicz, Lodz, Poland.
   4
   5 // Copyright (c) 2015-2020, Oracle and/or its affiliates.
   6
   7 // Contributed and/or modified by Menelaos Karavelas, on behalf of Oracle
   8 // Contributed and/or modified by Adam Wulkiewicz, on behalf of Oracle
   9
  10 // Licensed under the Boost Software License version 1.0.
  11 // http://www.boost.org/users/license.html
  12
  13
  14 #ifndef BOOST_GEOMETRY_ALGORITHMS_DETAIL_OVERLAY_POINTLIKE_LINEAR_HPP
  15 #define BOOST_GEOMETRY_ALGORITHMS_DETAIL_OVERLAY_POINTLIKE_LINEAR_HPP
  16
  17 #include <iterator>
  18 #include <vector>
  19
  20 #include <boost/range/begin.hpp>
  21 #include <boost/range/end.hpp>
  22 #include <boost/range/value_type.hpp>
  23
  24 #include <boost/geometry/algorithms/disjoint.hpp>
  25 #include <boost/geometry/algorithms/envelope.hpp>
  26 #include <boost/geometry/algorithms/expand.hpp>
  27 #include <boost/geometry/algorithms/not_implemented.hpp>
  28
  29 #include <boost/geometry/algorithms/detail/not.hpp>
  30 #include <boost/geometry/algorithms/detail/partition.hpp>
  31 #include <boost/geometry/algorithms/detail/disjoint/point_geometry.hpp>
  32 #include <boost/geometry/algorithms/detail/equals/point_point.hpp>
  33 #include <boost/geometry/algorithms/detail/overlay/overlay_type.hpp>
  34 #include <boost/geometry/algorithms/detail/overlay/pointlike_pointlike.hpp>
  35
  36 #include <boost/geometry/core/tags.hpp>
  37
  38 #include <boost/geometry/geometries/box.hpp>
  39
  40 #include <boost/geometry/iterators/segment_iterator.hpp>
  41
  42 // TEMP
  43 #include <boost/geometry/strategies/envelope/cartesian.hpp>
  44 #include <boost/geometry/strategies/envelope/geographic.hpp>
  45 #include <boost/geometry/strategies/envelope/spherical.hpp>
  46
  47
  48 namespace boost { namespace geometry
  49 {
  50
  51
  52 #ifndef DOXYGEN_NO_DETAIL
  53 namespace detail { namespace overlay
  54 {
  55
  56
  57 // difference/intersection of point-linear
  58 template
  59 <
  60     typename Point,
  61     typename Geometry,
  62     typename PointOut,
  63     overlay_type OverlayType,
  64     typename Policy
  65 >
  66 struct point_single_point
  67 {
  68     template <typename RobustPolicy, typename OutputIterator, typename Strategy>
  69     static inline OutputIterator apply(Point const& point,
  70                                        Geometry const& geometry,
  71                                        RobustPolicy const&,
  72                                        OutputIterator oit,
  73                                        Strategy const& strategy)
  74     {
  75         action_selector_pl
  76             <
  77                 PointOut, OverlayType
  78             >::apply(point, Policy::apply(point, geometry, strategy), oit);
  79         return oit;
  80     }
  81 };
  82
  83 // difference/intersection of multipoint-segment
  84 template
  85 <
  86     typename MultiPoint,
  87     typename Geometry,
  88     typename PointOut,
  89     overlay_type OverlayType,
  90     typename Policy
  91 >
  92 struct multipoint_single_point
  93 {
  94     template <typename RobustPolicy, typename OutputIterator, typename Strategy>
  95     static inline OutputIterator apply(MultiPoint const& multipoint,
  96                                        Geometry const& geometry,
  97                                        RobustPolicy const&,
  98                                        OutputIterator oit,
  99                                        Strategy const& strategy)
 100     {
 101         for (typename boost::range_iterator<MultiPoint const>::type
 102                  it = boost::begin(multipoint);
 103              it != boost::end(multipoint);
 104              ++it)
 105         {
 106             action_selector_pl
 107                 <
 108                     PointOut, OverlayType
 109                 >::apply(*it, Policy::apply(*it, geometry, strategy), oit);
 110         }
 111
 112         return oit;
 113     }
 114 };
 115
 116
 117 // difference/intersection of multipoint-linear
 118 template
 119 <
 120     typename MultiPoint,
 121     typename Linear,
 122     typename PointOut,
 123     overlay_type OverlayType,
 124     typename Policy
 125 >
 126 class multipoint_linear_point
 127 {
 128 private:
 129     // structs for partition -- start
 130     template <typename Strategy>
 131     struct expand_box_point
 132     {
 133         expand_box_point(Strategy const& strategy)
 134             : m_strategy(strategy)
 135         {}
 136
 137         template <typename Box, typename Point>
 138         inline void apply(Box& total, Point const& point) const
 139         {
 140             geometry::expand(total, point, m_strategy);
 141         }
 142
 143         Strategy const& m_strategy;
 144     };
 145
 146     template <typename Strategy>
 147     struct expand_box_segment
 148     {
 149         explicit expand_box_segment(Strategy const& strategy)
 150             : m_strategy(strategy)
 151         {}
 152
 153         template <typename Box, typename Segment>
 154         inline void apply(Box& total, Segment const& segment) const
 155         {
 156             geometry::expand(total,
 157                              geometry::return_envelope<Box>(segment, m_strategy),
 158                              m_strategy);
 159         }
 160
 161         Strategy const& m_strategy;
 162     };
 163
 164     template <typename Strategy>
 165     struct overlaps_box_point
 166     {
 167         explicit overlaps_box_point(Strategy const& strategy)
 168             : m_strategy(strategy)
 169         {}
 170
 171         template <typename Box, typename Point>
 172         inline bool apply(Box const& box, Point const& point) const
 173         {
 174             return ! geometry::disjoint(point, box, m_strategy);
 175         }
 176
 177         Strategy const& m_strategy;
 178     };
 179
 180     template <typename Strategy>
 181     struct overlaps_box_segment
 182     {
 183         explicit overlaps_box_segment(Strategy const& strategy)
 184             : m_strategy(strategy)
 185         {}
 186
 187         template <typename Box, typename Segment>
 188         inline bool apply(Box const& box, Segment const& segment) const
 189         {
 190             return ! geometry::disjoint(segment, box, m_strategy);
 191         }
 192
 193         Strategy const& m_strategy;
 194     };
 195
 196     template <typename OutputIterator, typename Strategy>
 197     class item_visitor_type
 198     {
 199     public:
 200         item_visitor_type(OutputIterator& oit, Strategy const& strategy)
 201             : m_oit(oit)
 202             , m_strategy(strategy)
 203         {}
 204
 205         template <typename Item1, typename Item2>
 206         inline bool apply(Item1 const& item1, Item2 const& item2)
 207         {
 208             action_selector_pl
 209                 <
 210                     PointOut, overlay_intersection
 211                 >::apply(item1, Policy::apply(item1, item2, m_strategy), m_oit);
 212
 213             return true;
 214         }
 215
 216     private:
 217         OutputIterator& m_oit;
 218         Strategy const& m_strategy;
 219     };
 220     // structs for partition -- end
 221
 222     class segment_range
 223     {
 224     public:
 225         typedef geometry::segment_iterator<Linear const> const_iterator;
 226         typedef const_iterator iterator;
 227
 228         explicit segment_range(Linear const& linear)
 229             : m_linear(linear)
 230         {}
 231
 232         const_iterator begin() const
 233         {
 234             return geometry::segments_begin(m_linear);
 235         }
 236
 237         const_iterator end() const
 238         {
 239             return geometry::segments_end(m_linear);
 240         }
 241
 242     private:
 243         Linear const& m_linear;
 244     };
 245
 246     template <typename OutputIterator, typename Strategy>
 247     static inline OutputIterator get_common_points(MultiPoint const& multipoint,
 248                                                    Linear const& linear,
 249                                                    OutputIterator oit,
 250                                                    Strategy const& strategy)
 251     {
 252         item_visitor_type<OutputIterator, Strategy> item_visitor(oit, strategy);
 253
 254         // TODO: disjoint Segment/Box may be called in partition multiple times
 255         // possibly for non-cartesian segments which could be slow. We should consider
 256         // passing a range of bounding boxes of segments after calculating them once.
 257         // Alternatively instead of a range of segments a range of Segment/Envelope pairs
 258         // should be passed, where envelope would be lazily calculated when needed the first time
 259         geometry::partition
 260             <
 261                 geometry::model::box
 262                     <
 263                         typename boost::range_value<MultiPoint>::type
 264                     >
 265             >::apply(multipoint, segment_range(linear), item_visitor,
 266                      expand_box_point<Strategy>(strategy),
 267                      overlaps_box_point<Strategy>(strategy),
 268                      expand_box_segment<Strategy>(strategy),
 269                      overlaps_box_segment<Strategy>(strategy));
 270
 271         return oit;
 272     }
 273
 274 public:
 275     template <typename RobustPolicy, typename OutputIterator, typename Strategy>
 276     static inline OutputIterator apply(MultiPoint const& multipoint,
 277                                        Linear const& linear,
 278                                        RobustPolicy const& robust_policy,
 279                                        OutputIterator oit,
 280                                        Strategy const& strategy)
 281     {
 282         typedef std::vector
 283             <
 284                 typename boost::range_value<MultiPoint>::type
 285             > point_vector_type;
 286
 287         point_vector_type common_points;
 288
 289         // compute the common points
 290         get_common_points(multipoint, linear,
 291                           std::back_inserter(common_points),
 292                           strategy);
 293
 294         return multipoint_multipoint_point
 295             <
 296                 MultiPoint, point_vector_type, PointOut, OverlayType
 297             >::apply(multipoint, common_points, robust_policy, oit, strategy);
 298     }
 299 };
 300
 301
 302 }} // namespace detail::overlay
 303 #endif // DOXYGEN_NO_DETAIL
 304
 305
 306 #ifndef DOXYGEN_NO_DISPATCH
 307 namespace detail_dispatch { namespace overlay
 308 {
 309
 310 // dispatch struct for pointlike-linear difference/intersection computation
 311 template
 312 <
 313     typename PointLike,
 314     typename Linear,
 315     typename PointOut,
 316     overlay_type OverlayType,
 317     typename Tag1,
 318     typename Tag2
 319 >
 320 struct pointlike_linear_point
 321     : not_implemented<PointLike, Linear, PointOut>
 322 {};
 323
 324
 325 template
 326 <
 327     typename Point,
 328     typename Linear,
 329     typename PointOut,
 330     overlay_type OverlayType
 331 >
 332 struct pointlike_linear_point
 333     <
 334         Point, Linear, PointOut, OverlayType, point_tag, linear_tag
 335     > : detail::overlay::point_single_point
 336         <
 337             Point, Linear, PointOut, OverlayType,
 338             detail::not_<detail::disjoint::reverse_covered_by>
 339         >
 340 {};
 341
 342
 343 template
 344 <
 345     typename Point,
 346     typename Segment,
 347     typename PointOut,
 348     overlay_type OverlayType
 349 >
 350 struct pointlike_linear_point
 351     <
 352         Point, Segment, PointOut, OverlayType, point_tag, segment_tag
 353     > : detail::overlay::point_single_point
 354         <
 355             Point, Segment, PointOut, OverlayType,
 356             detail::not_<detail::disjoint::reverse_covered_by>
 357         >
 358 {};
 359
 360
 361 template
 362 <
 363     typename MultiPoint,
 364     typename Linear,
 365     typename PointOut,
 366     overlay_type OverlayType
 367 >
 368 struct pointlike_linear_point
 369     <
 370         MultiPoint, Linear, PointOut, OverlayType, multi_point_tag, linear_tag
 371     > : detail::overlay::multipoint_linear_point
 372         <
 373             MultiPoint, Linear, PointOut, OverlayType,
 374             detail::not_<detail::disjoint::reverse_covered_by>
 375         >
 376 {};
 377
 378
 379 template
 380 <
 381     typename MultiPoint,
 382     typename Segment,
 383     typename PointOut,
 384     overlay_type OverlayType
 385 >
 386 struct pointlike_linear_point
 387     <
 388         MultiPoint, Segment, PointOut, OverlayType, multi_point_tag, segment_tag
 389     > : detail::overlay::multipoint_single_point
 390         <
 391             MultiPoint, Segment, PointOut, OverlayType,
 392             detail::not_<detail::disjoint::reverse_covered_by>
 393         >
 394 {};
 395
 396
 397 }} // namespace detail_dispatch::overlay
 398 #endif // DOXYGEN_NO_DISPATCH
 399
 400
 401 }} // namespace boost::geometry
 402
 403
 404 #endif // BOOST_GEOMETRY_ALGORITHMS_DETAIL_OVERLAY_POINTLIKE_LINEAR_HPP