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