diff options
Diffstat (limited to 'boost/geometry/algorithms/detail/disjoint/multipoint_geometry.hpp')
| -rw-r--r-- | boost/geometry/algorithms/detail/disjoint/multipoint_geometry.hpp | 140 |
1 files changed, 132 insertions, 8 deletions
diff --git a/boost/geometry/algorithms/detail/disjoint/multipoint_geometry.hpp b/boost/geometry/algorithms/detail/disjoint/multipoint_geometry.hpp index 7d1bb05242..29e438e546 100644 --- a/boost/geometry/algorithms/detail/disjoint/multipoint_geometry.hpp +++ b/boost/geometry/algorithms/detail/disjoint/multipoint_geometry.hpp @@ -1,6 +1,6 @@ // Boost.Geometry (aka GGL, Generic Geometry Library) -// Copyright (c) 2014, Oracle and/or its affiliates. +// Copyright (c) 2014-2015, Oracle and/or its affiliates. // Contributed and/or modified by Menelaos Karavelas, on behalf of Oracle @@ -13,10 +13,20 @@ #include <algorithm> #include <vector> -#include <boost/assert.hpp> #include <boost/range.hpp> +#include <boost/geometry/core/assert.hpp> +#include <boost/geometry/core/tags.hpp> + +#include <boost/geometry/geometries/box.hpp> + +#include <boost/geometry/iterators/segment_iterator.hpp> + +#include <boost/geometry/algorithms/envelope.hpp> +#include <boost/geometry/algorithms/expand.hpp> + #include <boost/geometry/algorithms/detail/check_iterator_range.hpp> +#include <boost/geometry/algorithms/detail/partition.hpp> #include <boost/geometry/algorithms/detail/disjoint/multirange_geometry.hpp> #include <boost/geometry/algorithms/detail/disjoint/point_point.hpp> #include <boost/geometry/algorithms/detail/disjoint/point_geometry.hpp> @@ -33,7 +43,8 @@ namespace boost { namespace geometry namespace detail { namespace disjoint { -template<typename MultiPoint1, typename MultiPoint2> + +template <typename MultiPoint1, typename MultiPoint2> class multipoint_multipoint { private: @@ -66,7 +77,7 @@ public: static inline bool apply(MultiPoint1 const& multipoint1, MultiPoint2 const& multipoint2) { - BOOST_ASSERT( boost::size(multipoint1) <= boost::size(multipoint2) ); + BOOST_GEOMETRY_ASSERT( boost::size(multipoint1) <= boost::size(multipoint2) ); typedef typename boost::range_value<MultiPoint1>::type point1_type; @@ -90,6 +101,98 @@ public: }; +template <typename MultiPoint, typename Linear> +class multipoint_linear +{ +private: + // structs for partition -- start + struct expand_box + { + template <typename Box, typename Geometry> + static inline void apply(Box& total, Geometry const& geometry) + { + geometry::expand(total, geometry::return_envelope<Box>(geometry)); + } + + }; + + struct overlaps_box + { + template <typename Box, typename Geometry> + static inline bool apply(Box const& box, Geometry const& geometry) + { + return ! dispatch::disjoint<Geometry, Box>::apply(geometry, box); + } + }; + + class item_visitor_type + { + public: + item_visitor_type() : m_intersection_found(false) {} + + template <typename Item1, typename Item2> + inline void apply(Item1 const& item1, Item2 const& item2) + { + if (! m_intersection_found + && ! dispatch::disjoint<Item1, Item2>::apply(item1, item2)) + { + m_intersection_found = true; + } + } + + inline bool intersection_found() const { return m_intersection_found; } + + private: + bool m_intersection_found; + }; + // structs for partition -- end + + class segment_range + { + public: + typedef geometry::segment_iterator<Linear const> const_iterator; + typedef const_iterator iterator; + + segment_range(Linear const& linear) + : m_linear(linear) + {} + + const_iterator begin() const + { + return geometry::segments_begin(m_linear); + } + + const_iterator end() const + { + return geometry::segments_end(m_linear); + } + + private: + Linear const& m_linear; + }; + +public: + static inline bool apply(MultiPoint const& multipoint, Linear const& linear) + { + item_visitor_type visitor; + + geometry::partition + < + geometry::model::box<typename point_type<MultiPoint>::type>, + expand_box, + overlaps_box + >::apply(multipoint, segment_range(linear), visitor); + + return ! visitor.intersection_found(); + } + + static inline bool apply(Linear const& linear, MultiPoint const& multipoint) + { + return apply(multipoint, linear); + } +}; + + }} // namespace detail::disjoint #endif // DOXYGEN_NO_DETAIL @@ -101,7 +204,7 @@ namespace dispatch { -template<typename Point, typename MultiPoint, std::size_t DimensionCount> +template <typename Point, typename MultiPoint, std::size_t DimensionCount> struct disjoint < Point, MultiPoint, DimensionCount, point_tag, multi_point_tag, false @@ -109,7 +212,7 @@ struct disjoint {}; -template<typename MultiPoint, typename Segment, std::size_t DimensionCount> +template <typename MultiPoint, typename Segment, std::size_t DimensionCount> struct disjoint < MultiPoint, Segment, DimensionCount, multi_point_tag, segment_tag, false @@ -117,7 +220,7 @@ struct disjoint {}; -template<typename MultiPoint, typename Box, std::size_t DimensionCount> +template <typename MultiPoint, typename Box, std::size_t DimensionCount> struct disjoint < MultiPoint, Box, DimensionCount, multi_point_tag, box_tag, false @@ -125,7 +228,12 @@ struct disjoint {}; -template<typename MultiPoint1, typename MultiPoint2, std::size_t DimensionCount> +template +< + typename MultiPoint1, + typename MultiPoint2, + std::size_t DimensionCount +> struct disjoint < MultiPoint1, MultiPoint2, DimensionCount, @@ -151,6 +259,22 @@ struct disjoint }; +template <typename Linear, typename MultiPoint, std::size_t DimensionCount> +struct disjoint + < + Linear, MultiPoint, DimensionCount, linear_tag, multi_point_tag, false + > : detail::disjoint::multipoint_linear<MultiPoint, Linear> +{}; + + +template <typename MultiPoint, typename Linear, std::size_t DimensionCount> +struct disjoint + < + MultiPoint, Linear, DimensionCount, multi_point_tag, linear_tag, false + > : detail::disjoint::multipoint_linear<MultiPoint, Linear> +{}; + + } // namespace dispatch #endif // DOXYGEN_NO_DISPATCH |