123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176 |
- // Boost.Geometry (aka GGL, Generic Geometry Library)
- // Copyright (c) 2014-2018 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_BOUNDARY_CHECKER_HPP
- #define BOOST_GEOMETRY_ALGORITHMS_DETAIL_RELATE_BOUNDARY_CHECKER_HPP
- #include <boost/core/ignore_unused.hpp>
- #include <boost/geometry/algorithms/detail/equals/point_point.hpp>
- #include <boost/geometry/algorithms/detail/sub_range.hpp>
- #include <boost/geometry/algorithms/num_points.hpp>
- #include <boost/geometry/policies/compare.hpp>
- #include <boost/geometry/util/has_nan_coordinate.hpp>
- #include <boost/geometry/util/range.hpp>
- namespace boost { namespace geometry
- {
- #ifndef DOXYGEN_NO_DETAIL
- namespace detail { namespace relate {
- enum boundary_query { boundary_front, boundary_back, boundary_any };
- template <typename Geometry,
- typename WithinStrategy, // Point/Point equals (within) strategy
- typename Tag = typename geometry::tag<Geometry>::type>
- class boundary_checker {};
- template <typename Geometry, typename WithinStrategy>
- class boundary_checker<Geometry, WithinStrategy, linestring_tag>
- {
- typedef typename point_type<Geometry>::type point_type;
- public:
- typedef WithinStrategy equals_strategy_type;
- boundary_checker(Geometry const& g)
- : has_boundary( boost::size(g) >= 2
- && !detail::equals::equals_point_point(range::front(g),
- range::back(g),
- equals_strategy_type()) )
- #ifdef BOOST_GEOMETRY_DEBUG_RELATE_BOUNDARY_CHECKER
- , geometry(g)
- #endif
- {}
- template <boundary_query BoundaryQuery>
- bool is_endpoint_boundary(point_type const& pt) const
- {
- boost::ignore_unused(pt);
- #ifdef BOOST_GEOMETRY_DEBUG_RELATE_BOUNDARY_CHECKER
- // may give false positives for INT
- BOOST_GEOMETRY_ASSERT( (BoundaryQuery == boundary_front || BoundaryQuery == boundary_any)
- && detail::equals::equals_point_point(pt, range::front(geometry), WithinStrategy())
- || (BoundaryQuery == boundary_back || BoundaryQuery == boundary_any)
- && detail::equals::equals_point_point(pt, range::back(geometry), WithinStrategy()) );
- #endif
- return has_boundary;
- }
- private:
- bool has_boundary;
- #ifdef BOOST_GEOMETRY_DEBUG_RELATE_BOUNDARY_CHECKER
- Geometry const& geometry;
- #endif
- };
- template <typename Geometry, typename WithinStrategy>
- class boundary_checker<Geometry, WithinStrategy, multi_linestring_tag>
- {
- typedef typename point_type<Geometry>::type point_type;
- public:
- typedef WithinStrategy equals_strategy_type;
-
- boundary_checker(Geometry const& g)
- : is_filled(false), geometry(g)
- {}
- // First call O(NlogN)
- // Each next call O(logN)
- template <boundary_query BoundaryQuery>
- bool is_endpoint_boundary(point_type const& pt) const
- {
- typedef geometry::less<point_type, -1, typename WithinStrategy::cs_tag> less_type;
- typedef typename boost::range_size<Geometry>::type size_type;
- size_type multi_count = boost::size(geometry);
- if ( multi_count < 1 )
- return false;
- if ( ! is_filled )
- {
- //boundary_points.clear();
- boundary_points.reserve(multi_count * 2);
- typedef typename boost::range_iterator<Geometry const>::type multi_iterator;
- for ( multi_iterator it = boost::begin(geometry) ;
- it != boost::end(geometry) ; ++ it )
- {
- typename boost::range_reference<Geometry const>::type
- ls = *it;
- // empty or point - no boundary
- if (boost::size(ls) < 2)
- {
- continue;
- }
- typedef typename boost::range_reference
- <
- typename boost::range_value<Geometry const>::type const
- >::type point_reference;
- point_reference front_pt = range::front(ls);
- point_reference back_pt = range::back(ls);
- // linear ring or point - no boundary
- if (! equals::equals_point_point(front_pt, back_pt, equals_strategy_type()))
- {
- // do not add points containing NaN coordinates
- // because they cannot be reasonably compared, e.g. with MSVC
- // an assertion failure is reported in std::equal_range()
- if (! geometry::has_nan_coordinate(front_pt))
- {
- boundary_points.push_back(front_pt);
- }
- if (! geometry::has_nan_coordinate(back_pt))
- {
- boundary_points.push_back(back_pt);
- }
- }
- }
- std::sort(boundary_points.begin(),
- boundary_points.end(),
- less_type());
- is_filled = true;
- }
- std::size_t equal_points_count
- = boost::size(
- std::equal_range(boundary_points.begin(),
- boundary_points.end(),
- pt,
- less_type())
- );
- return equal_points_count % 2 != 0;// && equal_points_count > 0; // the number is odd and > 0
- }
- private:
- mutable bool is_filled;
- // TODO: store references/pointers instead of points?
- mutable std::vector<point_type> boundary_points;
- Geometry const& geometry;
- };
- }} // namespace detail::relate
- #endif // DOXYGEN_NO_DETAIL
- }} // namespace boost::geometry
- #endif // BOOST_GEOMETRY_ALGORITHMS_DETAIL_RELATE_BOUNDARY_CHECKER_HPP
|