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

   1 // Boost.Geometry (aka GGL, Generic Geometry Library)
   2
   3 // Copyright (c) 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_LINEAR_HPP
  12 #define BOOST_GEOMETRY_ALGORITHMS_DETAIL_OVERLAY_POINTLIKE_LINEAR_HPP
  13
  14 #include <iterator>
  15 #include <vector>
  16
  17 #include <boost/range.hpp>
  18
  19 #include <boost/geometry/core/tags.hpp>
  20
  21 #include <boost/geometry/geometries/box.hpp>
  22
  23 #include <boost/geometry/iterators/segment_iterator.hpp>
  24
  25 #include <boost/geometry/algorithms/disjoint.hpp>
  26 #include <boost/geometry/algorithms/envelope.hpp>
  27 #include <boost/geometry/algorithms/expand.hpp>
  28 #include <boost/geometry/algorithms/not_implemented.hpp>
  29
  30 #include <boost/geometry/algorithms/detail/not.hpp>
  31 #include <boost/geometry/algorithms/detail/partition.hpp>
  32 #include <boost/geometry/algorithms/detail/relate/less.hpp>
  33 #include <boost/geometry/algorithms/detail/disjoint/point_geometry.hpp>
  34 #include <boost/geometry/algorithms/detail/equals/point_point.hpp>
  35 #include <boost/geometry/algorithms/detail/overlay/overlay_type.hpp>
  36 #include <boost/geometry/algorithms/detail/overlay/pointlike_pointlike.hpp>
  37
  38
  39 namespace boost { namespace geometry
  40 {
  41
  42
  43 #ifndef DOXYGEN_NO_DETAIL
  44 namespace detail { namespace overlay
  45 {
  46
  47
  48 // action struct for pointlike-linear difference/intersection
  49 // it works the same as its pointlike-pointlike counterpart, hence the
  50 // derivation
  51 template <typename PointOut, overlay_type OverlayType>
  52 struct action_selector_pl_l
  53     : action_selector_pl_pl<PointOut, OverlayType>
  54 {};
  55
  56 // difference/intersection of point-linear
  57 template
  58 <
  59     typename Point,
  60     typename Linear,
  61     typename PointOut,
  62     overlay_type OverlayType,
  63     typename Policy
  64 >
  65 struct point_linear_point
  66 {
  67     template <typename RobustPolicy, typename OutputIterator, typename Strategy>
  68     static inline OutputIterator apply(Point const& point,
  69                                        Linear const& linear,
  70                                        RobustPolicy const&,
  71                                        OutputIterator oit,
  72                                        Strategy const&)
  73     {
  74         action_selector_pl_l
  75             <
  76                 PointOut, OverlayType
  77             >::apply(point, Policy::apply(point, linear), oit);
  78         return oit;
  79     }
  80 };
  81
  82 // difference/intersection of multipoint-segment
  83 template
  84 <
  85     typename MultiPoint,
  86     typename Segment,
  87     typename PointOut,
  88     overlay_type OverlayType,
  89     typename Policy
  90 >
  91 struct multipoint_segment_point
  92 {
  93     template <typename RobustPolicy, typename OutputIterator, typename Strategy>
  94     static inline OutputIterator apply(MultiPoint const& multipoint,
  95                                        Segment const& segment,
  96                                        RobustPolicy const&,
  97                                        OutputIterator oit,
  98                                        Strategy const&)
  99     {
 100         for (typename boost::range_iterator<MultiPoint const>::type
 101                  it = boost::begin(multipoint);
 102              it != boost::end(multipoint);
 103              ++it)
 104         {
 105             action_selector_pl_l
 106                 <
 107                     PointOut, OverlayType
 108                 >::apply(*it, Policy::apply(*it, segment), oit);
 109         }
 110
 111         return oit;
 112     }
 113 };
 114
 115
 116 // difference/intersection of multipoint-linear
 117 template
 118 <
 119     typename MultiPoint,
 120     typename Linear,
 121     typename PointOut,
 122     overlay_type OverlayType,
 123     typename Policy
 124 >
 125 class multipoint_linear_point
 126 {
 127 private:
 128     // structs for partition -- start
 129     struct expand_box
 130     {
 131         template <typename Box, typename Geometry>
 132         static inline void apply(Box& total, Geometry const& geometry)
 133         {
 134             geometry::expand(total, geometry::return_envelope<Box>(geometry));
 135         }
 136
 137     };
 138
 139     struct overlaps_box
 140     {
 141         template <typename Box, typename Geometry>
 142         static inline bool apply(Box const& box, Geometry const& geometry)
 143         {
 144             return ! geometry::disjoint(geometry, box);
 145         }
 146     };
 147
 148     template <typename OutputIterator>
 149     class item_visitor_type
 150     {
 151     public:
 152         item_visitor_type(OutputIterator& oit) : m_oit(oit) {}
 153
 154         template <typename Item1, typename Item2>
 155         inline void apply(Item1 const& item1, Item2 const& item2)
 156         {
 157             action_selector_pl_l
 158                 <
 159                     PointOut, overlay_intersection
 160                 >::apply(item1, Policy::apply(item1, item2), m_oit);
 161         }
 162
 163     private:
 164         OutputIterator& m_oit;
 165     };
 166     // structs for partition -- end
 167
 168     class segment_range
 169     {
 170     public:
 171         typedef geometry::segment_iterator<Linear const> const_iterator;
 172         typedef const_iterator iterator;
 173
 174         segment_range(Linear const& linear)
 175             : m_linear(linear)
 176         {}
 177
 178         const_iterator begin() const
 179         {
 180             return geometry::segments_begin(m_linear);
 181         }
 182
 183         const_iterator end() const
 184         {
 185             return geometry::segments_end(m_linear);
 186         }
 187
 188     private:
 189         Linear const& m_linear;
 190     };
 191
 192     template <typename OutputIterator>
 193     static inline OutputIterator get_common_points(MultiPoint const& multipoint,
 194                                                    Linear const& linear,
 195                                                    OutputIterator oit)
 196     {
 197         item_visitor_type<OutputIterator> item_visitor(oit);
 198
 199         segment_range rng(linear);
 200
 201         geometry::partition
 202             <
 203                 geometry::model::box
 204                     <
 205                         typename boost::range_value<MultiPoint>::type
 206                     >,
 207                 expand_box,
 208                 overlaps_box
 209             >::apply(multipoint, rng, item_visitor);
 210
 211         return oit;
 212     }
 213
 214 public:
 215     template <typename RobustPolicy, typename OutputIterator, typename Strategy>
 216     static inline OutputIterator apply(MultiPoint const& multipoint,
 217                                        Linear const& linear,
 218                                        RobustPolicy const& robust_policy,
 219                                        OutputIterator oit,
 220                                        Strategy const& strategy)
 221     {
 222         typedef std::vector
 223             <
 224                 typename boost::range_value<MultiPoint>::type
 225             > point_vector_type;
 226
 227         point_vector_type common_points;
 228
 229         // compute the common points
 230         get_common_points(multipoint, linear,
 231                           std::back_inserter(common_points));
 232
 233         return multipoint_multipoint_point
 234             <
 235                 MultiPoint, point_vector_type, PointOut, OverlayType
 236             >::apply(multipoint, common_points, robust_policy, oit, strategy);
 237     }
 238 };
 239
 240
 241 }} // namespace detail::overlay
 242 #endif // DOXYGEN_NO_DETAIL
 243
 244
 245 #ifndef DOXYGEN_NO_DISPATCH
 246 namespace detail_dispatch { namespace overlay
 247 {
 248
 249 // dispatch struct for pointlike-linear difference/intersection computation
 250 template
 251 <
 252     typename PointLike,
 253     typename Linear,
 254     typename PointOut,
 255     overlay_type OverlayType,
 256     typename Tag1,
 257     typename Tag2
 258 >
 259 struct pointlike_linear_point
 260     : not_implemented<PointLike, Linear, PointOut>
 261 {};
 262
 263
 264 template
 265 <
 266     typename Point,
 267     typename Linear,
 268     typename PointOut,
 269     overlay_type OverlayType
 270 >
 271 struct pointlike_linear_point
 272     <
 273         Point, Linear, PointOut, OverlayType, point_tag, linear_tag
 274     > : detail::overlay::point_linear_point
 275         <
 276             Point, Linear, PointOut, OverlayType,
 277             detail::not_<detail::disjoint::reverse_covered_by>
 278         >
 279 {};
 280
 281
 282 template
 283 <
 284     typename Point,
 285     typename Segment,
 286     typename PointOut,
 287     overlay_type OverlayType
 288 >
 289 struct pointlike_linear_point
 290     <
 291         Point, Segment, PointOut, OverlayType, point_tag, segment_tag
 292     > : detail::overlay::point_linear_point
 293         <
 294             Point, Segment, PointOut, OverlayType,
 295             detail::not_<detail::disjoint::reverse_covered_by>
 296         >
 297 {};
 298
 299
 300 template
 301 <
 302     typename MultiPoint,
 303     typename Linear,
 304     typename PointOut,
 305     overlay_type OverlayType
 306 >
 307 struct pointlike_linear_point
 308     <
 309         MultiPoint, Linear, PointOut, OverlayType, multi_point_tag, linear_tag
 310     > : detail::overlay::multipoint_linear_point
 311         <
 312             MultiPoint, Linear, PointOut, OverlayType,
 313             detail::not_<detail::disjoint::reverse_covered_by>
 314         >
 315 {};
 316
 317
 318 template
 319 <
 320     typename MultiPoint,
 321     typename Segment,
 322     typename PointOut,
 323     overlay_type OverlayType
 324 >
 325 struct pointlike_linear_point
 326     <
 327         MultiPoint, Segment, PointOut, OverlayType, multi_point_tag, segment_tag
 328     > : detail::overlay::multipoint_segment_point
 329         <
 330             MultiPoint, Segment, PointOut, OverlayType,
 331             detail::not_<detail::disjoint::reverse_covered_by>
 332         >
 333 {};
 334
 335
 336 }} // namespace detail_dispatch::overlay
 337 #endif // DOXYGEN_NO_DISPATCH
 338
 339
 340 }} // namespace boost::geometry
 341
 342
 343 #endif // BOOST_GEOMETRY_ALGORITHMS_DETAIL_OVERLAY_POINTLIKE_LINEAR_HPP