detail/relate/topology_check.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_TOPOLOGY_CHECK_HPP
0013 #define BOOST_GEOMETRY_ALGORITHMS_DETAIL_RELATE_TOPOLOGY_CHECK_HPP
0014
0015 #include <boost/range/size.hpp>
0016
0017 #include <boost/geometry/algorithms/detail/equals/point_point.hpp>
0018 #include <boost/geometry/algorithms/not_implemented.hpp>
0019
0020 #include <boost/geometry/policies/compare.hpp>
0021
0022 #include <boost/geometry/util/has_nan_coordinate.hpp>
0023 #include <boost/geometry/util/range.hpp>
0024
0025
0026 namespace boost { namespace geometry {
0027
0028 #ifndef DOXYGEN_NO_DETAIL
0029 namespace detail { namespace relate {
0030
0031 // TODO: change the name for e.g. something with the word "exterior"
0032
0033 template
0034 <
0035     typename Geometry,
0036     typename Strategy,
0037     typename Tag = typename geometry::tag<Geometry>::type
0038 >
0039 struct topology_check
0040     : not_implemented<Tag>
0041 {};
0042
0043 //template <typename Point, typename Strategy>
0044 //struct topology_check<Point, Strategy, point_tag>
0045 //{
0046 //    static const char interior = '0';
0047 //    static const char boundary = 'F';
0048 //
0049 //    static const bool has_interior = true;
0050 //    static const bool has_boundary = false;
0051 //
0052 //    topology_check(Point const&) {}
0053 //    template <typename IgnoreBoundaryPoint>
0054 //    topology_check(Point const&, IgnoreBoundaryPoint const&) {}
0055 //};
0056
0057 template <typename Linestring, typename Strategy>
0058 struct topology_check<Linestring, Strategy, linestring_tag>
0059 {
0060     static const char interior = '1';
0061     static const char boundary = '0';
0062
0063     topology_check(Linestring const& ls, Strategy const& strategy)
0064         : m_ls(ls)
0065         , m_strategy(strategy)
0066         , m_is_initialized(false)
0067     {}
0068
0069     bool has_interior() const
0070     {
0071         init();
0072         return m_has_interior;
0073     }
0074
0075     bool has_boundary() const
0076     {
0077         init();
0078         return m_has_boundary;
0079     }
0080
0081     /*template <typename Point>
0082     bool check_boundary_point(Point const& point) const
0083     {
0084         init();
0085         return m_has_boundary
0086             && ( equals::equals_point_point(point, range::front(m_ls))
0087               || equals::equals_point_point(point, range::back(m_ls)) );
0088     }*/
0089
0090     template <typename Visitor>
0091     void for_each_boundary_point(Visitor & visitor) const
0092     {
0093         init();
0094         if (m_has_boundary)
0095         {
0096             if (visitor.apply(range::front(m_ls), m_strategy))
0097                 visitor.apply(range::back(m_ls), m_strategy);
0098         }
0099     }
0100
0101 private:
0102     void init() const
0103     {
0104         if (m_is_initialized)
0105             return;
0106
0107         std::size_t count = boost::size(m_ls);
0108         m_has_interior = count > 0;
0109         // NOTE: Linestring with all points equal is treated as 1d linear ring
0110         m_has_boundary = count > 1
0111             && ! detail::equals::equals_point_point(range::front(m_ls),
0112                                                     range::back(m_ls),
0113                                                     m_strategy);
0114
0115         m_is_initialized = true;
0116     }
0117
0118     Linestring const& m_ls;
0119     Strategy const& m_strategy;
0120
0121     mutable bool m_is_initialized;
0122
0123     mutable bool m_has_interior;
0124     mutable bool m_has_boundary;
0125 };
0126
0127 template <typename MultiLinestring, typename Strategy>
0128 struct topology_check<MultiLinestring, Strategy, multi_linestring_tag>
0129 {
0130     static const char interior = '1';
0131     static const char boundary = '0';
0132
0133     topology_check(MultiLinestring const& mls, Strategy const& strategy)
0134         : m_mls(mls)
0135         , m_strategy(strategy)
0136         , m_is_initialized(false)
0137     {}
0138
0139     bool has_interior() const
0140     {
0141         init();
0142         return m_has_interior;
0143     }
0144
0145     bool has_boundary() const
0146     {
0147         init();
0148         return m_has_boundary;
0149     }
0150
0151     template <typename Point>
0152     bool check_boundary_point(Point const& point) const
0153     {
0154         init();
0155
0156         if (! m_has_boundary)
0157             return false;
0158
0159         std::size_t count = count_equal(m_endpoints.begin(), m_endpoints.end(), point);
0160
0161         return count % 2 != 0; // odd count -> boundary
0162     }
0163
0164     template <typename Visitor>
0165     void for_each_boundary_point(Visitor & visitor) const
0166     {
0167         init();
0168         if (m_has_boundary)
0169         {
0170             for_each_boundary_point(m_endpoints.begin(), m_endpoints.end(), visitor);
0171         }
0172     }
0173
0174 private:
0175     typedef geometry::less<void, -1, Strategy> less_type;
0176
0177     void init() const
0178     {
0179         if (m_is_initialized)
0180         {
0181             return;
0182         }
0183
0184         m_endpoints.reserve(boost::size(m_mls) * 2);
0185
0186         m_has_interior = false;
0187
0188         for (auto it = boost::begin(m_mls); it != boost::end(m_mls); ++it)
0189         {
0190             auto const& ls = *it;
0191
0192             std::size_t count = boost::size(ls);
0193
0194             if (count > 0)
0195             {
0196                 m_has_interior = true;
0197             }
0198
0199             if (count > 1)
0200             {
0201                 auto const& front_pt = range::front(ls);
0202                 auto const& back_pt = range::back(ls);
0203
0204                 // don't store boundaries of linear rings, this doesn't change anything
0205                 if (! equals::equals_point_point(front_pt, back_pt, m_strategy))
0206                 {
0207                     // do not add points containing NaN coordinates
0208                     // because they cannot be reasonably compared, e.g. with MSVC
0209                     // an assertion failure is reported in std::equal_range()
0210                     // NOTE: currently ignoring_counter calling std::equal_range()
0211                     //   is not used anywhere in the code, still it's safer this way
0212                     if (! geometry::has_nan_coordinate(front_pt))
0213                     {
0214                         m_endpoints.push_back(front_pt);
0215                     }
0216                     if (! geometry::has_nan_coordinate(back_pt))
0217                     {
0218                         m_endpoints.push_back(back_pt);
0219                     }
0220                 }
0221             }
0222         }
0223
0224         m_has_boundary = false;
0225
0226         if (! m_endpoints.empty())
0227         {
0228             std::sort(m_endpoints.begin(), m_endpoints.end(), less_type());
0229             m_has_boundary = find_odd_count(m_endpoints.begin(), m_endpoints.end());
0230         }
0231
0232         m_is_initialized = true;
0233     }
0234
0235     template <typename It, typename Point>
0236     static inline std::size_t count_equal(It first, It last, Point const& point)
0237     {
0238         std::pair<It, It> rng = std::equal_range(first, last, point, less_type());
0239         return (std::size_t)std::distance(rng.first, rng.second);
0240     }
0241
0242     template <typename It>
0243     inline bool find_odd_count(It first, It last) const
0244     {
0245         interrupting_visitor visitor;
0246         for_each_boundary_point(first, last, visitor);
0247         return visitor.found;
0248     }
0249
0250     struct interrupting_visitor
0251     {
0252         bool found;
0253         interrupting_visitor() : found(false) {}
0254         template <typename Point>
0255         bool apply(Point const&, Strategy const&)
0256         {
0257             found = true;
0258             return false;
0259         }
0260     };
0261
0262     template <typename It, typename Visitor>
0263     void for_each_boundary_point(It first, It last, Visitor& visitor) const
0264     {
0265         if ( first == last )
0266             return;
0267
0268         std::size_t count = 1;
0269         It prev = first;
0270         ++first;
0271         for ( ; first != last ; ++first, ++prev )
0272         {
0273             // the end of the equal points subrange
0274             if ( ! equals::equals_point_point(*first, *prev, m_strategy) )
0275             {
0276                 // odd count -> boundary
0277                 if ( count % 2 != 0 )
0278                 {
0279                     if (! visitor.apply(*prev, m_strategy))
0280                     {
0281                         return;
0282                     }
0283                 }
0284
0285                 count = 1;
0286             }
0287             else
0288             {
0289                 ++count;
0290             }
0291         }
0292
0293         // odd count -> boundary
0294         if ( count % 2 != 0 )
0295         {
0296             visitor.apply(*prev, m_strategy);
0297         }
0298     }
0299
0300 private:
0301     MultiLinestring const& m_mls;
0302     Strategy const& m_strategy;
0303
0304     mutable bool m_is_initialized;
0305
0306     mutable bool m_has_interior;
0307     mutable bool m_has_boundary;
0308
0309     typedef typename geometry::point_type<MultiLinestring>::type point_type;
0310     mutable std::vector<point_type> m_endpoints;
0311 };
0312
0313 struct topology_check_areal
0314 {
0315     static const char interior = '2';
0316     static const char boundary = '1';
0317
0318     static bool has_interior() { return true; }
0319     static bool has_boundary() { return true; }
0320 };
0321
0322 template <typename Ring, typename Strategy>
0323 struct topology_check<Ring, Strategy, ring_tag>
0324     : topology_check_areal
0325 {
0326     topology_check(Ring const&, Strategy const&) {}
0327 };
0328
0329 template <typename Polygon, typename Strategy>
0330 struct topology_check<Polygon, Strategy, polygon_tag>
0331     : topology_check_areal
0332 {
0333     topology_check(Polygon const&, Strategy const&) {}
0334 };
0335
0336 template <typename MultiPolygon, typename Strategy>
0337 struct topology_check<MultiPolygon, Strategy, multi_polygon_tag>
0338     : topology_check_areal
0339 {
0340     topology_check(MultiPolygon const&, Strategy const&) {}
0341
0342     template <typename Point>
0343     static bool check_boundary_point(Point const& ) { return true; }
0344 };
0345
0346 }} // namespace detail::relate
0347 #endif // DOXYGEN_NO_DETAIL
0348
0349 }} // namespace boost::geometry
0350
0351 #endif // BOOST_GEOMETRY_ALGORITHMS_DETAIL_RELATE_TOPOLOGY_CHECK_HPP