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: unary_disjoint_predicate(Iterator first,Iterator last)59 unary_disjoint_predicate(Iterator first, Iterator last) 60 : base_type(), m_first(first), m_last(last) 61 {} 62 63 template <typename Point> apply(Point const & point) const64 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: apply(MultiPoint1 const & multipoint1,MultiPoint2 const & multipoint2)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> applyboost::geometry::detail::disjoint::multipoint_linear::expand_box112 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> applyboost::geometry::detail::disjoint::multipoint_linear::overlaps_box122 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: item_visitor_type()131 item_visitor_type() : m_intersection_found(false) {} 132 133 template <typename Item1, typename Item2> apply(Item1 const & item1,Item2 const & 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 intersection_found() const143 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 segment_range(Linear const & linear)156 segment_range(Linear const& linear) 157 : m_linear(linear) 158 {} 159 begin() const160 const_iterator begin() const 161 { 162 return geometry::segments_begin(m_linear); 163 } 164 end() const165 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: apply(MultiPoint const & multipoint,Linear const & linear)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 apply(Linear const & linear,MultiPoint const & multipoint)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 { applyboost::geometry::dispatch::disjoint243 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 287