ceph/src/boost/libs/geometry/include/boost/geometry/algorithms/detail/disjoint/multipoint_geometry.hpp

   1 // Boost.Geometry (aka GGL, Generic Geometry Library)
   2
   3 // Copyright (c) 2014-2015, Oracle and/or its affiliates.
   4
   5 // Contributed and/or modified by Menelaos Karavelas, on behalf of Oracle
   6
   7 // Licensed under the Boost Software License version 1.0.
   8 // http://www.boost.org/users/license.html
   9
  10 #ifndef BOOST_GEOMETRY_ALGORITHMS_DETAIL_DISJOINT_MULTIPOINT_GEOMETRY_HPP
  11 #define BOOST_GEOMETRY_ALGORITHMS_DETAIL_DISJOINT_MULTIPOINT_GEOMETRY_HPP
  12
  13 #include <algorithm>
  14 #include <vector>
  15
  16 #include <boost/range.hpp>
  17
  18 #include <boost/geometry/core/assert.hpp>
  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/envelope.hpp>
  26 #include <boost/geometry/algorithms/expand.hpp>
  27
  28 #include <boost/geometry/algorithms/detail/check_iterator_range.hpp>
  29 #include <boost/geometry/algorithms/detail/partition.hpp>
  30 #include <boost/geometry/algorithms/detail/disjoint/multirange_geometry.hpp>
  31 #include <boost/geometry/algorithms/detail/disjoint/point_point.hpp>
  32 #include <boost/geometry/algorithms/detail/disjoint/point_geometry.hpp>
  33 #include <boost/geometry/algorithms/detail/relate/less.hpp>
  34
  35 #include <boost/geometry/algorithms/dispatch/disjoint.hpp>
  36
  37
  38 namespace boost { namespace geometry
  39 {
  40
  41
  42 #ifndef DOXYGEN_NO_DETAIL
  43 namespace detail { namespace disjoint
  44 {
  45
  46
  47 template <typename MultiPoint1, typename MultiPoint2>
  48 class multipoint_multipoint
  49 {
  50 private:
  51     template <typename Iterator>
  52     class unary_disjoint_predicate
  53         : detail::relate::less
  54     {
  55     private:
  56         typedef detail::relate::less base_type;
  57
  58     public:
  59         unary_disjoint_predicate(Iterator first, Iterator last)
  60             : base_type(), m_first(first), m_last(last)
  61         {}
  62
  63         template <typename Point>
  64         inline bool apply(Point const& point) const
  65         {
  66             return !std::binary_search(m_first,
  67                                        m_last,
  68                                        point,
  69                                        static_cast<base_type const&>(*this));
  70         }
  71
  72     private:
  73         Iterator m_first, m_last;
  74     };
  75
  76 public:
  77     static inline bool apply(MultiPoint1 const& multipoint1,
  78                              MultiPoint2 const& multipoint2)
  79     {
  80         BOOST_GEOMETRY_ASSERT( boost::size(multipoint1) <= boost::size(multipoint2) );
  81
  82         typedef typename boost::range_value<MultiPoint1>::type point1_type;
  83
  84         std::vector<point1_type> points1(boost::begin(multipoint1),
  85                                          boost::end(multipoint1));
  86
  87         std::sort(points1.begin(), points1.end(), detail::relate::less());
  88
  89         typedef unary_disjoint_predicate
  90             <
  91                 typename std::vector<point1_type>::const_iterator
  92             > predicate_type;
  93
  94         return check_iterator_range
  95             <
  96                 predicate_type
  97             >::apply(boost::begin(multipoint2),
  98                      boost::end(multipoint2),
  99                      predicate_type(points1.begin(), points1.end()));
 100     }
 101 };
 102
 103
 104 template <typename MultiPoint, typename Linear>
 105 class multipoint_linear
 106 {
 107 private:
 108     // structs for partition -- start
 109     struct expand_box
 110     {
 111         template <typename Box, typename Geometry>
 112         static inline void apply(Box& total, Geometry const& geometry)
 113         {
 114             geometry::expand(total, geometry::return_envelope<Box>(geometry));
 115         }
 116
 117     };
 118
 119     struct overlaps_box
 120     {
 121         template <typename Box, typename Geometry>
 122         static inline bool apply(Box const& box, Geometry const& geometry)
 123         {
 124             return ! dispatch::disjoint<Geometry, Box>::apply(geometry, box);
 125         }
 126     };
 127
 128     class item_visitor_type
 129     {
 130     public:
 131         item_visitor_type() : m_intersection_found(false) {}
 132
 133         template <typename Item1, typename Item2>
 134         inline void apply(Item1 const& item1, Item2 const& item2)
 135         {
 136             if (! m_intersection_found
 137                 && ! dispatch::disjoint<Item1, Item2>::apply(item1, item2))
 138             {
 139                 m_intersection_found = true;
 140             }
 141         }
 142
 143         inline bool intersection_found() const { return m_intersection_found; }
 144
 145     private:
 146         bool m_intersection_found;
 147     };
 148     // structs for partition -- end
 149
 150     class segment_range
 151     {
 152     public:
 153         typedef geometry::segment_iterator<Linear const> const_iterator;
 154         typedef const_iterator iterator;
 155
 156         segment_range(Linear const& linear)
 157             : m_linear(linear)
 158         {}
 159
 160         const_iterator begin() const
 161         {
 162             return geometry::segments_begin(m_linear);
 163         }
 164
 165         const_iterator end() const
 166         {
 167             return geometry::segments_end(m_linear);
 168         }
 169
 170     private:
 171         Linear const& m_linear;
 172     };
 173
 174 public:
 175     static inline bool apply(MultiPoint const& multipoint, Linear const& linear)
 176     {
 177         item_visitor_type visitor;
 178
 179         geometry::partition
 180             <
 181                 geometry::model::box<typename point_type<MultiPoint>::type>,
 182                 expand_box,
 183                 overlaps_box
 184             >::apply(multipoint, segment_range(linear), visitor);
 185
 186         return ! visitor.intersection_found();
 187     }
 188
 189     static inline bool apply(Linear const& linear, MultiPoint const& multipoint)
 190     {
 191         return apply(multipoint, linear);
 192     }
 193 };
 194
 195
 196 }} // namespace detail::disjoint
 197 #endif // DOXYGEN_NO_DETAIL
 198
 199
 200
 201
 202 #ifndef DOXYGEN_NO_DISPATCH
 203 namespace dispatch
 204 {
 205
 206
 207 template <typename Point, typename MultiPoint, std::size_t DimensionCount>
 208 struct disjoint
 209     <
 210         Point, MultiPoint, DimensionCount, point_tag, multi_point_tag, false
 211     > : detail::disjoint::multirange_constant_size_geometry<MultiPoint, Point>
 212 {};
 213
 214
 215 template <typename MultiPoint, typename Segment, std::size_t DimensionCount>
 216 struct disjoint
 217     <
 218         MultiPoint, Segment, DimensionCount, multi_point_tag, segment_tag, false
 219     > : detail::disjoint::multirange_constant_size_geometry<MultiPoint, Segment>
 220 {};
 221
 222
 223 template <typename MultiPoint, typename Box, std::size_t DimensionCount>
 224 struct disjoint
 225     <
 226         MultiPoint, Box, DimensionCount, multi_point_tag, box_tag, false
 227     > : detail::disjoint::multirange_constant_size_geometry<MultiPoint, Box>
 228 {};
 229
 230
 231 template
 232 <
 233     typename MultiPoint1,
 234     typename MultiPoint2,
 235     std::size_t DimensionCount
 236 >
 237 struct disjoint
 238     <
 239         MultiPoint1, MultiPoint2, DimensionCount,
 240         multi_point_tag, multi_point_tag, false
 241     >
 242 {
 243     static inline bool apply(MultiPoint1 const& multipoint1,
 244                              MultiPoint2 const& multipoint2)
 245     {
 246         if ( boost::size(multipoint2) < boost::size(multipoint1) )
 247         {
 248             return detail::disjoint::multipoint_multipoint
 249                 <
 250                     MultiPoint2, MultiPoint1
 251                 >::apply(multipoint2, multipoint1);
 252         }
 253
 254         return detail::disjoint::multipoint_multipoint
 255             <
 256                 MultiPoint1, MultiPoint2
 257             >::apply(multipoint1, multipoint2);
 258    }
 259 };
 260
 261
 262 template <typename Linear, typename MultiPoint, std::size_t DimensionCount>
 263 struct disjoint
 264     <
 265         Linear, MultiPoint, DimensionCount, linear_tag, multi_point_tag, false
 266     > : detail::disjoint::multipoint_linear<MultiPoint, Linear>
 267 {};
 268
 269
 270 template <typename MultiPoint, typename Linear, std::size_t DimensionCount>
 271 struct disjoint
 272     <
 273         MultiPoint, Linear, DimensionCount, multi_point_tag, linear_tag, false
 274     > : detail::disjoint::multipoint_linear<MultiPoint, Linear>
 275 {};
 276
 277
 278 } // namespace dispatch
 279 #endif // DOXYGEN_NO_DISPATCH
 280
 281
 282 }} // namespace boost::geometry
 283
 284
 285
 286 #endif // BOOST_GEOMETRY_ALGORITHMS_DETAIL_DISJOINT_MULTIPOINT_GEOMETRY_HPP