detail/relate/boundary_checker.hpp

0001 // Boost.Geometry (aka GGL, Generic Geometry Library)
0002
0003 // Copyright (c) 2014-2023, Oracle and/or its affiliates.
0004
0005 // Contributed and/or modified by Vissarion Fysikopoulos, on behalf of Oracle
0006 // Contributed and/or modified by Adam Wulkiewicz, on behalf of Oracle
0007
0008 // Use, modification and distribution is subject to the Boost Software License,
0009 // Version 1.0. (See accompanying file LICENSE_1_0.txt or copy at
0010 // http://www.boost.org/LICENSE_1_0.txt)
0011
0012 #ifndef BOOST_GEOMETRY_ALGORITHMS_DETAIL_RELATE_BOUNDARY_CHECKER_HPP
0013 #define BOOST_GEOMETRY_ALGORITHMS_DETAIL_RELATE_BOUNDARY_CHECKER_HPP
0014
0015 #include <boost/core/ignore_unused.hpp>
0016 #include <boost/range/size.hpp>
0017
0018 #include <boost/geometry/algorithms/detail/equals/point_point.hpp>
0019 #include <boost/geometry/algorithms/detail/sub_range.hpp>
0020 #include <boost/geometry/algorithms/num_points.hpp>
0021
0022 #include <boost/geometry/geometries/helper_geometry.hpp>
0023
0024 #include <boost/geometry/policies/compare.hpp>
0025
0026 #include <boost/geometry/strategies/relate/cartesian.hpp>
0027 #include <boost/geometry/strategies/relate/geographic.hpp>
0028 #include <boost/geometry/strategies/relate/spherical.hpp>
0029
0030 #include <boost/geometry/util/has_nan_coordinate.hpp>
0031 #include <boost/geometry/util/range.hpp>
0032
0033 namespace boost { namespace geometry
0034 {
0035
0036 #ifndef DOXYGEN_NO_DETAIL
0037 namespace detail { namespace relate
0038 {
0039
0040
0041 template
0042 <
0043     typename Geometry,
0044     typename Strategy,
0045     typename Tag = typename geometry::tag<Geometry>::type
0046 >
0047 class boundary_checker {};
0048
0049 template <typename Geometry, typename Strategy>
0050 class boundary_checker<Geometry, Strategy, linestring_tag>
0051 {
0052 public:
0053     boundary_checker(Geometry const& g, Strategy const& s)
0054         : m_has_boundary(
0055             boost::size(g) >= 2
0056             && ! detail::equals::equals_point_point(range::front(g), range::back(g), s))
0057 #ifdef BOOST_GEOMETRY_DEBUG_RELATE_BOUNDARY_CHECKER
0058         , m_geometry(g)
0059 #endif
0060         , m_strategy(s)
0061     {}
0062
0063     template <typename Point>
0064     bool is_endpoint_boundary(Point const& pt) const
0065     {
0066         boost::ignore_unused(pt);
0067 #ifdef BOOST_GEOMETRY_DEBUG_RELATE_BOUNDARY_CHECKER
0068         // may give false positives for INT
0069         BOOST_GEOMETRY_ASSERT(
0070             detail::equals::equals_point_point(pt, range::front(m_geometry), m_strategy)
0071          || detail::equals::equals_point_point(pt, range::back(m_geometry), m_strategy));
0072 #endif
0073         return m_has_boundary;
0074     }
0075
0076     Strategy const& strategy() const
0077     {
0078         return m_strategy;
0079     }
0080
0081 private:
0082     bool m_has_boundary;
0083 #ifdef BOOST_GEOMETRY_DEBUG_RELATE_BOUNDARY_CHECKER
0084     Geometry const& m_geometry;
0085 #endif
0086     Strategy const& m_strategy;
0087 };
0088
0089
0090 template <typename Point, typename Strategy, typename Out>
0091 inline void copy_boundary_points(Point const& front_pt, Point const& back_pt,
0092                                  Strategy const& strategy, Out & boundary_points)
0093 {
0094     using mutable_point_type = typename Out::value_type;
0095     // linear ring or point - no boundary
0096     if (! equals::equals_point_point(front_pt, back_pt, strategy))
0097     {
0098         // do not add points containing NaN coordinates
0099         // because they cannot be reasonably compared, e.g. with MSVC
0100         // an assertion failure is reported in std::equal_range()
0101         if (! geometry::has_nan_coordinate(front_pt))
0102         {
0103             mutable_point_type pt;
0104             geometry::convert(front_pt, pt);
0105             boundary_points.push_back(pt);
0106         }
0107         if (! geometry::has_nan_coordinate(back_pt))
0108         {
0109             mutable_point_type pt;
0110             geometry::convert(back_pt, pt);
0111             boundary_points.push_back(pt);
0112         }
0113     }
0114 }
0115
0116 template <typename Segment, typename Strategy, typename Out>
0117 inline void copy_boundary_points_of_seg(Segment const& seg, Strategy const& strategy,
0118                                         Out & boundary_points)
0119 {
0120     typename Out::value_type front_pt, back_pt;
0121     assign_point_from_index<0>(seg, front_pt);
0122     assign_point_from_index<1>(seg, back_pt);
0123     copy_boundary_points(front_pt, back_pt, strategy, boundary_points);
0124 }
0125
0126 template <typename Linestring, typename Strategy, typename Out>
0127 inline void copy_boundary_points_of_ls(Linestring const& ls, Strategy const& strategy,
0128                                        Out & boundary_points)
0129 {
0130     // empty or point - no boundary
0131     if (boost::size(ls) >= 2)
0132     {
0133         auto const& front_pt = range::front(ls);
0134         auto const& back_pt = range::back(ls);
0135         copy_boundary_points(front_pt, back_pt, strategy, boundary_points);
0136     }
0137 }
0138
0139 template <typename MultiLinestring, typename Strategy, typename Out>
0140 inline void copy_boundary_points_of_mls(MultiLinestring const& mls, Strategy const& strategy,
0141                                         Out & boundary_points)
0142 {
0143     for (auto it = boost::begin(mls); it != boost::end(mls); ++it)
0144     {
0145         copy_boundary_points_of_ls(*it, strategy, boundary_points);
0146     }
0147 }
0148
0149
0150 template <typename Geometry, typename Strategy>
0151 class boundary_checker<Geometry, Strategy, multi_linestring_tag>
0152 {
0153     using point_type = typename point_type<Geometry>::type;
0154     using mutable_point_type = typename helper_geometry<point_type>::type;
0155
0156 public:
0157     boundary_checker(Geometry const& g, Strategy const& s)
0158         : m_is_filled(false), m_geometry(g), m_strategy(s)
0159     {}
0160
0161     // First call O(NlogN)
0162     // Each next call O(logN)
0163     template <typename Point>
0164     bool is_endpoint_boundary(Point const& pt) const
0165     {
0166         using less_type = geometry::less<mutable_point_type, -1, Strategy>;
0167
0168         auto const multi_count = boost::size(m_geometry);
0169
0170         if (multi_count < 1)
0171         {
0172             return false;
0173         }
0174
0175         if (! m_is_filled)
0176         {
0177             //boundary_points.clear();
0178             m_boundary_points.reserve(multi_count * 2);
0179
0180             copy_boundary_points_of_mls(m_geometry, m_strategy, m_boundary_points);
0181
0182             std::sort(m_boundary_points.begin(), m_boundary_points.end(), less_type());
0183
0184             m_is_filled = true;
0185         }
0186
0187         mutable_point_type mpt;
0188         geometry::convert(pt, mpt);
0189         auto const equal_range = std::equal_range(m_boundary_points.begin(),
0190                                                   m_boundary_points.end(),
0191                                                   mpt,
0192                                                   less_type());
0193
0194         std::size_t const equal_points_count = boost::size(equal_range);
0195         return equal_points_count % 2 != 0;// && equal_points_count > 0; // the number is odd and > 0
0196     }
0197
0198     Strategy const& strategy() const
0199     {
0200         return m_strategy;
0201     }
0202
0203 private:
0204     mutable bool m_is_filled;
0205     // TODO: store references/pointers instead of converted points?
0206     mutable std::vector<mutable_point_type> m_boundary_points;
0207
0208     Geometry const& m_geometry;
0209     Strategy const& m_strategy;
0210 };
0211
0212
0213 }} // namespace detail::relate
0214 #endif // DOXYGEN_NO_DETAIL
0215
0216 }} // namespace boost::geometry
0217
0218 #endif // BOOST_GEOMETRY_ALGORITHMS_DETAIL_RELATE_BOUNDARY_CHECKER_HPP