diff options
Diffstat (limited to 'boost/geometry/algorithms/detail/relate')
5 files changed, 791 insertions, 124 deletions
diff --git a/boost/geometry/algorithms/detail/relate/implementation.hpp b/boost/geometry/algorithms/detail/relate/implementation.hpp index 3bd0f806c1..8f7942d46e 100644 --- a/boost/geometry/algorithms/detail/relate/implementation.hpp +++ b/boost/geometry/algorithms/detail/relate/implementation.hpp @@ -23,6 +23,7 @@ #include <boost/geometry/algorithms/detail/relate/point_geometry.hpp> #include <boost/geometry/algorithms/detail/relate/linear_linear.hpp> #include <boost/geometry/algorithms/detail/relate/linear_areal.hpp> +#include <boost/geometry/algorithms/detail/relate/multi_point_geometry.hpp> #include <boost/geometry/algorithms/detail/relate/areal_areal.hpp> #include <boost/geometry/strategies/intersection.hpp> @@ -81,6 +82,16 @@ struct relate<Geometry, Point, Tag1, point_tag, TopDim1, 0, true> : detail::relate::geometry_point<Geometry, Point> {}; +template <typename MultiPoint, typename Geometry, typename Tag2, int TopDim2> +struct relate<MultiPoint, Geometry, multi_point_tag, Tag2, 0, TopDim2, false> + : detail::relate::multi_point_geometry<MultiPoint, Geometry> +{}; + +template <typename Geometry, typename MultiPoint, typename Tag1, int TopDim1> +struct relate<Geometry, MultiPoint, Tag1, multi_point_tag, TopDim1, 0, false> + : detail::relate::geometry_multi_point<Geometry, MultiPoint> +{}; + template <typename Linear1, typename Linear2, typename Tag1, typename Tag2> struct relate<Linear1, Linear2, Tag1, Tag2, 1, 1, true> diff --git a/boost/geometry/algorithms/detail/relate/multi_point_geometry.hpp b/boost/geometry/algorithms/detail/relate/multi_point_geometry.hpp new file mode 100644 index 0000000000..47c6963b87 --- /dev/null +++ b/boost/geometry/algorithms/detail/relate/multi_point_geometry.hpp @@ -0,0 +1,568 @@ +// Boost.Geometry + +// Copyright (c) 2017 Oracle and/or its affiliates. + +// Contributed and/or modified by Adam Wulkiewicz, on behalf of Oracle + +// Use, modification and distribution is subject to the Boost Software License, +// Version 1.0. (See accompanying file LICENSE_1_0.txt or copy at +// http://www.boost.org/LICENSE_1_0.txt) + +#ifndef BOOST_GEOMETRY_ALGORITHMS_DETAIL_RELATE_MULTI_POINT_GEOMETRY_HPP +#define BOOST_GEOMETRY_ALGORITHMS_DETAIL_RELATE_MULTI_POINT_GEOMETRY_HPP + + +#include <boost/range.hpp> + +#include <boost/geometry/algorithms/detail/disjoint/box_box.hpp> +#include <boost/geometry/algorithms/detail/disjoint/point_box.hpp> +#include <boost/geometry/algorithms/detail/expand_by_epsilon.hpp> +#include <boost/geometry/algorithms/detail/relate/result.hpp> +#include <boost/geometry/algorithms/detail/relate/topology_check.hpp> +#include <boost/geometry/algorithms/detail/within/point_in_geometry.hpp> +#include <boost/geometry/algorithms/envelope.hpp> + +#include <boost/geometry/core/is_areal.hpp> +#include <boost/geometry/core/point_type.hpp> + +#include <boost/geometry/geometries/box.hpp> + +#include <boost/geometry/index/rtree.hpp> + + +namespace boost { namespace geometry +{ + +#ifndef DOXYGEN_NO_DETAIL +namespace detail { namespace relate +{ + +template +< + typename Geometry, + typename Tag = typename tag<Geometry>::type +> +struct multi_point_geometry_eb +{ + template <typename MultiPoint> + static inline bool apply(MultiPoint const& , + detail::relate::topology_check<Geometry> const& ) + { + return true; + } +}; + +template <typename Geometry> +struct multi_point_geometry_eb<Geometry, linestring_tag> +{ + template <typename Points> + struct boundary_visitor + { + boundary_visitor(Points const& points) + : m_points(points) + , m_boundary_found(false) + {} + + template <typename Point> + struct find_pred + { + find_pred(Point const& point) + : m_point(point) + {} + + template <typename Pt> + bool operator()(Pt const& pt) const + { + return detail::equals::equals_point_point(pt, m_point); + } + + Point const& m_point; + }; + + template <typename Point> + bool apply(Point const& boundary_point) + { + if (std::find_if(m_points.begin(), m_points.end(), find_pred<Point>(boundary_point)) == m_points.end()) + { + m_boundary_found = true; + return false; + } + return true; + } + + bool result() const { return m_boundary_found; } + + private: + Points const& m_points; + bool m_boundary_found; + }; + + template <typename MultiPoint> + static inline bool apply(MultiPoint const& multi_point, + detail::relate::topology_check<Geometry> const& tc) + { + boundary_visitor<MultiPoint> visitor(multi_point); + tc.for_each_boundary_point(visitor); + return visitor.result(); + } +}; + +template <typename Geometry> +struct multi_point_geometry_eb<Geometry, multi_linestring_tag> +{ + template <typename Points> + struct boundary_visitor + { + boundary_visitor(Points const& points) + : m_points(points) + , m_boundary_found(false) + {} + + template <typename Point> + bool apply(Point const& boundary_point) + { + if (! std::binary_search(m_points.begin(), m_points.end(), boundary_point, relate::less())) + { + m_boundary_found = true; + return false; + } + return true; + } + + bool result() const { return m_boundary_found; } + + private: + Points const& m_points; + bool m_boundary_found; + }; + + template <typename MultiPoint> + static inline bool apply(MultiPoint const& multi_point, + detail::relate::topology_check<Geometry> const& tc) + { + typedef typename boost::range_value<MultiPoint>::type point_type; + typedef std::vector<point_type> points_type; + points_type points(boost::begin(multi_point), boost::end(multi_point)); + std::sort(points.begin(), points.end(), relate::less()); + + boundary_visitor<points_type> visitor(points); + tc.for_each_boundary_point(visitor); + return visitor.result(); + } +}; + +// SingleGeometry - Linear or Areal +template <typename MultiPoint, typename SingleGeometry, bool Transpose = false> +struct multi_point_single_geometry +{ + static const bool interruption_enabled = true; + + template <typename Result, typename Strategy> + static inline void apply(MultiPoint const& multi_point, + SingleGeometry const& single_geometry, + Result & result, + Strategy const& strategy) + { + 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 ) + { + if (! (relate::may_update<interior, interior, '0', Transpose>(result) + || relate::may_update<interior, boundary, '0', Transpose>(result) + || relate::may_update<interior, exterior, '0', Transpose>(result) ) ) + { + break; + } + + // The default strategy is enough for Point/Box + if (detail::disjoint::disjoint_point_box(*it, box2)) + { + relate::set<interior, exterior, '0', Transpose>(result); + } + else + { + int in_val = detail::within::point_in_geometry(*it, single_geometry, strategy); + + if (in_val > 0) // within + { + relate::set<interior, interior, '0', Transpose>(result); + } + else if (in_val == 0) + { + relate::set<interior, boundary, '0', Transpose>(result); + } + else // in_val < 0 - not within + { + relate::set<interior, exterior, '0', Transpose>(result); + } + } + + if ( BOOST_GEOMETRY_CONDITION(result.interrupt) ) + { + return; + } + } + + typedef detail::relate::topology_check<SingleGeometry> tc_t; + if ( relate::may_update<exterior, interior, tc_t::interior, Transpose>(result) + || relate::may_update<exterior, boundary, tc_t::boundary, Transpose>(result) ) + { + tc_t tc(single_geometry); + + if ( relate::may_update<exterior, interior, tc_t::interior, Transpose>(result) + && tc.has_interior() ) + { + // TODO: this is not true if a linestring is degenerated to a point + // then the interior has topological dimension = 0, not 1 + relate::set<exterior, interior, tc_t::interior, Transpose>(result); + } + + if ( relate::may_update<exterior, boundary, tc_t::boundary, Transpose>(result) + && tc.has_boundary() ) + { + if (multi_point_geometry_eb<SingleGeometry>::apply(multi_point, tc)) + relate::set<exterior, boundary, tc_t::boundary, Transpose>(result); + } + } + + relate::set<exterior, exterior, result_dimension<MultiPoint>::value, Transpose>(result); + } +}; + + +// MultiGeometry - Linear or Areal +// part of the algorithm calculating II and IB when no IE has to be calculated +// using partition() +template <typename MultiPoint, typename MultiGeometry, bool Transpose> +class multi_point_multi_geometry_ii_ib +{ + 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> + static inline void apply(Box& total, BoxPair const& box_pair) + { + 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> + static inline bool apply(Box const& box, BoxPair const& box_pair) + { + // The default strategy is enough for Box/Box + return ! detail::disjoint::disjoint_box_box(box_pair.first, box); + } + }; + + template <typename Result, typename PtSegStrategy> + class item_visitor_type + { + public: + item_visitor_type(MultiGeometry const& multi_geometry, + detail::relate::topology_check<MultiGeometry> const& tc, + Result & result, + PtSegStrategy const& strategy) + : m_multi_geometry(multi_geometry) + , m_tc(tc) + , m_result(result) + , m_strategy(strategy) + {} + + template <typename Point, typename BoxPair> + inline bool apply(Point const& point, BoxPair const& box_pair) + { + // The default strategy is enough for Point/Box + if (! detail::disjoint::disjoint_point_box(point, box_pair.first)) + { + typename boost::range_value<MultiGeometry>::type const& + single = range::at(m_multi_geometry, box_pair.second); + + int in_val = detail::within::point_in_geometry(point, single, m_strategy); + + if (in_val > 0) // within + { + relate::set<interior, interior, '0', Transpose>(m_result); + } + else if (in_val == 0) + { + if (m_tc.check_boundary_point(point)) + relate::set<interior, boundary, '0', Transpose>(m_result); + else + relate::set<interior, interior, '0', Transpose>(m_result); + } + } + + if ( BOOST_GEOMETRY_CONDITION(m_result.interrupt) ) + { + return false; + } + + if (! (relate::may_update<interior, interior, '0', Transpose>(m_result) + || relate::may_update<interior, boundary, '0', Transpose>(m_result) ) ) + { + return false; + } + + return true; + } + + + private: + MultiGeometry const& m_multi_geometry; + detail::relate::topology_check<MultiGeometry> const& m_tc; + Result & m_result; + PtSegStrategy const& m_strategy; + }; + +public: + 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; + + template <typename Result, typename Strategy> + static inline void apply(MultiPoint const& multi_point, + MultiGeometry const& multi_geometry, + std::vector<box_pair_type> const& boxes, + detail::relate::topology_check<MultiGeometry> const& tc, + Result & result, + Strategy const& strategy) + { + item_visitor_type<Result, Strategy> visitor(multi_geometry, tc, result, strategy); + + geometry::partition + < + box1_type + >::apply(multi_point, boxes, visitor, + expand_box_point(), + overlaps_box_point(), + expand_box_box_pair(), + overlaps_box_box_pair()); + } + +}; + +// MultiGeometry - Linear or Areal +// part of the algorithm calculating II, IB and IE +// using rtree +template <typename MultiPoint, typename MultiGeometry, bool Transpose> +struct multi_point_multi_geometry_ii_ib_ie +{ + 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; + typedef std::vector<box_pair_type> boxes_type; + typedef typename boxes_type::const_iterator boxes_iterator; + + template <typename Result, typename Strategy> + static inline void apply(MultiPoint const& multi_point, + MultiGeometry const& multi_geometry, + std::vector<box_pair_type> const& boxes, + detail::relate::topology_check<MultiGeometry> const& tc, + Result & result, + Strategy const& strategy) + { + index::rtree<box_pair_type, index::rstar<4> > rt(boxes.begin(), boxes.end()); + + typedef typename boost::range_const_iterator<MultiPoint>::type iterator; + for ( iterator it = boost::begin(multi_point) ; it != boost::end(multi_point) ; ++it ) + { + if (! (relate::may_update<interior, interior, '0', Transpose>(result) + || relate::may_update<interior, boundary, '0', Transpose>(result) + || relate::may_update<interior, exterior, '0', Transpose>(result) ) ) + { + return; + } + + typename boost::range_value<MultiPoint>::type const& point = *it; + + boxes_type boxes_found; + rt.query(index::intersects(point), std::back_inserter(boxes_found)); + + bool found_ii_or_ib = false; + for (boxes_iterator bi = boxes_found.begin() ; bi != boxes_found.end() ; ++bi) + { + typename boost::range_value<MultiGeometry>::type const& + single = range::at(multi_geometry, bi->second); + + int in_val = detail::within::point_in_geometry(point, single, strategy); + + if (in_val > 0) // within + { + relate::set<interior, interior, '0', Transpose>(result); + found_ii_or_ib = true; + } + else if (in_val == 0) // on boundary of single + { + if (tc.check_boundary_point(point)) + relate::set<interior, boundary, '0', Transpose>(result); + else + relate::set<interior, interior, '0', Transpose>(result); + found_ii_or_ib = true; + } + } + + // neither interior nor boundary found -> exterior + if (found_ii_or_ib == false) + { + relate::set<interior, exterior, '0', Transpose>(result); + } + + if ( BOOST_GEOMETRY_CONDITION(result.interrupt) ) + { + return; + } + } + } +}; + +// MultiGeometry - Linear or Areal +template <typename MultiPoint, typename MultiGeometry, bool Transpose = false> +struct multi_point_multi_geometry +{ + static const bool interruption_enabled = true; + + template <typename Result, typename Strategy> + static inline void apply(MultiPoint const& multi_point, + MultiGeometry const& multi_geometry, + Result & result, + Strategy const& strategy) + { + typedef typename point_type<MultiGeometry>::type point2_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; + } + + typedef detail::relate::topology_check<MultiGeometry> tc_t; + tc_t tc(multi_geometry); + + if ( relate::may_update<interior, interior, '0', Transpose>(result) + || relate::may_update<interior, boundary, '0', Transpose>(result) + || relate::may_update<interior, exterior, '0', Transpose>(result) ) + { + // If there is no need to calculate IE, use partition + if (! relate::may_update<interior, exterior, '0', Transpose>(result) ) + { + multi_point_multi_geometry_ii_ib<MultiPoint, MultiGeometry, Transpose> + ::apply(multi_point, multi_geometry, boxes, tc, result, strategy); + } + else // otherwise use rtree + { + multi_point_multi_geometry_ii_ib_ie<MultiPoint, MultiGeometry, Transpose> + ::apply(multi_point, multi_geometry, boxes, tc, result, strategy); + } + } + + if ( BOOST_GEOMETRY_CONDITION(result.interrupt) ) + { + return; + } + + if ( relate::may_update<exterior, interior, tc_t::interior, Transpose>(result) + || relate::may_update<exterior, boundary, tc_t::boundary, Transpose>(result) ) + { + if ( relate::may_update<exterior, interior, tc_t::interior, Transpose>(result) + && tc.has_interior() ) + { + // TODO: this is not true if a linestring is degenerated to a point + // then the interior has topological dimension = 0, not 1 + relate::set<exterior, interior, tc_t::interior, Transpose>(result); + } + + if ( relate::may_update<exterior, boundary, tc_t::boundary, Transpose>(result) + && tc.has_boundary() ) + { + if (multi_point_geometry_eb<MultiGeometry>::apply(multi_point, tc)) + relate::set<exterior, boundary, tc_t::boundary, Transpose>(result); + } + } + + relate::set<exterior, exterior, result_dimension<MultiPoint>::value, Transpose>(result); + } + +}; + + +template +< + typename MultiPoint, typename Geometry, + bool Transpose = false, + bool isMulti = boost::is_same + < + typename tag_cast + < + typename tag<Geometry>::type, multi_tag + >::type, + multi_tag + >::value +> +struct multi_point_geometry + : multi_point_single_geometry<MultiPoint, Geometry, Transpose> +{}; + +template <typename MultiPoint, typename Geometry, bool Transpose> +struct multi_point_geometry<MultiPoint, Geometry, Transpose, true> + : multi_point_multi_geometry<MultiPoint, Geometry, Transpose> +{}; + + +// transposed result of multi_point_geometry +template <typename Geometry, typename MultiPoint> +struct geometry_multi_point +{ + static const bool interruption_enabled = true; + + template <typename Result, typename Strategy> + static inline void apply(Geometry const& geometry, MultiPoint const& multi_point, + Result & result, Strategy const& strategy) + { + multi_point_geometry<MultiPoint, Geometry, true>::apply(multi_point, geometry, result, strategy); + } +}; + +}} // namespace detail::relate +#endif // DOXYGEN_NO_DETAIL + +}} // namespace boost::geometry + +#endif // BOOST_GEOMETRY_ALGORITHMS_DETAIL_RELATE_MULTI_POINT_GEOMETRY_HPP diff --git a/boost/geometry/algorithms/detail/relate/point_geometry.hpp b/boost/geometry/algorithms/detail/relate/point_geometry.hpp index a0c6c0d49b..e78a404b21 100644 --- a/boost/geometry/algorithms/detail/relate/point_geometry.hpp +++ b/boost/geometry/algorithms/detail/relate/point_geometry.hpp @@ -60,29 +60,27 @@ struct point_geometry if ( BOOST_GEOMETRY_CONDITION(result.interrupt) ) return; - // the point is on the boundary - if ( pig == 0 ) + typedef detail::relate::topology_check<Geometry> tc_t; + if ( relate::may_update<exterior, interior, tc_t::interior, Transpose>(result) + || relate::may_update<exterior, boundary, tc_t::boundary, Transpose>(result) ) { - // NOTE: even for MLs, if there is at least one boundary point, - // somewhere there must be another one - - // check if there are other boundaries outside - typedef detail::relate::topology_check<Geometry> tc_t; - //tc_t tc(geometry, point); - //if ( tc.has_interior ) - relate::set<exterior, interior, tc_t::interior, Transpose>(result); - //if ( tc.has_boundary ) - relate::set<exterior, boundary, tc_t::boundary, Transpose>(result); - } - else - { - // check if there is a boundary in Geometry - typedef detail::relate::topology_check<Geometry> tc_t; - tc_t tc(geometry); - if ( tc.has_interior ) + // the point is on the boundary + if ( pig == 0 ) + { + // NOTE: even for MLs, if there is at least one boundary point, + // somewhere there must be another one relate::set<exterior, interior, tc_t::interior, Transpose>(result); - if ( tc.has_boundary ) relate::set<exterior, boundary, tc_t::boundary, Transpose>(result); + } + else + { + // check if there is a boundary in Geometry + tc_t tc(geometry); + if ( tc.has_interior() ) + relate::set<exterior, interior, tc_t::interior, Transpose>(result); + if ( tc.has_boundary() ) + relate::set<exterior, boundary, tc_t::boundary, Transpose>(result); + } } } }; diff --git a/boost/geometry/algorithms/detail/relate/point_point.hpp b/boost/geometry/algorithms/detail/relate/point_point.hpp index b41d346f0b..68d8be031e 100644 --- a/boost/geometry/algorithms/detail/relate/point_point.hpp +++ b/boost/geometry/algorithms/detail/relate/point_point.hpp @@ -165,22 +165,41 @@ struct multipoint_multipoint } } -// TODO: ADD A CHECK TO THE RESULT INDICATING IF THE FIRST AND/OR SECOND GEOMETRY MUST BE ANALYSED + // The geometry containing smaller number of points will be analysed first + if ( boost::size(multi_point1) < boost::size(multi_point2) ) + { + search_both<false>(multi_point1, multi_point2, result); + } + else + { + search_both<true>(multi_point2, multi_point1, result); + } -// TODO: if I/I is set for one MPt, this won't be changed when the other one in analysed -// so if e.g. only I/I must be analysed we musn't check the other MPt + relate::set<exterior, exterior, result_dimension<MultiPoint1>::value>(result); + } -// TODO: Also, the geometry with the smaller number of points may be analysed first - //if ( boost::size(multi_point1) < boost::size(multi_point2) ) + template <bool Transpose, typename MPt1, typename MPt2, typename Result> + static inline void search_both(MPt1 const& first_sorted_mpt, MPt2 const& first_iterated_mpt, + Result & result) + { + if ( relate::may_update<interior, interior, '0'>(result) + || relate::may_update<interior, exterior, '0'>(result) + || relate::may_update<exterior, interior, '0'>(result) ) + { + // NlogN + MlogN + bool is_disjoint = search<Transpose>(first_sorted_mpt, first_iterated_mpt, result); - // NlogN + MlogN - bool all_handled = search<false>(multi_point1, multi_point2, result); - - if ( BOOST_GEOMETRY_CONDITION(all_handled || result.interrupt) ) - return; + if ( BOOST_GEOMETRY_CONDITION(is_disjoint || result.interrupt) ) + return; + } - // MlogM + NlogM - search<true>(multi_point2, multi_point1, result); + if ( relate::may_update<interior, interior, '0'>(result) + || relate::may_update<interior, exterior, '0'>(result) + || relate::may_update<exterior, interior, '0'>(result) ) + { + // MlogM + NlogM + search<! Transpose>(first_iterated_mpt, first_sorted_mpt, result); + } } template <bool Transpose, @@ -215,9 +234,6 @@ struct multipoint_multipoint break; } - // an optimization - bool all_handled = false; - if ( found_inside ) // some point of MP2 is equal to some of MP1 { // TODO: if I/I is set for one MPt, this won't be changed when the other one in analysed @@ -234,14 +250,10 @@ struct multipoint_multipoint { relate::set<interior, exterior, '0', Transpose>(result); relate::set<exterior, interior, '0', Transpose>(result); - - // if no point is intersecting the other MPt then we musn't analyse the reversed case - all_handled = true; } - relate::set<exterior, exterior, result_dimension<point_type>::value, Transpose>(result); - - return all_handled; + // if no point is intersecting the other MPt then we musn't analyse the reversed case + return ! found_inside; } }; diff --git a/boost/geometry/algorithms/detail/relate/topology_check.hpp b/boost/geometry/algorithms/detail/relate/topology_check.hpp index caa8a3c22d..654999d8fb 100644 --- a/boost/geometry/algorithms/detail/relate/topology_check.hpp +++ b/boost/geometry/algorithms/detail/relate/topology_check.hpp @@ -1,22 +1,23 @@ // 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 Adam Wulkiewicz, on behalf of Oracle // Use, modification and distribution is subject to the Boost Software License, // Version 1.0. (See accompanying file LICENSE_1_0.txt or copy at // http://www.boost.org/LICENSE_1_0.txt) -// Contributed and/or modified by Adam Wulkiewicz, on behalf of Oracle - #ifndef BOOST_GEOMETRY_ALGORITHMS_DETAIL_RELATE_TOPOLOGY_CHECK_HPP #define BOOST_GEOMETRY_ALGORITHMS_DETAIL_RELATE_TOPOLOGY_CHECK_HPP -#include <boost/geometry/util/range.hpp> #include <boost/geometry/algorithms/detail/equals/point_point.hpp> -#include <boost/geometry/policies/compare.hpp> +#include <boost/geometry/algorithms/detail/relate/less.hpp> #include <boost/geometry/util/has_nan_coordinate.hpp> +#include <boost/geometry/util/range.hpp> + namespace boost { namespace geometry { @@ -51,31 +52,63 @@ struct topology_check<Linestring, linestring_tag> static const char interior = '1'; static const char boundary = '0'; - bool has_interior; - bool has_boundary; - topology_check(Linestring const& ls) + : m_ls(ls) + , m_is_initialized(false) + {} + + bool has_interior() const { - init(ls, 0); /*dummy param*/ + init(); + return m_has_interior; } - template <typename IgnoreBoundaryPoint> - topology_check(Linestring const& ls, IgnoreBoundaryPoint const& ibp) + bool has_boundary() const { - init(ls, ibp); /*dummy param, won't be used*/ + init(); + return m_has_boundary; } - // Even if some point is on the boundary, if the Linestring has the boundary, - // there will be second boundary point different than IgnoreBoundaryPoint - template <typename IgnoreBoundaryPoint> - void init(Linestring const& ls, IgnoreBoundaryPoint const&) + /*template <typename Point> + bool check_boundary_point(Point const& point) const { - std::size_t count = boost::size(ls); - has_interior = count > 0; + init(); + return m_has_boundary + && ( equals::equals_point_point(point, range::front(m_ls)) + || equals::equals_point_point(point, range::back(m_ls)) ); + }*/ + + template <typename Visitor> + void for_each_boundary_point(Visitor & visitor) const + { + init(); + if (m_has_boundary) + { + if (visitor.apply(range::front(m_ls))) + visitor.apply(range::back(m_ls)); + } + } + +private: + void init() const + { + if (m_is_initialized) + return; + + std::size_t count = boost::size(m_ls); + m_has_interior = count > 0; // NOTE: Linestring with all points equal is treated as 1d linear ring - has_boundary = count > 1 - && ! detail::equals::equals_point_point(range::front(ls), range::back(ls)); + m_has_boundary = count > 1 + && ! detail::equals::equals_point_point(range::front(m_ls), range::back(m_ls)); + + m_is_initialized = true; } + + Linestring const& m_ls; + mutable bool m_is_initialized; + + mutable bool m_has_interior; + mutable bool m_has_boundary; }; template <typename MultiLinestring> @@ -84,29 +117,58 @@ struct topology_check<MultiLinestring, multi_linestring_tag> static const char interior = '1'; static const char boundary = '0'; - bool has_interior; - bool has_boundary; - topology_check(MultiLinestring const& mls) + : m_mls(mls) + , m_is_initialized(false) + {} + + bool has_interior() const { - init(mls, not_ignoring_counter()); + init(); + return m_has_interior; } - template <typename IgnoreBoundaryPoint> - topology_check(MultiLinestring const& mls, IgnoreBoundaryPoint const& ibp) + bool has_boundary() const { - init(mls, ignoring_counter<IgnoreBoundaryPoint>(ibp)); + init(); + return m_has_boundary; } - template <typename OddCounter> - void init(MultiLinestring const& mls, OddCounter const& odd_counter) + template <typename Point> + bool check_boundary_point(Point const& point) const { - typedef typename geometry::point_type<MultiLinestring>::type point_type; - std::vector<point_type> endpoints; - endpoints.reserve(boost::size(mls) * 2); + init(); + + if (! m_has_boundary) + return false; + + std::size_t count = count_equal(m_endpoints.begin(), m_endpoints.end(), point); + + return count % 2 != 0; // odd count -> boundary + } + + template <typename Visitor> + void for_each_boundary_point(Visitor & visitor) const + { + init(); + if (m_has_boundary) + { + for_each_boundary_point(m_endpoints.begin(), m_endpoints.end(), visitor); + } + } + +private: + void init() const + { + if (m_is_initialized) + return; + + m_endpoints.reserve(boost::size(m_mls) * 2); + + m_has_interior = false; typedef typename boost::range_iterator<MultiLinestring const>::type ls_iterator; - for ( ls_iterator it = boost::begin(mls) ; it != boost::end(mls) ; ++it ) + for ( ls_iterator it = boost::begin(m_mls) ; it != boost::end(m_mls) ; ++it ) { typename boost::range_reference<MultiLinestring const>::type ls = *it; @@ -115,7 +177,7 @@ struct topology_check<MultiLinestring, multi_linestring_tag> if (count > 0) { - has_interior = true; + m_has_interior = true; } if (count > 1) @@ -138,62 +200,59 @@ struct topology_check<MultiLinestring, multi_linestring_tag> // is not used anywhere in the code, still it's safer this way if (! geometry::has_nan_coordinate(front_pt)) { - endpoints.push_back(front_pt); + m_endpoints.push_back(front_pt); } if (! geometry::has_nan_coordinate(back_pt)) { - endpoints.push_back(back_pt); + m_endpoints.push_back(back_pt); } } } } - has_boundary = false; + m_has_boundary = false; - if ( !endpoints.empty() ) + if (! m_endpoints.empty() ) { - std::sort(endpoints.begin(), endpoints.end(), geometry::less<point_type>()); - has_boundary = odd_counter(endpoints.begin(), endpoints.end()); + std::sort(m_endpoints.begin(), m_endpoints.end(), relate::less()); + m_has_boundary = find_odd_count(m_endpoints.begin(), m_endpoints.end()); } + + m_is_initialized = true; } - struct not_ignoring_counter + template <typename It, typename Point> + static inline std::size_t count_equal(It first, It last, Point const& point) { - template <typename It> - bool operator()(It first, It last) const - { - return find_odd_count(first, last); - } - }; + std::pair<It, It> rng = std::equal_range(first, last, point, relate::less()); + return (std::size_t)std::distance(rng.first, rng.second); + } - template <typename Point> - struct ignoring_counter + template <typename It> + static inline bool find_odd_count(It first, It last) { - ignoring_counter(Point const& pt) : m_pt(pt) {} + interrupting_visitor visitor; + for_each_boundary_point(first, last, visitor); + return visitor.found; + } - template <typename It> - bool operator()(It first, It last) const + struct interrupting_visitor + { + bool found; + interrupting_visitor() : found(false) {} + template <typename Point> + bool apply(Point const&) { - typedef typename std::iterator_traits<It>::value_type point_type; - - std::pair<It, It> ignore_range - = std::equal_range(first, last, m_pt, - geometry::less<point_type>()); - - if ( find_odd_count(first, ignore_range.first) ) - return true; - - return find_odd_count(ignore_range.second, last); + found = true; + return false; } - - Point const& m_pt; }; - template <typename It> - static inline bool find_odd_count(It first, It last) + template <typename It, typename Visitor> + static void for_each_boundary_point(It first, It last, Visitor& visitor) { if ( first == last ) - return false; + return; std::size_t count = 1; It prev = first; @@ -203,8 +262,14 @@ struct topology_check<MultiLinestring, multi_linestring_tag> // the end of the equal points subrange if ( ! equals::equals_point_point(*first, *prev) ) { + // odd count -> boundary if ( count % 2 != 0 ) - return true; + { + if (! visitor.apply(*prev)) + { + return; + } + } count = 1; } @@ -214,8 +279,22 @@ struct topology_check<MultiLinestring, multi_linestring_tag> } } - return count % 2 != 0; + // odd count -> boundary + if ( count % 2 != 0 ) + { + visitor.apply(*prev); + } } + +private: + MultiLinestring const& m_mls; + mutable bool m_is_initialized; + + mutable bool m_has_interior; + mutable bool m_has_boundary; + + typedef typename geometry::point_type<MultiLinestring>::type point_type; + mutable std::vector<point_type> m_endpoints; }; template <typename Ring> @@ -223,12 +302,11 @@ struct topology_check<Ring, ring_tag> { static const char interior = '2'; static const char boundary = '1'; - static const bool has_interior = true; - static const bool has_boundary = true; topology_check(Ring const&) {} - template <typename P> - topology_check(Ring const&, P const&) {} + + static bool has_interior() { return true; } + static bool has_boundary() { return true; } }; template <typename Polygon> @@ -236,12 +314,11 @@ struct topology_check<Polygon, polygon_tag> { static const char interior = '2'; static const char boundary = '1'; - static const bool has_interior = true; - static const bool has_boundary = true; - + topology_check(Polygon const&) {} - template <typename P> - topology_check(Polygon const&, P const&) {} + + static bool has_interior() { return true; } + static bool has_boundary() { return true; } }; template <typename MultiPolygon> @@ -249,12 +326,13 @@ struct topology_check<MultiPolygon, multi_polygon_tag> { static const char interior = '2'; static const char boundary = '1'; - static const bool has_interior = true; - static const bool has_boundary = true; - + topology_check(MultiPolygon const&) {} - template <typename P> - topology_check(MultiPolygon const&, P const&) {} + + static bool has_interior() { return true; } + static bool has_boundary() { return true; } + template <typename Point> + static bool check_boundary_point(Point const& ) { return true; } }; }} // namespace detail::relate |