diff options
Diffstat (limited to 'boost/geometry/algorithms/detail/disjoint')
4 files changed, 289 insertions, 65 deletions
diff --git a/boost/geometry/algorithms/detail/disjoint/interface.hpp b/boost/geometry/algorithms/detail/disjoint/interface.hpp index 96d6881296..18c010731e 100644 --- a/boost/geometry/algorithms/detail/disjoint/interface.hpp +++ b/boost/geometry/algorithms/detail/disjoint/interface.hpp @@ -175,7 +175,7 @@ struct disjoint< */ template <typename Geometry1, typename Geometry2> inline bool disjoint(Geometry1 const& geometry1, - Geometry2 const& geometry2) + Geometry2 const& geometry2) { return resolve_variant::disjoint<Geometry1, Geometry2>::apply(geometry1, geometry2); } 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 diff --git a/boost/geometry/algorithms/detail/disjoint/point_geometry.hpp b/boost/geometry/algorithms/detail/disjoint/point_geometry.hpp index a58bff41da..9ae43f73d0 100644 --- a/boost/geometry/algorithms/detail/disjoint/point_geometry.hpp +++ b/boost/geometry/algorithms/detail/disjoint/point_geometry.hpp @@ -1,12 +1,12 @@ // Boost.Geometry (aka GGL, Generic Geometry Library) -// Copyright (c) 2007-2014 Barend Gehrels, Amsterdam, the Netherlands. -// Copyright (c) 2008-2014 Bruno Lalande, Paris, France. -// Copyright (c) 2009-2014 Mateusz Loskot, London, UK. -// Copyright (c) 2013-2014 Adam Wulkiewicz, Lodz, Poland. +// Copyright (c) 2007-2015 Barend Gehrels, Amsterdam, the Netherlands. +// Copyright (c) 2008-2015 Bruno Lalande, Paris, France. +// Copyright (c) 2009-2015 Mateusz Loskot, London, UK. +// Copyright (c) 2013-2015 Adam Wulkiewicz, Lodz, Poland. -// This file was modified by Oracle on 2013-2014. -// Modifications copyright (c) 2013-2014, Oracle and/or its affiliates. +// This file was modified by Oracle on 2013, 2014, 2015. +// Modifications copyright (c) 2013-2015, Oracle and/or its affiliates. // Contributed and/or modified by Adam Wulkiewicz, on behalf of Oracle // Contributed and/or modified by Menelaos Karavelas, on behalf of Oracle @@ -21,8 +21,6 @@ #ifndef BOOST_GEOMETRY_ALGORITHMS_DETAIL_DISJOINT_POINT_GEOMETRY_HPP #define BOOST_GEOMETRY_ALGORITHMS_DETAIL_DISJOINT_POINT_GEOMETRY_HPP -#include <boost/geometry/geometries/segment.hpp> - #include <boost/geometry/algorithms/covered_by.hpp> #include <boost/geometry/algorithms/detail/disjoint/linear_linear.hpp> @@ -39,24 +37,13 @@ namespace detail { namespace disjoint { -template<typename Point, typename Geometry> -struct disjoint_point_linear -{ - static inline - bool apply(Point const& pt, Geometry const& g) - { - return !geometry::covered_by(pt, g); - } -}; - - -template <typename Geometry1, typename Geometry2> struct reverse_covered_by { + template <typename Geometry1, typename Geometry2> static inline bool apply(Geometry1 const& geometry1, Geometry2 const& geometry2) { - return !geometry::covered_by(geometry1, geometry2); + return ! geometry::covered_by(geometry1, geometry2); } }; @@ -74,30 +61,20 @@ namespace dispatch template<typename Point, typename Linear, std::size_t DimensionCount> struct disjoint<Point, Linear, DimensionCount, point_tag, linear_tag, false> - : public detail::disjoint::disjoint_point_linear<Point, Linear> + : detail::disjoint::reverse_covered_by {}; template <typename Point, typename Areal, std::size_t DimensionCount> struct disjoint<Point, Areal, DimensionCount, point_tag, areal_tag, false> - : detail::disjoint::reverse_covered_by<Point, Areal> + : detail::disjoint::reverse_covered_by {}; template<typename Point, typename Segment, std::size_t DimensionCount> struct disjoint<Point, Segment, DimensionCount, point_tag, segment_tag, false> -{ - static inline bool apply(Point const& point, Segment const& segment) - { - typedef geometry::model::referring_segment<Point const> other_segment; - - other_segment other(point, point); - return detail::disjoint::disjoint_segment - < - Segment, other_segment - >::apply(segment, other); - } -}; + : detail::disjoint::reverse_covered_by +{}; } // namespace dispatch diff --git a/boost/geometry/algorithms/detail/disjoint/point_point.hpp b/boost/geometry/algorithms/detail/disjoint/point_point.hpp index b1d32bf95e..7580b7287b 100644 --- a/boost/geometry/algorithms/detail/disjoint/point_point.hpp +++ b/boost/geometry/algorithms/detail/disjoint/point_point.hpp @@ -1,12 +1,12 @@ // Boost.Geometry (aka GGL, Generic Geometry Library) -// Copyright (c) 2007-2014 Barend Gehrels, Amsterdam, the Netherlands. -// Copyright (c) 2008-2014 Bruno Lalande, Paris, France. -// Copyright (c) 2009-2014 Mateusz Loskot, London, UK. -// Copyright (c) 2013-2014 Adam Wulkiewicz, Lodz, Poland +// Copyright (c) 2007-2015 Barend Gehrels, Amsterdam, the Netherlands. +// Copyright (c) 2008-2015 Bruno Lalande, Paris, France. +// Copyright (c) 2009-2015 Mateusz Loskot, London, UK. +// Copyright (c) 2013-2015 Adam Wulkiewicz, Lodz, Poland -// This file was modified by Oracle on 2013-2014. -// Modifications copyright (c) 2013-2014, Oracle and/or its affiliates. +// This file was modified by Oracle on 2013, 2014, 2015. +// Modifications copyright (c) 2013-2015, Oracle and/or its affiliates. // Contributed and/or modified by Adam Wulkiewicz, on behalf of Oracle // Contributed and/or modified by Menelaos Karavelas, on behalf of Oracle @@ -23,11 +23,26 @@ #include <cstddef> +#include <boost/type_traits/is_same.hpp> + #include <boost/geometry/core/access.hpp> +#include <boost/geometry/core/radian_access.hpp> #include <boost/geometry/core/coordinate_dimension.hpp> +#include <boost/geometry/core/coordinate_system.hpp> +#include <boost/geometry/core/coordinate_type.hpp> +#include <boost/geometry/core/cs.hpp> #include <boost/geometry/core/tags.hpp> #include <boost/geometry/util/math.hpp> +#include <boost/geometry/util/select_most_precise.hpp> + +#include <boost/geometry/strategies/strategy_transform.hpp> + +#include <boost/geometry/geometries/helper_geometry.hpp> + +#include <boost/geometry/algorithms/transform.hpp> + +#include <boost/geometry/algorithms/detail/normalize.hpp> #include <boost/geometry/algorithms/dispatch/disjoint.hpp> @@ -40,38 +55,146 @@ namespace boost { namespace geometry namespace detail { namespace disjoint { -template -< - typename Point1, typename Point2, - std::size_t Dimension, std::size_t DimensionCount -> -struct point_point + +template <std::size_t Dimension, std::size_t DimensionCount> +struct point_point_generic { + template <typename Point1, typename Point2> static inline bool apply(Point1 const& p1, Point2 const& p2) { if (! geometry::math::equals(get<Dimension>(p1), get<Dimension>(p2))) { return true; } - return point_point - < - Point1, Point2, - Dimension + 1, DimensionCount - >::apply(p1, p2); + return + point_point_generic<Dimension + 1, DimensionCount>::apply(p1, p2); } }; - -template <typename Point1, typename Point2, std::size_t DimensionCount> -struct point_point<Point1, Point2, DimensionCount, DimensionCount> +template <std::size_t DimensionCount> +struct point_point_generic<DimensionCount, DimensionCount> { - static inline bool apply(Point1 const& , Point2 const& ) + template <typename Point1, typename Point2> + static inline bool apply(Point1 const&, Point2 const&) { return false; } }; +class point_point_on_spheroid +{ +private: + template <typename Point1, typename Point2, bool SameUnits> + struct are_same_points + { + static inline bool apply(Point1 const& point1, Point2 const& point2) + { + typedef typename helper_geometry<Point1>::type helper_point_type1; + typedef typename helper_geometry<Point2>::type helper_point_type2; + + helper_point_type1 point1_normalized + = return_normalized<helper_point_type1>(point1); + helper_point_type2 point2_normalized + = return_normalized<helper_point_type2>(point2); + + return point_point_generic + < + 0, dimension<Point1>::value + >::apply(point1_normalized, point2_normalized); + } + }; + + template <typename Point1, typename Point2> + struct are_same_points<Point1, Point2, false> // points have different units + { + static inline bool apply(Point1 const& point1, Point2 const& point2) + { + typedef typename geometry::select_most_precise + < + typename fp_coordinate_type<Point1>::type, + typename fp_coordinate_type<Point2>::type + >::type calculation_type; + + typename helper_geometry + < + Point1, calculation_type, radian + >::type helper_point1, helper_point2; + + Point1 point1_normalized = return_normalized<Point1>(point1); + Point2 point2_normalized = return_normalized<Point2>(point2); + + geometry::transform(point1_normalized, helper_point1); + geometry::transform(point2_normalized, helper_point2); + + return point_point_generic + < + 0, dimension<Point1>::value + >::apply(helper_point1, helper_point2); + } + }; + +public: + template <typename Point1, typename Point2> + static inline bool apply(Point1 const& point1, Point2 const& point2) + { + return are_same_points + < + Point1, + Point2, + boost::is_same + < + typename coordinate_system<Point1>::type::units, + typename coordinate_system<Point2>::type::units + >::value + >::apply(point1, point2); + } +}; + + +template +< + typename Point1, typename Point2, + std::size_t Dimension, std::size_t DimensionCount, + typename CSTag1 = typename cs_tag<Point1>::type, + typename CSTag2 = CSTag1 +> +struct point_point + : point_point<Point1, Point2, Dimension, DimensionCount, cartesian_tag> +{}; + +template +< + typename Point1, typename Point2, + std::size_t Dimension, std::size_t DimensionCount +> +struct point_point + < + Point1, Point2, Dimension, DimensionCount, spherical_equatorial_tag + > : point_point_on_spheroid +{}; + +template +< + typename Point1, typename Point2, + std::size_t Dimension, std::size_t DimensionCount +> +struct point_point + < + Point1, Point2, Dimension, DimensionCount, geographic_tag + > : point_point_on_spheroid +{}; + +template +< + typename Point1, typename Point2, + std::size_t Dimension, std::size_t DimensionCount +> +struct point_point<Point1, Point2, Dimension, DimensionCount, cartesian_tag> + : point_point_generic<Dimension, DimensionCount> +{}; + + /*! \brief Internal utility function to detect of points are disjoint \note To avoid circular references |