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