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