diff options
Diffstat (limited to 'boost/geometry/algorithms/detail/relate/topology_check.hpp')
| -rw-r--r-- | boost/geometry/algorithms/detail/relate/topology_check.hpp | 244 |
1 files changed, 161 insertions, 83 deletions
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 |