diff options
author | DongHun Kwak <dh0128.kwak@samsung.com> | 2017-09-13 11:08:07 +0900 |
---|---|---|
committer | DongHun Kwak <dh0128.kwak@samsung.com> | 2017-09-13 11:09:00 +0900 |
commit | b5c87084afaef42b2d058f68091be31988a6a874 (patch) | |
tree | adef9a65870a41181687e11d57fdf98e7629de3c /boost/geometry/algorithms/detail/disjoint | |
parent | 34bd32e225e2a8a94104489b31c42e5801cc1f4a (diff) | |
download | boost-b5c87084afaef42b2d058f68091be31988a6a874.tar.gz boost-b5c87084afaef42b2d058f68091be31988a6a874.tar.bz2 boost-b5c87084afaef42b2d058f68091be31988a6a874.zip |
Imported Upstream version 1.64.0upstream/1.64.0
Change-Id: Id9212edd016dd55f21172c427aa7894d1d24148b
Signed-off-by: DongHun Kwak <dh0128.kwak@samsung.com>
Diffstat (limited to 'boost/geometry/algorithms/detail/disjoint')
12 files changed, 391 insertions, 402 deletions
diff --git a/boost/geometry/algorithms/detail/disjoint/areal_areal.hpp b/boost/geometry/algorithms/detail/disjoint/areal_areal.hpp index 284858a130..664c995384 100644 --- a/boost/geometry/algorithms/detail/disjoint/areal_areal.hpp +++ b/boost/geometry/algorithms/detail/disjoint/areal_areal.hpp @@ -5,8 +5,8 @@ // Copyright (c) 2009-2014 Mateusz Loskot, London, UK. // Copyright (c) 2013-2014 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-2017. +// Modifications copyright (c) 2013-2017, 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 @@ -39,15 +39,45 @@ namespace detail { namespace disjoint { -template<typename Geometry> +template <typename Geometry, typename Tag = typename tag<Geometry>::type> +struct check_each_ring_for_within_call_covered_by +{ + /*! + \tparam Strategy point_in_geometry strategy + */ + template <typename Point, typename Strategy> + static inline bool apply(Point const& p, Geometry const& g, Strategy const& strategy) + { + return geometry::covered_by(p, g, strategy); + } +}; + +template <typename Geometry> +struct check_each_ring_for_within_call_covered_by<Geometry, box_tag> +{ + template <typename Point, typename Strategy> + static inline bool apply(Point const& p, Geometry const& g, Strategy const& ) + { + return geometry::covered_by(p, g); + } +}; + + +/*! +\tparam Strategy point_in_geometry strategy +*/ +template<typename Geometry, typename Strategy> struct check_each_ring_for_within { bool not_disjoint; Geometry const& m_geometry; + Strategy const& m_strategy; - inline check_each_ring_for_within(Geometry const& g) + inline check_each_ring_for_within(Geometry const& g, + Strategy const& strategy) : not_disjoint(false) , m_geometry(g) + , m_strategy(strategy) {} template <typename Range> @@ -56,17 +86,26 @@ struct check_each_ring_for_within typename point_type<Range>::type pt; not_disjoint = not_disjoint || ( geometry::point_on_border(pt, range) - && geometry::covered_by(pt, m_geometry) ); + && check_each_ring_for_within_call_covered_by + < + Geometry + >::apply(pt, m_geometry, m_strategy) ); } }; - -template <typename FirstGeometry, typename SecondGeometry> +/*! +\tparam Strategy point_in_geometry strategy +*/ +template <typename FirstGeometry, typename SecondGeometry, typename Strategy> inline bool rings_containing(FirstGeometry const& geometry1, - SecondGeometry const& geometry2) + SecondGeometry const& geometry2, + Strategy const& strategy) { - check_each_ring_for_within<FirstGeometry> checker(geometry1); + check_each_ring_for_within + < + FirstGeometry, Strategy + > checker(geometry1, strategy); geometry::detail::for_each_range(geometry2, checker); return checker.not_disjoint; } @@ -76,10 +115,15 @@ inline bool rings_containing(FirstGeometry const& geometry1, template <typename Geometry1, typename Geometry2> struct general_areal { - static inline - bool apply(Geometry1 const& geometry1, Geometry2 const& geometry2) + /*! + \tparam Strategy relate (segments intersection) strategy + */ + template <typename Strategy> + static inline bool apply(Geometry1 const& geometry1, + Geometry2 const& geometry2, + Strategy const& strategy) { - if ( ! disjoint_linear<Geometry1, Geometry2>::apply(geometry1, geometry2) ) + if ( ! disjoint_linear<Geometry1, Geometry2>::apply(geometry1, geometry2, strategy) ) { return false; } @@ -90,8 +134,10 @@ struct general_areal // We check that using a point on the border (external boundary), // and see if that is contained in the other geometry. And vice versa. - if ( rings_containing(geometry1, geometry2) - || rings_containing(geometry2, geometry1) ) + if ( rings_containing(geometry1, geometry2, + strategy.template get_point_in_geometry_strategy<Geometry2, Geometry1>()) + || rings_containing(geometry2, geometry1, + strategy.template get_point_in_geometry_strategy<Geometry1, Geometry2>()) ) { return false; } diff --git a/boost/geometry/algorithms/detail/disjoint/box_box.hpp b/boost/geometry/algorithms/detail/disjoint/box_box.hpp index 3b81755e20..f830f8161c 100644 --- a/boost/geometry/algorithms/detail/disjoint/box_box.hpp +++ b/boost/geometry/algorithms/detail/disjoint/box_box.hpp @@ -5,8 +5,8 @@ // Copyright (c) 2009-2015 Mateusz Loskot, London, UK. // Copyright (c) 2013-2015 Adam Wulkiewicz, Lodz, Poland. -// This file was modified by Oracle on 2013-2016. -// Modifications copyright (c) 2013-2016, Oracle and/or its affiliates. +// This file was modified by Oracle on 2013-2017. +// Modifications copyright (c) 2013-2017, 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 @@ -52,6 +52,12 @@ template > struct box_box { + template <typename Strategy> + static inline bool apply(Box1 const& box1, Box2 const& box2, Strategy const&) + { + return apply(box1, box2); + } + static inline bool apply(Box1 const& box1, Box2 const& box2) { if (get<max_corner, Dimension>(box1) < get<min_corner, Dimension>(box2)) @@ -84,6 +90,12 @@ struct box_box<Box1, Box2, DimensionCount, DimensionCount, CSTag> template <typename Box1, typename Box2, std::size_t DimensionCount> struct box_box<Box1, Box2, 0, DimensionCount, spherical_tag> { + template <typename Strategy> + static inline bool apply(Box1 const& box1, Box2 const& box2, Strategy const&) + { + return apply(box1, box2); + } + static inline bool apply(Box1 const& box1, Box2 const& box2) { typedef typename geometry::select_most_precise diff --git a/boost/geometry/algorithms/detail/disjoint/interface.hpp b/boost/geometry/algorithms/detail/disjoint/interface.hpp index ce7fe6d45c..64898e35fe 100644 --- a/boost/geometry/algorithms/detail/disjoint/interface.hpp +++ b/boost/geometry/algorithms/detail/disjoint/interface.hpp @@ -5,8 +5,8 @@ // Copyright (c) 2009-2014 Mateusz Loskot, London, UK. // Copyright (c) 2013-2014 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-2017. +// Modifications copyright (c) 2013-2017, 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 @@ -27,43 +27,51 @@ #include <boost/variant/static_visitor.hpp> #include <boost/variant/variant_fwd.hpp> +#include <boost/geometry/algorithms/detail/relate/interface.hpp> +#include <boost/geometry/algorithms/dispatch/disjoint.hpp> + #include <boost/geometry/geometries/concepts/check.hpp> -#include <boost/geometry/algorithms/dispatch/disjoint.hpp> +#include <boost/geometry/strategies/disjoint.hpp> namespace boost { namespace geometry { - -#ifndef DOXYGEN_NO_DISPATCH -namespace dispatch +namespace resolve_strategy { - -// If reversal is needed, perform it -template -< - typename Geometry1, typename Geometry2, - std::size_t DimensionCount, - typename Tag1, typename Tag2 -> -struct disjoint<Geometry1, Geometry2, DimensionCount, Tag1, Tag2, true> +struct disjoint { - static inline bool apply(Geometry1 const& g1, Geometry2 const& g2) + template <typename Geometry1, typename Geometry2, typename Strategy> + static inline bool apply(Geometry1 const& geometry1, + Geometry2 const& geometry2, + Strategy const& strategy) { - return disjoint + return dispatch::disjoint + < + Geometry1, Geometry2 + >::apply(geometry1, geometry2, strategy); + } + + template <typename Geometry1, typename Geometry2> + static inline bool apply(Geometry1 const& geometry1, + Geometry2 const& geometry2, + default_strategy) + { + typedef typename strategy::disjoint::services::default_strategy < - Geometry2, Geometry1, - DimensionCount, - Tag2, Tag1 - >::apply(g2, g1); + Geometry1, Geometry2 + >::type strategy_type; + + return dispatch::disjoint + < + Geometry1, Geometry2 + >::apply(geometry1, geometry2, strategy_type()); } }; - -} // namespace dispatch -#endif // DOXYGEN_NO_DISPATCH +} // namespace resolve_strategy namespace resolve_variant { @@ -71,7 +79,8 @@ namespace resolve_variant { template <typename Geometry1, typename Geometry2> struct disjoint { - static inline bool apply(Geometry1 const& geometry1, Geometry2 const& geometry2) + template <typename Strategy> + static inline bool apply(Geometry1 const& geometry1, Geometry2 const& geometry2, Strategy const& strategy) { concepts::check_concepts_and_equal_dimensions < @@ -79,88 +88,135 @@ struct disjoint Geometry2 const >(); - return dispatch::disjoint<Geometry1, Geometry2>::apply(geometry1, geometry2); + return resolve_strategy::disjoint::apply(geometry1, geometry2, strategy); } }; template <BOOST_VARIANT_ENUM_PARAMS(typename T), typename Geometry2> struct disjoint<boost::variant<BOOST_VARIANT_ENUM_PARAMS(T)>, Geometry2> { + template <typename Strategy> struct visitor: boost::static_visitor<bool> { Geometry2 const& m_geometry2; + Strategy const& m_strategy; - visitor(Geometry2 const& geometry2): m_geometry2(geometry2) {} + visitor(Geometry2 const& geometry2, Strategy const& strategy) + : m_geometry2(geometry2) + , m_strategy(strategy) + {} template <typename Geometry1> bool operator()(Geometry1 const& geometry1) const { - return disjoint<Geometry1, Geometry2>::apply(geometry1, m_geometry2); + return disjoint<Geometry1, Geometry2>::apply(geometry1, m_geometry2, m_strategy); } }; - static inline bool - apply(boost::variant<BOOST_VARIANT_ENUM_PARAMS(T)> const& geometry1, - Geometry2 const& geometry2) + template <typename Strategy> + static inline bool apply(boost::variant<BOOST_VARIANT_ENUM_PARAMS(T)> const& geometry1, + Geometry2 const& geometry2, + Strategy const& strategy) { - return boost::apply_visitor(visitor(geometry2), geometry1); + return boost::apply_visitor(visitor<Strategy>(geometry2, strategy), geometry1); } }; template <typename Geometry1, BOOST_VARIANT_ENUM_PARAMS(typename T)> struct disjoint<Geometry1, boost::variant<BOOST_VARIANT_ENUM_PARAMS(T)> > { + template <typename Strategy> struct visitor: boost::static_visitor<bool> { Geometry1 const& m_geometry1; + Strategy const& m_strategy; - visitor(Geometry1 const& geometry1): m_geometry1(geometry1) {} + visitor(Geometry1 const& geometry1, Strategy const& strategy) + : m_geometry1(geometry1) + , m_strategy(strategy) + {} template <typename Geometry2> bool operator()(Geometry2 const& geometry2) const { - return disjoint<Geometry1, Geometry2>::apply(m_geometry1, geometry2); + return disjoint<Geometry1, Geometry2>::apply(m_geometry1, geometry2, m_strategy); } }; - static inline bool - apply(Geometry1 const& geometry1, - boost::variant<BOOST_VARIANT_ENUM_PARAMS(T)> const& geometry2) + template <typename Strategy> + static inline bool apply(Geometry1 const& geometry1, + boost::variant<BOOST_VARIANT_ENUM_PARAMS(T)> const& geometry2, + Strategy const& strategy) { - return boost::apply_visitor(visitor(geometry1), geometry2); + return boost::apply_visitor(visitor<Strategy>(geometry1, strategy), geometry2); } }; -template < +template +< BOOST_VARIANT_ENUM_PARAMS(typename T1), BOOST_VARIANT_ENUM_PARAMS(typename T2) > -struct disjoint< - boost::variant<BOOST_VARIANT_ENUM_PARAMS(T1)>, - boost::variant<BOOST_VARIANT_ENUM_PARAMS(T2)> -> +struct disjoint + < + boost::variant<BOOST_VARIANT_ENUM_PARAMS(T1)>, + boost::variant<BOOST_VARIANT_ENUM_PARAMS(T2)> + > { + template <typename Strategy> struct visitor: boost::static_visitor<bool> { + Strategy const& m_strategy; + + visitor(Strategy const& strategy) + : m_strategy(strategy) + {} + template <typename Geometry1, typename Geometry2> bool operator()(Geometry1 const& geometry1, Geometry2 const& geometry2) const { - return disjoint<Geometry1, Geometry2>::apply(geometry1, geometry2); + return disjoint<Geometry1, Geometry2>::apply(geometry1, geometry2, m_strategy); } }; - static inline bool - apply(boost::variant<BOOST_VARIANT_ENUM_PARAMS(T1)> const& geometry1, - boost::variant<BOOST_VARIANT_ENUM_PARAMS(T2)> const& geometry2) + template <typename Strategy> + static inline bool apply(boost::variant<BOOST_VARIANT_ENUM_PARAMS(T1)> const& geometry1, + boost::variant<BOOST_VARIANT_ENUM_PARAMS(T2)> const& geometry2, + Strategy const& strategy) { - return boost::apply_visitor(visitor(), geometry1, geometry2); + return boost::apply_visitor(visitor<Strategy>(strategy), geometry1, geometry2); } }; } // namespace resolve_variant +/*! +\brief \brief_check2{are disjoint} +\ingroup disjoint +\tparam Geometry1 \tparam_geometry +\tparam Geometry2 \tparam_geometry +\tparam Strategy \tparam_strategy{Disjoint} +\param geometry1 \param_geometry +\param geometry2 \param_geometry +\param strategy \param_strategy{disjoint} +\return \return_check2{are disjoint} + +\qbk{distinguish,with strategy} +\qbk{[include reference/algorithms/disjoint.qbk]} +*/ +template <typename Geometry1, typename Geometry2, typename Strategy> +inline bool disjoint(Geometry1 const& geometry1, + Geometry2 const& geometry2, + Strategy const& strategy) +{ + return resolve_variant::disjoint + < + Geometry1, Geometry2 + >::apply(geometry1, geometry2, strategy); +} + /*! \brief \brief_check2{are disjoint} @@ -177,7 +233,10 @@ template <typename Geometry1, typename Geometry2> inline bool disjoint(Geometry1 const& geometry1, Geometry2 const& geometry2) { - return resolve_variant::disjoint<Geometry1, Geometry2>::apply(geometry1, geometry2); + return resolve_variant::disjoint + < + Geometry1, Geometry2 + >::apply(geometry1, geometry2, default_strategy()); } diff --git a/boost/geometry/algorithms/detail/disjoint/linear_areal.hpp b/boost/geometry/algorithms/detail/disjoint/linear_areal.hpp index 6a48b684a1..e6077d3e7f 100644 --- a/boost/geometry/algorithms/detail/disjoint/linear_areal.hpp +++ b/boost/geometry/algorithms/detail/disjoint/linear_areal.hpp @@ -5,8 +5,8 @@ // Copyright (c) 2009-2014 Mateusz Loskot, London, UK. // Copyright (c) 2013-2014 Adam Wulkiewicz, Lodz, Poland. -// This file was modified by Oracle on 2013-2015. -// Modifications copyright (c) 2013-2015, Oracle and/or its affiliates. +// This file was modified by Oracle on 2013-2017. +// Modifications copyright (c) 2013-2017, 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 @@ -61,19 +61,28 @@ template <typename Geometry1, typename Geometry2, typename Tag1OrMulti = typename tag_cast<Tag1, multi_tag>::type> struct disjoint_no_intersections_policy { - static inline bool apply(Geometry1 const& g1, Geometry2 const& g2) + /*! + \tparam Strategy point_in_geometry strategy + */ + template <typename Strategy> + static inline bool apply(Geometry1 const& g1, Geometry2 const& g2, Strategy const& strategy) { typedef typename point_type<Geometry1>::type point1_type; point1_type p; geometry::point_on_border(p, g1); - return !geometry::covered_by(p, g2); + + return !geometry::covered_by(p, g2, strategy); } }; template <typename Geometry1, typename Geometry2, typename Tag1> struct disjoint_no_intersections_policy<Geometry1, Geometry2, Tag1, multi_tag> { - static inline bool apply(Geometry1 const& g1, Geometry2 const& g2) + /*! + \tparam Strategy point_in_geometry strategy + */ + template <typename Strategy> + static inline bool apply(Geometry1 const& g1, Geometry2 const& g2, Strategy const& strategy) { // TODO: use partition or rtree on g2 typedef typename boost::range_iterator<Geometry1 const>::type iterator; @@ -81,7 +90,7 @@ struct disjoint_no_intersections_policy<Geometry1, Geometry2, Tag1, multi_tag> { typedef typename boost::range_value<Geometry1 const>::type value_type; if ( ! disjoint_no_intersections_policy<value_type const, Geometry2> - ::apply(*it, g2) ) + ::apply(*it, g2, strategy) ) { return false; } @@ -96,15 +105,21 @@ template<typename Geometry1, typename Geometry2, = disjoint_no_intersections_policy<Geometry1, Geometry2> > struct disjoint_linear_areal { - static inline bool apply(Geometry1 const& g1, Geometry2 const& g2) + /*! + \tparam Strategy relate (segments intersection) strategy + */ + template <typename Strategy> + static inline bool apply(Geometry1 const& g1, Geometry2 const& g2, Strategy const& strategy) { // if there are intersections - return false - if ( !disjoint_linear<Geometry1, Geometry2>::apply(g1, g2) ) + if ( !disjoint_linear<Geometry1, Geometry2>::apply(g1, g2, strategy) ) { return false; } - return NoIntersectionsPolicy::apply(g1, g2); + return NoIntersectionsPolicy + ::apply(g1, g2, + strategy.template get_point_in_geometry_strategy<Geometry1, Geometry2>()); } }; @@ -126,16 +141,18 @@ template <typename Segment, typename Polygon> class disjoint_segment_areal<Segment, Polygon, polygon_tag> { private: - template <typename InteriorRings> + template <typename InteriorRings, typename Strategy> static inline bool check_interior_rings(InteriorRings const& interior_rings, - Segment const& segment) + Segment const& segment, + Strategy const& strategy) { typedef typename boost::range_value<InteriorRings>::type ring_type; typedef unary_disjoint_geometry_to_query_geometry < Segment, + Strategy, disjoint_range_segment_or_box < ring_type, closure<ring_type>::value, Segment @@ -147,24 +164,27 @@ private: unary_predicate_type >::apply(boost::begin(interior_rings), boost::end(interior_rings), - unary_predicate_type(segment)); + unary_predicate_type(segment, strategy)); } public: - static inline bool apply(Segment const& segment, Polygon const& polygon) + template <typename IntersectionStrategy> + static inline bool apply(Segment const& segment, + Polygon const& polygon, + IntersectionStrategy const& strategy) { typedef typename geometry::ring_type<Polygon>::type ring; if ( !disjoint_range_segment_or_box < ring, closure<Polygon>::value, Segment - >::apply(geometry::exterior_ring(polygon), segment) ) + >::apply(geometry::exterior_ring(polygon), segment, strategy) ) { return false; } - if ( !check_interior_rings(geometry::interior_rings(polygon), segment) ) + if ( !check_interior_rings(geometry::interior_rings(polygon), segment, strategy) ) { return false; } @@ -172,7 +192,8 @@ public: typename point_type<Segment>::type p; detail::assign_point_from_index<0>(segment, p); - return !geometry::covered_by(p, polygon); + return !geometry::covered_by(p, polygon, + strategy.template get_point_in_geometry_strategy<Segment, Polygon>()); } }; @@ -180,13 +201,14 @@ public: template <typename Segment, typename MultiPolygon> struct disjoint_segment_areal<Segment, MultiPolygon, multi_polygon_tag> { - static inline - bool apply(Segment const& segment, MultiPolygon const& multipolygon) + template <typename IntersectionStrategy> + static inline bool apply(Segment const& segment, MultiPolygon const& multipolygon, + IntersectionStrategy const& strategy) { return multirange_constant_size_geometry < MultiPolygon, Segment - >::apply(multipolygon, segment); + >::apply(multipolygon, segment, strategy); } }; @@ -194,20 +216,24 @@ struct disjoint_segment_areal<Segment, MultiPolygon, multi_polygon_tag> template <typename Segment, typename Ring> struct disjoint_segment_areal<Segment, Ring, ring_tag> { - static inline bool apply(Segment const& segment, Ring const& ring) + template <typename IntersectionStrategy> + static inline bool apply(Segment const& segment, + Ring const& ring, + IntersectionStrategy const& strategy) { if ( !disjoint_range_segment_or_box < Ring, closure<Ring>::value, Segment - >::apply(ring, segment) ) + >::apply(ring, segment, strategy) ) { return false; } typename point_type<Segment>::type p; detail::assign_point_from_index<0>(segment, p); - - return !geometry::covered_by(p, ring); + + return !geometry::covered_by(p, ring, + strategy.template get_point_in_geometry_strategy<Segment, Ring>()); } }; @@ -231,14 +257,15 @@ struct disjoint<Linear, Areal, 2, linear_tag, areal_tag, false> template <typename Areal, typename Linear> struct disjoint<Areal, Linear, 2, areal_tag, linear_tag, false> -{ - static inline - bool apply(Areal const& areal, Linear const& linear) +{ + template <typename Strategy> + static inline bool apply(Areal const& areal, Linear const& linear, + Strategy const& strategy) { return detail::disjoint::disjoint_linear_areal < Linear, Areal - >::apply(linear, areal); + >::apply(linear, areal, strategy); } }; @@ -246,12 +273,14 @@ struct disjoint<Areal, Linear, 2, areal_tag, linear_tag, false> template <typename Areal, typename Segment> struct disjoint<Areal, Segment, 2, areal_tag, segment_tag, false> { - static inline bool apply(Areal const& g1, Segment const& g2) + template <typename Strategy> + static inline bool apply(Areal const& g1, Segment const& g2, + Strategy const& strategy) { return detail::disjoint::disjoint_segment_areal < Segment, Areal - >::apply(g2, g1); + >::apply(g2, g1, strategy); } }; diff --git a/boost/geometry/algorithms/detail/disjoint/linear_linear.hpp b/boost/geometry/algorithms/detail/disjoint/linear_linear.hpp index 91f985edb8..989b8df247 100644 --- a/boost/geometry/algorithms/detail/disjoint/linear_linear.hpp +++ b/boost/geometry/algorithms/detail/disjoint/linear_linear.hpp @@ -5,8 +5,8 @@ // Copyright (c) 2009-2014 Mateusz Loskot, London, UK. // Copyright (c) 2013-2014 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-2017. +// Modifications copyright (c) 2013-2017, 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 @@ -53,7 +53,9 @@ namespace detail { namespace disjoint template <typename Segment1, typename Segment2> struct disjoint_segment { - static inline bool apply(Segment1 const& segment1, Segment2 const& segment2) + template <typename Strategy> + static inline bool apply(Segment1 const& segment1, Segment2 const& segment2, + Strategy const& strategy) { typedef typename point_type<Segment1>::type point_type; @@ -62,23 +64,23 @@ struct disjoint_segment rescale_policy_type robust_policy; typedef segment_intersection_points - < - point_type, - typename segment_ratio_type + < + point_type, + typename segment_ratio_type < point_type, rescale_policy_type >::type - > intersection_return_type; + > intersection_return_type; - intersection_return_type is - = strategy::intersection::relate_cartesian_segments + typedef policies::relate::segments_intersection_points < - policies::relate::segments_intersection_points - < - intersection_return_type - > - >::apply(segment1, segment2, robust_policy); + intersection_return_type + > intersection_policy; + + intersection_return_type is = strategy.apply(segment1, segment2, + intersection_policy(), + robust_policy); return is.count == 0; } @@ -109,8 +111,10 @@ struct assign_disjoint_policy template <typename Geometry1, typename Geometry2> struct disjoint_linear { - static inline - bool apply(Geometry1 const& geometry1, Geometry2 const& geometry2) + template <typename Strategy> + static inline bool apply(Geometry1 const& geometry1, + Geometry2 const& geometry2, + Strategy const& strategy) { typedef typename geometry::point_type<Geometry1>::type point_type; typedef detail::no_rescale_policy rescale_policy_type; @@ -147,7 +151,7 @@ struct disjoint_linear Geometry1, Geometry2, assign_disjoint_policy > >::apply(0, geometry1, 1, geometry2, - rescale_policy_type(), turns, interrupt_policy); + strategy, rescale_policy_type(), turns, interrupt_policy); return !interrupt_policy.has_intersections; } diff --git a/boost/geometry/algorithms/detail/disjoint/linear_segment_or_box.hpp b/boost/geometry/algorithms/detail/disjoint/linear_segment_or_box.hpp index 8d82f7c911..b4c71c8f30 100644 --- a/boost/geometry/algorithms/detail/disjoint/linear_segment_or_box.hpp +++ b/boost/geometry/algorithms/detail/disjoint/linear_segment_or_box.hpp @@ -53,8 +53,10 @@ template > struct disjoint_range_segment_or_box { - static inline - bool apply(Range const& range, SegmentOrBox const& segment_or_box) + template <typename Strategy> + static inline bool apply(Range const& range, + SegmentOrBox const& segment_or_box, + Strategy const& strategy) { typedef typename closeable_view<Range const, Closure>::type view_type; @@ -85,7 +87,8 @@ struct disjoint_range_segment_or_box < point_type, SegmentOrBox >::apply(geometry::range::front<view_type const>(view), - segment_or_box); + segment_or_box, + strategy.template get_point_in_geometry_strategy<Range, SegmentOrBox>()); } else { @@ -99,7 +102,7 @@ struct disjoint_range_segment_or_box if ( !dispatch::disjoint < range_segment, SegmentOrBox - >::apply(rng_segment, segment_or_box) ) + >::apply(rng_segment, segment_or_box, strategy) ) { return false; } diff --git a/boost/geometry/algorithms/detail/disjoint/multipoint_geometry.hpp b/boost/geometry/algorithms/detail/disjoint/multipoint_geometry.hpp index 29e438e546..7c1a93cdb7 100644 --- a/boost/geometry/algorithms/detail/disjoint/multipoint_geometry.hpp +++ b/boost/geometry/algorithms/detail/disjoint/multipoint_geometry.hpp @@ -1,8 +1,9 @@ // Boost.Geometry (aka GGL, Generic Geometry Library) -// Copyright (c) 2014-2015, Oracle and/or its affiliates. +// Copyright (c) 2014-2017, Oracle and/or its affiliates. // Contributed and/or modified by Menelaos Karavelas, on behalf of Oracle +// Contributed and/or modified by Adam Wulkiewicz, on behalf of Oracle // Licensed under the Boost Software License version 1.0. // http://www.boost.org/users/license.html @@ -14,8 +15,10 @@ #include <vector> #include <boost/range.hpp> +#include <boost/mpl/assert.hpp> #include <boost/geometry/core/assert.hpp> +#include <boost/geometry/core/tag.hpp> #include <boost/geometry/core/tags.hpp> #include <boost/geometry/geometries/box.hpp> @@ -105,36 +108,74 @@ template <typename MultiPoint, typename Linear> class multipoint_linear { private: - // structs for partition -- start - struct expand_box + struct expand_box_point { - template <typename Box, typename Geometry> - static inline void apply(Box& total, Geometry const& geometry) + template <typename Box, typename Point> + static inline void apply(Box& total, Point const& point) { - geometry::expand(total, geometry::return_envelope<Box>(geometry)); + geometry::expand(total, point); } + }; + // TODO: After adding non-cartesian Segment envelope to the library + // this policy should be modified to take envelope strategy. + struct expand_box_segment + { + template <typename Box, typename Segment> + static inline void apply(Box& total, Segment const& segment) + { + geometry::expand(total, geometry::return_envelope<Box>(segment)); + } }; - struct overlaps_box + struct overlaps_box_point { - template <typename Box, typename Geometry> - static inline bool apply(Box const& box, Geometry const& geometry) + template <typename Box, typename Point> + static inline bool apply(Box const& box, Point const& point) { - return ! dispatch::disjoint<Geometry, Box>::apply(geometry, box); + // The default strategy is enough in this case + typedef typename strategy::disjoint::services::default_strategy + < + Point, Box + >::type strategy_type; + return ! dispatch::disjoint<Point, Box>::apply(point, box, strategy_type()); } }; + // TODO: After implementing disjoint Segment/Box for non-cartesian geometries + // this strategy should be passed here. + // TODO: This Segment/Box strategy should somehow be derived from Point/Segment strategy + // which by default is winding containing CS-specific side strategy + // TODO: disjoint Segment/Box will be called in this case which may take + // quite long in non-cartesian CS. So we should consider passing range of bounding boxes + // of segments after calculating them once. + struct overlaps_box_segment + { + template <typename Box, typename Segment> + static inline bool apply(Box const& box, Segment const& segment) + { + typedef typename strategy::disjoint::services::default_strategy + < + Segment, Box + >::type strategy_type; + return ! dispatch::disjoint<Segment, Box>::apply(segment, box, strategy_type()); + } + }; + + template <typename PtSegStrategy> class item_visitor_type { public: - item_visitor_type() : m_intersection_found(false) {} + item_visitor_type(PtSegStrategy const& strategy) + : m_intersection_found(false) + , m_strategy(strategy) + {} 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)) + && ! dispatch::disjoint<Item1, Item2>::apply(item1, item2, m_strategy)) { m_intersection_found = true; } @@ -144,6 +185,7 @@ private: private: bool m_intersection_found; + PtSegStrategy const& m_strategy; }; // structs for partition -- end @@ -172,23 +214,25 @@ private: }; public: - static inline bool apply(MultiPoint const& multipoint, Linear const& linear) + template <typename Strategy> + static inline bool apply(MultiPoint const& multipoint, Linear const& linear, Strategy const& strategy) { - item_visitor_type visitor; + item_visitor_type<Strategy> visitor(strategy); geometry::partition < - geometry::model::box<typename point_type<MultiPoint>::type>, - expand_box, - overlaps_box - >::apply(multipoint, segment_range(linear), visitor); + geometry::model::box<typename point_type<MultiPoint>::type> + >::apply(multipoint, segment_range(linear), visitor, + expand_box_point(), overlaps_box_point(), + expand_box_segment(), overlaps_box_segment()); return ! visitor.intersection_found(); } - static inline bool apply(Linear const& linear, MultiPoint const& multipoint) + template <typename Strategy> + static inline bool apply(Linear const& linear, MultiPoint const& multipoint, Strategy const& strategy) { - return apply(multipoint, linear); + return apply(multipoint, linear, strategy); } }; @@ -240,8 +284,10 @@ struct disjoint multi_point_tag, multi_point_tag, false > { + template <typename Strategy> static inline bool apply(MultiPoint1 const& multipoint1, - MultiPoint2 const& multipoint2) + MultiPoint2 const& multipoint2, + Strategy const& ) { if ( boost::size(multipoint2) < boost::size(multipoint1) ) { diff --git a/boost/geometry/algorithms/detail/disjoint/multirange_geometry.hpp b/boost/geometry/algorithms/detail/disjoint/multirange_geometry.hpp index 78a683e46e..53fb1642af 100644 --- a/boost/geometry/algorithms/detail/disjoint/multirange_geometry.hpp +++ b/boost/geometry/algorithms/detail/disjoint/multirange_geometry.hpp @@ -1,8 +1,9 @@ // Boost.Geometry (aka GGL, Generic Geometry Library) -// Copyright (c) 2014, Oracle and/or its affiliates. +// Copyright (c) 2014-2017, Oracle and/or its affiliates. // Contributed and/or modified by Menelaos Karavelas, on behalf of Oracle +// Contributed and/or modified by Adam Wulkiewicz, on behalf of Oracle // Licensed under the Boost Software License version 1.0. // http://www.boost.org/users/license.html @@ -25,34 +26,40 @@ namespace detail { namespace disjoint { -template <typename Geometry, typename BinaryPredicate> +template <typename Geometry, typename Strategy, typename BinaryPredicate> class unary_disjoint_geometry_to_query_geometry { public: - unary_disjoint_geometry_to_query_geometry(Geometry const& geometry) + unary_disjoint_geometry_to_query_geometry(Geometry const& geometry, + Strategy const& strategy) : m_geometry(geometry) + , m_strategy(strategy) {} template <typename QueryGeometry> inline bool apply(QueryGeometry const& query_geometry) const { - return BinaryPredicate::apply(query_geometry, m_geometry); + return BinaryPredicate::apply(query_geometry, m_geometry, m_strategy); } private: Geometry const& m_geometry; + Strategy const& m_strategy; }; template<typename MultiRange, typename ConstantSizeGeometry> struct multirange_constant_size_geometry { + template <typename Strategy> static inline bool apply(MultiRange const& multirange, - ConstantSizeGeometry const& constant_size_geometry) + ConstantSizeGeometry const& constant_size_geometry, + Strategy const& strategy) { typedef unary_disjoint_geometry_to_query_geometry < ConstantSizeGeometry, + Strategy, dispatch::disjoint < typename boost::range_value<MultiRange>::type, @@ -64,13 +71,15 @@ struct multirange_constant_size_geometry < unary_predicate_type >::apply(boost::begin(multirange), boost::end(multirange), - unary_predicate_type(constant_size_geometry)); + unary_predicate_type(constant_size_geometry, strategy)); } + template <typename Strategy> static inline bool apply(ConstantSizeGeometry const& constant_size_geometry, - MultiRange const& multirange) + MultiRange const& multirange, + Strategy const& strategy) { - return apply(multirange, constant_size_geometry); + return apply(multirange, constant_size_geometry, strategy); } }; diff --git a/boost/geometry/algorithms/detail/disjoint/point_box.hpp b/boost/geometry/algorithms/detail/disjoint/point_box.hpp index 2f1085ada9..2e6773d221 100644 --- a/boost/geometry/algorithms/detail/disjoint/point_box.hpp +++ b/boost/geometry/algorithms/detail/disjoint/point_box.hpp @@ -5,8 +5,8 @@ // Copyright (c) 2009-2015 Mateusz Loskot, London, UK. // Copyright (c) 2013-2015 Adam Wulkiewicz, Lodz, Poland -// This file was modified by Oracle on 2013-2016. -// Modifications copyright (c) 2013-2016, Oracle and/or its affiliates. +// This file was modified by Oracle on 2013-2017. +// Modifications copyright (c) 2013-2017, 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 @@ -28,7 +28,7 @@ #include <boost/geometry/core/tags.hpp> #include <boost/geometry/algorithms/dispatch/disjoint.hpp> -#include <boost/geometry/strategies/cartesian/point_in_box.hpp> +#include <boost/geometry/strategies/disjoint.hpp> namespace boost { namespace geometry { @@ -44,13 +44,13 @@ namespace detail { namespace disjoint template <typename Point, typename Box> inline bool disjoint_point_box(Point const& point, Box const& box) { + typedef typename strategy::disjoint::services::default_strategy + < + Point, Box + >::type strategy_type; + // ! covered_by(point, box) - return ! strategy::within::relate_point_box_loop - < - strategy::within::covered_by_range, - Point, Box, - 0, dimension<Point>::type::value - >::apply(point, box); + return ! strategy_type::apply(point, box); } @@ -66,15 +66,11 @@ namespace dispatch template <typename Point, typename Box, std::size_t DimensionCount> struct disjoint<Point, Box, DimensionCount, point_tag, box_tag, false> { - static inline bool apply(Point const& point, Box const& box) + template <typename Strategy> + static inline bool apply(Point const& point, Box const& box, Strategy const& ) { // ! covered_by(point, box) - return ! strategy::within::relate_point_box_loop - < - strategy::within::covered_by_range, - Point, Box, - 0, DimensionCount - >::apply(point, box); + return ! Strategy::apply(point, box); } }; diff --git a/boost/geometry/algorithms/detail/disjoint/point_geometry.hpp b/boost/geometry/algorithms/detail/disjoint/point_geometry.hpp index 9ae43f73d0..66bd7c26ce 100644 --- a/boost/geometry/algorithms/detail/disjoint/point_geometry.hpp +++ b/boost/geometry/algorithms/detail/disjoint/point_geometry.hpp @@ -39,11 +39,12 @@ namespace detail { namespace disjoint struct reverse_covered_by { - template <typename Geometry1, typename Geometry2> - static inline - bool apply(Geometry1 const& geometry1, Geometry2 const& geometry2) + template <typename Geometry1, typename Geometry2, typename Strategy> + static inline bool apply(Geometry1 const& geometry1, + Geometry2 const& geometry2, + Strategy const& strategy) { - return ! geometry::covered_by(geometry1, geometry2); + return ! geometry::covered_by(geometry1, geometry2, strategy); } }; diff --git a/boost/geometry/algorithms/detail/disjoint/point_point.hpp b/boost/geometry/algorithms/detail/disjoint/point_point.hpp index 7580b7287b..13ac34d718 100644 --- a/boost/geometry/algorithms/detail/disjoint/point_point.hpp +++ b/boost/geometry/algorithms/detail/disjoint/point_point.hpp @@ -5,8 +5,8 @@ // 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, 2015. -// Modifications copyright (c) 2013-2015, Oracle and/or its affiliates. +// This file was modified by Oracle on 2013, 2014, 2015, 2017. +// Modifications copyright (c) 2013-2017, 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 @@ -59,6 +59,12 @@ namespace detail { namespace disjoint template <std::size_t Dimension, std::size_t DimensionCount> struct point_point_generic { + template <typename Point1, typename Point2, typename Strategy> + static inline bool apply(Point1 const& p1, Point2 const& p2, Strategy const& ) + { + return apply(p1, p2); + } + template <typename Point1, typename Point2> static inline bool apply(Point1 const& p1, Point2 const& p2) { @@ -75,7 +81,7 @@ template <std::size_t DimensionCount> struct point_point_generic<DimensionCount, DimensionCount> { template <typename Point1, typename Point2> - static inline bool apply(Point1 const&, Point2 const&) + static inline bool apply(Point1 const&, Point2 const& ) { return false; } @@ -135,6 +141,12 @@ private: }; public: + template <typename Point1, typename Point2, typename Strategy> + static inline bool apply(Point1 const& point1, Point2 const& point2, Strategy const& ) + { + return apply(point1, point2); + } + template <typename Point1, typename Point2> static inline bool apply(Point1 const& point1, Point2 const& point2) { diff --git a/boost/geometry/algorithms/detail/disjoint/segment_box.hpp b/boost/geometry/algorithms/detail/disjoint/segment_box.hpp index cc0c7949e3..c2741ce72c 100644 --- a/boost/geometry/algorithms/detail/disjoint/segment_box.hpp +++ b/boost/geometry/algorithms/detail/disjoint/segment_box.hpp @@ -5,8 +5,8 @@ // Copyright (c) 2009-2014 Mateusz Loskot, London, UK. // Copyright (c) 2013-2014 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-2017. +// Modifications copyright (c) 2013-2017, 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 @@ -22,19 +22,8 @@ #define BOOST_GEOMETRY_ALGORITHMS_DETAIL_DISJOINT_SEGMENT_BOX_HPP #include <cstddef> -#include <utility> -#include <boost/numeric/conversion/cast.hpp> - -#include <boost/geometry/util/math.hpp> -#include <boost/geometry/util/calculation_type.hpp> - -#include <boost/geometry/core/access.hpp> #include <boost/geometry/core/tags.hpp> -#include <boost/geometry/core/coordinate_dimension.hpp> -#include <boost/geometry/core/point_type.hpp> - -#include <boost/geometry/algorithms/detail/assign_indexed_point.hpp> #include <boost/geometry/algorithms/dispatch/disjoint.hpp> @@ -47,236 +36,19 @@ namespace boost { namespace geometry namespace detail { namespace disjoint { - -template <std::size_t I> -struct compute_tmin_tmax_per_dim -{ - template <typename SegmentPoint, typename Box, typename RelativeDistance> - static inline void apply(SegmentPoint const& p0, - SegmentPoint const& p1, - Box const& box, - RelativeDistance& ti_min, - RelativeDistance& ti_max, - RelativeDistance& diff) - { - typedef typename coordinate_type<Box>::type box_coordinate_type; - typedef typename coordinate_type - < - SegmentPoint - >::type point_coordinate_type; - - RelativeDistance c_p0 = boost::numeric_cast - < - point_coordinate_type - >( geometry::get<I>(p0) ); - - RelativeDistance c_p1 = boost::numeric_cast - < - point_coordinate_type - >( geometry::get<I>(p1) ); - - RelativeDistance c_b_min = boost::numeric_cast - < - box_coordinate_type - >( geometry::get<geometry::min_corner, I>(box) ); - - RelativeDistance c_b_max = boost::numeric_cast - < - box_coordinate_type - >( geometry::get<geometry::max_corner, I>(box) ); - - if ( geometry::get<I>(p1) >= geometry::get<I>(p0) ) - { - diff = c_p1 - c_p0; - ti_min = c_b_min - c_p0; - ti_max = c_b_max - c_p0; - } - else - { - diff = c_p0 - c_p1; - ti_min = c_p0 - c_b_max; - ti_max = c_p0 - c_b_min; - } - } -}; - - -template -< - typename RelativeDistance, - typename SegmentPoint, - typename Box, - std::size_t I, - std::size_t Dimension -> -struct disjoint_segment_box_impl -{ - template <typename RelativeDistancePair> - static inline bool apply(SegmentPoint const& p0, - SegmentPoint const& p1, - Box const& box, - RelativeDistancePair& t_min, - RelativeDistancePair& t_max) - { - RelativeDistance ti_min, ti_max, diff; - - compute_tmin_tmax_per_dim<I>::apply(p0, p1, box, ti_min, ti_max, diff); - - if ( geometry::math::equals(diff, 0) ) - { - if ( (geometry::math::equals(t_min.second, 0) - && t_min.first > ti_max) - || - (geometry::math::equals(t_max.second, 0) - && t_max.first < ti_min) - || - (math::sign(ti_min) * math::sign(ti_max) > 0) ) - { - return true; - } - } - - RelativeDistance t_min_x_diff = t_min.first * diff; - RelativeDistance t_max_x_diff = t_max.first * diff; - - if ( t_min_x_diff > ti_max * t_min.second - || t_max_x_diff < ti_min * t_max.second ) - { - return true; - } - - if ( ti_min * t_min.second > t_min_x_diff ) - { - t_min.first = ti_min; - t_min.second = diff; - } - if ( ti_max * t_max.second < t_max_x_diff ) - { - t_max.first = ti_max; - t_max.second = diff; - } - - if ( t_min.first > t_min.second || t_max.first < 0 ) - { - return true; - } - - return disjoint_segment_box_impl - < - RelativeDistance, - SegmentPoint, - Box, - I + 1, - Dimension - >::apply(p0, p1, box, t_min, t_max); - } -}; - - -template -< - typename RelativeDistance, - typename SegmentPoint, - typename Box, - std::size_t Dimension -> -struct disjoint_segment_box_impl - < - RelativeDistance, SegmentPoint, Box, 0, Dimension - > -{ - static inline bool apply(SegmentPoint const& p0, - SegmentPoint const& p1, - Box const& box) - { - std::pair<RelativeDistance, RelativeDistance> t_min, t_max; - RelativeDistance diff; - - compute_tmin_tmax_per_dim<0>::apply(p0, p1, box, - t_min.first, t_max.first, diff); - - if ( geometry::math::equals(diff, 0) ) - { - if ( geometry::math::equals(t_min.first, 0) ) { t_min.first = -1; } - if ( geometry::math::equals(t_max.first, 0) ) { t_max.first = 1; } - - if (math::sign(t_min.first) * math::sign(t_max.first) > 0) - { - return true; - } - } - - if ( t_min.first > diff || t_max.first < 0 ) - { - return true; - } - - t_min.second = t_max.second = diff; - - return disjoint_segment_box_impl - < - RelativeDistance, SegmentPoint, Box, 1, Dimension - >::apply(p0, p1, box, t_min, t_max); - } -}; - - -template -< - typename RelativeDistance, - typename SegmentPoint, - typename Box, - std::size_t Dimension -> -struct disjoint_segment_box_impl - < - RelativeDistance, SegmentPoint, Box, Dimension, Dimension - > -{ - template <typename RelativeDistancePair> - static inline bool apply(SegmentPoint const&, SegmentPoint const&, - Box const&, - RelativeDistancePair&, RelativeDistancePair&) - { - return false; - } -}; - - -//========================================================================= - - -template <typename Segment, typename Box> struct disjoint_segment_box -{ - static inline bool apply(Segment const& segment, Box const& box) +{ + template <typename Segment, typename Box, typename Strategy> + static inline bool apply(Segment const& segment, Box const& box, Strategy const& strategy) { - assert_dimension_equal<Segment, Box>(); - - typedef typename util::calculation_type::geometric::binary - < - Segment, Box, void - >::type relative_distance_type; - - typedef typename point_type<Segment>::type segment_point_type; - segment_point_type p0, p1; - geometry::detail::assign_point_from_index<0>(segment, p0); - geometry::detail::assign_point_from_index<1>(segment, p1); - - return disjoint_segment_box_impl - < - relative_distance_type, segment_point_type, Box, - 0, dimension<Box>::value - >::apply(p0, p1, box); + return strategy.apply(segment, box); } }; - }} // namespace detail::disjoint #endif // DOXYGEN_NO_DETAIL - #ifndef DOXYGEN_NO_DISPATCH namespace dispatch { @@ -284,7 +56,7 @@ namespace dispatch template <typename Segment, typename Box, std::size_t DimensionCount> struct disjoint<Segment, Box, DimensionCount, segment_tag, box_tag, false> - : detail::disjoint::disjoint_segment_box<Segment, Box> + : detail::disjoint::disjoint_segment_box {}; |