diff options
author | DongHun Kwak <dh0128.kwak@samsung.com> | 2017-09-13 11:24:46 +0900 |
---|---|---|
committer | DongHun Kwak <dh0128.kwak@samsung.com> | 2017-09-13 11:25:39 +0900 |
commit | 4fadd968fa12130524c8380f33fcfe25d4de79e5 (patch) | |
tree | fd26a490cd15388d42fc6652b3c5c13012e7f93e /boost/geometry/algorithms/detail/disjoint | |
parent | b5c87084afaef42b2d058f68091be31988a6a874 (diff) | |
download | boost-4fadd968fa12130524c8380f33fcfe25d4de79e5.tar.gz boost-4fadd968fa12130524c8380f33fcfe25d4de79e5.tar.bz2 boost-4fadd968fa12130524c8380f33fcfe25d4de79e5.zip |
Imported Upstream version 1.65.0upstream/1.65.0
Change-Id: Icf8400b375482cb11bcf77440a6934ba360d6ba4
Signed-off-by: DongHun Kwak <dh0128.kwak@samsung.com>
Diffstat (limited to 'boost/geometry/algorithms/detail/disjoint')
4 files changed, 401 insertions, 32 deletions
diff --git a/boost/geometry/algorithms/detail/disjoint/box_box.hpp b/boost/geometry/algorithms/detail/disjoint/box_box.hpp index f830f8161c..87618939b8 100644 --- a/boost/geometry/algorithms/detail/disjoint/box_box.hpp +++ b/boost/geometry/algorithms/detail/disjoint/box_box.hpp @@ -121,9 +121,18 @@ struct box_box<Box1, Box2, 0, DimensionCount, spherical_tag> // calculate positive longitude translation with b1_min as origin calc_t const diff_min = math::longitude_distance_unsigned<units_t>(b1_min, b2_min); calc_t const b2_min_transl = b1_min + diff_min; // always right of b1_min + calc_t b2_max_transl = b2_min_transl - constants::period() + diff2; - if (b2_min_transl > b1_max // b2_min right of b1_max - && b2_min_transl - constants::period() + diff2 < b1_min) // b2_max left of b1_min + // if the translation is too close then use the original point + // note that math::abs(b2_max_transl - b2_max) takes values very + // close to k*2*constants::period() for k=0,1,2,... + if (math::abs(b2_max_transl - b2_max) < constants::period() / 2) + { + b2_max_transl = b2_max; + } + + if (b2_min_transl > b1_max // b2_min right of b1_max + && b2_max_transl < b1_min) // b2_max left of b1_min { return true; } diff --git a/boost/geometry/algorithms/detail/disjoint/implementation.hpp b/boost/geometry/algorithms/detail/disjoint/implementation.hpp index d482c4a5a9..3a3d9865d1 100644 --- a/boost/geometry/algorithms/detail/disjoint/implementation.hpp +++ b/boost/geometry/algorithms/detail/disjoint/implementation.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 diff --git a/boost/geometry/algorithms/detail/disjoint/multipoint_geometry.hpp b/boost/geometry/algorithms/detail/disjoint/multipoint_geometry.hpp index 7c1a93cdb7..f8d3e3c593 100644 --- a/boost/geometry/algorithms/detail/disjoint/multipoint_geometry.hpp +++ b/boost/geometry/algorithms/detail/disjoint/multipoint_geometry.hpp @@ -1,6 +1,7 @@ // Boost.Geometry (aka GGL, Generic Geometry Library) // Copyright (c) 2014-2017, Oracle and/or its affiliates. +// Copyright (c) 2017 Adam Wulkiewicz, Lodz, Poland. // Contributed and/or modified by Menelaos Karavelas, on behalf of Oracle // Contributed and/or modified by Adam Wulkiewicz, on behalf of Oracle @@ -30,7 +31,9 @@ #include <boost/geometry/algorithms/detail/check_iterator_range.hpp> #include <boost/geometry/algorithms/detail/partition.hpp> +#include <boost/geometry/algorithms/detail/disjoint/box_box.hpp> #include <boost/geometry/algorithms/detail/disjoint/multirange_geometry.hpp> +#include <boost/geometry/algorithms/detail/disjoint/point_box.hpp> #include <boost/geometry/algorithms/detail/disjoint/point_point.hpp> #include <boost/geometry/algorithms/detail/disjoint/point_geometry.hpp> #include <boost/geometry/algorithms/detail/relate/less.hpp> @@ -117,15 +120,21 @@ private: } }; - // TODO: After adding non-cartesian Segment envelope to the library - // this policy should be modified to take envelope strategy. + template <typename EnvelopeStrategy> struct expand_box_segment { + explicit expand_box_segment(EnvelopeStrategy const& strategy) + : m_strategy(strategy) + {} + template <typename Box, typename Segment> - static inline void apply(Box& total, Segment const& segment) + inline void apply(Box& total, Segment const& segment) const { - geometry::expand(total, geometry::return_envelope<Box>(segment)); + geometry::expand(total, + geometry::return_envelope<Box>(segment, m_strategy)); } + + EnvelopeStrategy const& m_strategy; }; struct overlaps_box_point @@ -134,32 +143,24 @@ private: static inline bool apply(Box const& box, Point const& point) { // 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()); + return ! detail::disjoint::disjoint_point_box(point, box); } }; - // 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. + template <typename DisjointStrategy> struct overlaps_box_segment { + explicit overlaps_box_segment(DisjointStrategy const& strategy) + : m_strategy(strategy) + {} + template <typename Box, typename Segment> - static inline bool apply(Box const& box, Segment const& segment) + inline bool apply(Box const& box, Segment const& segment) const { - typedef typename strategy::disjoint::services::default_strategy - < - Segment, Box - >::type strategy_type; - return ! dispatch::disjoint<Segment, Box>::apply(segment, box, strategy_type()); + return ! dispatch::disjoint<Segment, Box>::apply(segment, box, m_strategy); } + + DisjointStrategy const& m_strategy; }; template <typename PtSegStrategy> @@ -172,13 +173,15 @@ private: {} template <typename Item1, typename Item2> - inline void apply(Item1 const& item1, Item2 const& item2) + inline bool apply(Item1 const& item1, Item2 const& item2) { if (! m_intersection_found && ! dispatch::disjoint<Item1, Item2>::apply(item1, item2, m_strategy)) { m_intersection_found = true; + return false; } + return true; } inline bool intersection_found() const { return m_intersection_found; } @@ -219,12 +222,22 @@ public: { item_visitor_type<Strategy> visitor(strategy); + typedef typename Strategy::envelope_strategy_type envelope_strategy_type; + typedef typename Strategy::disjoint_strategy_type disjoint_strategy_type; + + // TODO: disjoint Segment/Box may be called in partition multiple times + // possibly for non-cartesian segments which could be slow. We should consider + // passing a range of bounding boxes of segments after calculating them once. + // Alternatively instead of a range of segments a range of Segment/Envelope pairs + // should be passed, where envelope would be lazily calculated when needed the first time geometry::partition < 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()); + expand_box_point(), + overlaps_box_point(), + expand_box_segment<envelope_strategy_type>(strategy.get_envelope_strategy()), + overlaps_box_segment<disjoint_strategy_type>(strategy.get_disjoint_strategy())); return ! visitor.intersection_found(); } @@ -237,6 +250,176 @@ public: }; +template <typename MultiPoint, typename SingleGeometry> +class multi_point_single_geometry +{ +public: + template <typename Strategy> + static inline bool apply(MultiPoint const& multi_point, SingleGeometry const& single_geometry, Strategy const& strategy) + { + typedef typename point_type<MultiPoint>::type point1_type; + typedef typename point_type<SingleGeometry>::type point2_type; + typedef model::box<point2_type> box2_type; + + box2_type box2; + geometry::envelope(single_geometry, box2, strategy.get_envelope_strategy()); + geometry::detail::expand_by_epsilon(box2); + + typedef typename boost::range_const_iterator<MultiPoint>::type iterator; + for ( iterator it = boost::begin(multi_point) ; it != boost::end(multi_point) ; ++it ) + { + // The default strategy is enough for Point/Box + if (! detail::disjoint::disjoint_point_box(*it, box2) + && ! dispatch::disjoint<point1_type, SingleGeometry>::apply(*it, single_geometry, strategy)) + { + return false; + } + } + + return true; + } + + template <typename Strategy> + static inline bool apply(SingleGeometry const& single_geometry, MultiPoint const& multi_point, Strategy const& strategy) + { + return apply(multi_point, single_geometry, strategy); + } +}; + + +template <typename MultiPoint, typename MultiGeometry> +class multi_point_multi_geometry +{ +private: + struct expand_box_point + { + template <typename Box, typename Point> + static inline void apply(Box& total, Point const& point) + { + geometry::expand(total, point); + } + }; + + struct expand_box_box_pair + { + template <typename Box, typename BoxPair> + inline void apply(Box& total, BoxPair const& box_pair) const + { + geometry::expand(total, box_pair.first); + } + }; + + struct overlaps_box_point + { + template <typename Box, typename Point> + static inline bool apply(Box const& box, Point const& point) + { + // The default strategy is enough for Point/Box + return ! detail::disjoint::disjoint_point_box(point, box); + } + }; + + struct overlaps_box_box_pair + { + template <typename Box, typename BoxPair> + inline bool apply(Box const& box, BoxPair const& box_pair) const + { + // The default strategy is enough for Box/Box + return ! detail::disjoint::disjoint_box_box(box_pair.first, box); + } + }; + + template <typename PtSegStrategy> + class item_visitor_type + { + public: + item_visitor_type(MultiGeometry const& multi_geometry, + PtSegStrategy const& strategy) + : m_intersection_found(false) + , m_multi_geometry(multi_geometry) + , m_strategy(strategy) + {} + + template <typename Point, typename BoxPair> + inline bool apply(Point const& point, BoxPair const& box_pair) + { + typedef typename boost::range_value<MultiGeometry>::type single_type; + + // The default strategy is enough for Point/Box + if (! m_intersection_found + && ! detail::disjoint::disjoint_point_box(point, box_pair.first) + && ! dispatch::disjoint<Point, single_type>::apply(point, range::at(m_multi_geometry, box_pair.second), m_strategy)) + { + m_intersection_found = true; + return false; + } + return true; + } + + inline bool intersection_found() const { return m_intersection_found; } + + private: + bool m_intersection_found; + MultiGeometry const& m_multi_geometry; + PtSegStrategy const& m_strategy; + }; + // structs for partition -- end + +public: + template <typename Strategy> + static inline bool apply(MultiPoint const& multi_point, MultiGeometry const& multi_geometry, Strategy const& strategy) + { + typedef typename point_type<MultiPoint>::type point1_type; + typedef typename point_type<MultiGeometry>::type point2_type; + typedef model::box<point1_type> box1_type; + typedef model::box<point2_type> box2_type; + typedef std::pair<box2_type, std::size_t> box_pair_type; + + typename Strategy::envelope_strategy_type const + envelope_strategy = strategy.get_envelope_strategy(); + + std::size_t count2 = boost::size(multi_geometry); + std::vector<box_pair_type> boxes(count2); + for (std::size_t i = 0 ; i < count2 ; ++i) + { + geometry::envelope(range::at(multi_geometry, i), boxes[i].first, envelope_strategy); + geometry::detail::expand_by_epsilon(boxes[i].first); + boxes[i].second = i; + } + + item_visitor_type<Strategy> visitor(multi_geometry, strategy); + + geometry::partition + < + box1_type + >::apply(multi_point, boxes, visitor, + expand_box_point(), + overlaps_box_point(), + expand_box_box_pair(), + overlaps_box_box_pair()); + + return ! visitor.intersection_found(); + } + + template <typename Strategy> + static inline bool apply(MultiGeometry const& multi_geometry, MultiPoint const& multi_point, Strategy const& strategy) + { + return apply(multi_point, multi_geometry, strategy); + } +}; + + +template <typename MultiPoint, typename Areal, typename Tag = typename tag<Areal>::type> +struct multipoint_areal + : multi_point_single_geometry<MultiPoint, Areal> +{}; + +template <typename MultiPoint, typename Areal> +struct multipoint_areal<MultiPoint, Areal, multi_polygon_tag> + : multi_point_multi_geometry<MultiPoint, Areal> +{}; + + }} // namespace detail::disjoint #endif // DOXYGEN_NO_DETAIL @@ -321,6 +504,22 @@ struct disjoint {}; +template <typename Areal, typename MultiPoint, std::size_t DimensionCount> +struct disjoint + < + Areal, MultiPoint, DimensionCount, areal_tag, multi_point_tag, false + > : detail::disjoint::multipoint_areal<MultiPoint, Areal> +{}; + + +template <typename MultiPoint, typename Areal, std::size_t DimensionCount> +struct disjoint + < + MultiPoint, Areal, DimensionCount, multi_point_tag, areal_tag, false + > : detail::disjoint::multipoint_areal<MultiPoint, Areal> +{}; + + } // namespace dispatch #endif // DOXYGEN_NO_DISPATCH diff --git a/boost/geometry/algorithms/detail/disjoint/segment_box.hpp b/boost/geometry/algorithms/detail/disjoint/segment_box.hpp index c2741ce72c..fe849e1091 100644 --- a/boost/geometry/algorithms/detail/disjoint/segment_box.hpp +++ b/boost/geometry/algorithms/detail/disjoint/segment_box.hpp @@ -8,8 +8,9 @@ // 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 Vissarion Fysikopoulos, on behalf of Oracle // Contributed and/or modified by Menelaos Karavelas, on behalf of Oracle +// Contributed and/or modified by Adam Wulkiewicz, on behalf of Oracle // Parts of Boost.Geometry are redesigned from Geodan's Geographic Library // (geolib/GGL), copyright (c) 1995-2010 Geodan, Amsterdam, the Netherlands. @@ -24,9 +25,18 @@ #include <cstddef> #include <boost/geometry/core/tags.hpp> +#include <boost/geometry/core/radian_access.hpp> +#include <boost/geometry/algorithms/detail/assign_indexed_point.hpp> +#include <boost/geometry/algorithms/detail/disjoint/point_box.hpp> +#include <boost/geometry/algorithms/detail/disjoint/box_box.hpp> +#include <boost/geometry/algorithms/detail/envelope/segment.hpp> +#include <boost/geometry/algorithms/detail/normalize.hpp> #include <boost/geometry/algorithms/dispatch/disjoint.hpp> +#include <boost/geometry/formulas/vertex_longitude.hpp> + +#include <boost/geometry/geometries/box.hpp> namespace boost { namespace geometry { @@ -36,10 +46,161 @@ namespace boost { namespace geometry namespace detail { namespace disjoint { +template <typename CS_Tag> +struct disjoint_segment_box_sphere_or_spheroid +{ +private: + + template <typename CT> + static inline void swap(CT& lon1, + CT& lat1, + CT& lon2, + CT& lat2) + { + std::swap(lon1, lon2); + std::swap(lat1, lat2); + } + + +public: + + template <typename Segment, typename Box, typename Strategy> + static inline bool apply(Segment const& segment, + Box const& box, + Strategy const& azimuth_strategy) + { + assert_dimension_equal<Segment, Box>(); + + typedef typename point_type<Segment>::type segment_point_type; + typedef typename cs_tag<Segment>::type segment_cs_type; + + segment_point_type p0, p1; + geometry::detail::assign_point_from_index<0>(segment, p0); + geometry::detail::assign_point_from_index<1>(segment, p1); + + // Simplest cases first + + // Case 1: if box contains one of segment's endpoints then they are not disjoint + if (! disjoint_point_box(p0, box) || ! disjoint_point_box(p1, box)) + { + return false; + } + + // Case 2: disjoint if bounding boxes are disjoint + + typedef typename coordinate_type<segment_point_type>::type CT; + + segment_point_type p0_normalized = + geometry::detail::return_normalized<segment_point_type>(p0); + segment_point_type p1_normalized = + geometry::detail::return_normalized<segment_point_type>(p1); + + CT lon1 = geometry::get_as_radian<0>(p0_normalized); + CT lat1 = geometry::get_as_radian<1>(p0_normalized); + CT lon2 = geometry::get_as_radian<0>(p1_normalized); + CT lat2 = geometry::get_as_radian<1>(p1_normalized); + + if (lon1 > lon2) + { + swap(lon1, lat1, lon2, lat2); + } + + //Compute alp1 outside envelope and pass it to envelope_segment_impl + //in order for it to be used later in the algorithm + CT alp1; + + azimuth_strategy.apply(lon1, lat1, lon2, lat2, alp1); + + geometry::model::box<segment_point_type> box_seg; + + geometry::detail::envelope::envelope_segment_impl<segment_cs_type> + ::template apply<geometry::radian>(lon1, lat1, + lon2, lat2, + box_seg, + azimuth_strategy, + alp1); + if (disjoint_box_box(box, box_seg)) + { + return true; + } + + // Case 3: test intersection by comparing angles + + CT a_b0, a_b1, a_b2, a_b3; + + CT b_lon_min = geometry::get_as_radian<geometry::min_corner, 0>(box); + CT b_lat_min = geometry::get_as_radian<geometry::min_corner, 1>(box); + CT b_lon_max = geometry::get_as_radian<geometry::max_corner, 0>(box); + CT b_lat_max = geometry::get_as_radian<geometry::max_corner, 1>(box); + + azimuth_strategy.apply(lon1, lat1, b_lon_min, b_lat_min, a_b0); + azimuth_strategy.apply(lon1, lat1, b_lon_max, b_lat_min, a_b1); + azimuth_strategy.apply(lon1, lat1, b_lon_min, b_lat_max, a_b2); + azimuth_strategy.apply(lon1, lat1, b_lon_max, b_lat_max, a_b3); + + bool b0 = alp1 > a_b0; + bool b1 = alp1 > a_b1; + bool b2 = alp1 > a_b2; + bool b3 = alp1 > a_b3; + + // if not all box points on the same side of the segment then + // there is an intersection + if (!(b0 && b1 && b2 && b3) && (b0 || b1 || b2 || b3)) + { + return false; + } + + // Case 4: The only intersection case not covered above is when all four + // points of the box are above (below) the segment in northern (southern) + // hemisphere. Then we have to compute the vertex of the segment + + CT vertex_lat; + CT lat_sum = lat1 + lat2; + + if ((b0 && b1 && b2 && b3 && lat_sum > CT(0)) + || (!(b0 && b1 && b2 && b3) && lat_sum < CT(0))) + { + CT b_lat_below; //latitude of box closest to equator + + if (lat_sum > CT(0)) + { + vertex_lat = geometry::get_as_radian<geometry::max_corner, 1>(box_seg); + b_lat_below = b_lat_min; + } else { + vertex_lat = geometry::get_as_radian<geometry::min_corner, 1>(box_seg); + b_lat_below = b_lat_max; + } + + //optimization TODO: computing the spherical longitude should suffice for + // the majority of cases + CT vertex_lon = geometry::formula::vertex_longitude<CT, CS_Tag> + ::apply(lon1, lat1, + lon2, lat2, + vertex_lat, + alp1, + azimuth_strategy); + + // Check if the vertex point is within the band defined by the + // minimum and maximum longitude of the box; if yes, then return + // false if the point is above the min latitude of the box; return + // true in all other cases + if (vertex_lon >= b_lon_min && vertex_lon <= b_lon_max + && std::abs(vertex_lat) > std::abs(b_lat_below)) + { + return false; + } + } + + return true; + } +}; + struct disjoint_segment_box { template <typename Segment, typename Box, typename Strategy> - static inline bool apply(Segment const& segment, Box const& box, Strategy const& strategy) + static inline bool apply(Segment const& segment, + Box const& box, + Strategy const& strategy) { return strategy.apply(segment, box); } @@ -56,7 +217,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 + : detail::disjoint::disjoint_segment_box {}; |