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> applyboost::geometry::detail::overlay::point_linear_point68 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> applyboost::geometry::detail::overlay::multipoint_segment_point94 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> applyboost::geometry::detail::overlay::multipoint_linear_point::expand_box132 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> applyboost::geometry::detail::overlay::multipoint_linear_point::overlaps_box142 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: item_visitor_type(OutputIterator & oit)152 item_visitor_type(OutputIterator& oit) : m_oit(oit) {} 153 154 template <typename Item1, typename Item2> apply(Item1 const & item1,Item2 const & 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 segment_range(Linear const & linear)174 segment_range(Linear const& linear) 175 : m_linear(linear) 176 {} 177 begin() const178 const_iterator begin() const 179 { 180 return geometry::segments_begin(m_linear); 181 } 182 end() const183 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> get_common_points(MultiPoint const & multipoint,Linear const & linear,OutputIterator oit)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> apply(MultiPoint const & multipoint,Linear const & linear,RobustPolicy const & robust_policy,OutputIterator oit,Strategy const & 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 344