1 // Boost.Geometry (aka GGL, Generic Geometry Library) 2 3 // Copyright (c) 2014-2020, Oracle and/or its affiliates. 4 5 // Contributed and/or modified by Adam Wulkiewicz, on behalf of Oracle 6 7 // Use, modification and distribution is subject to the Boost Software License, 8 // Version 1.0. (See accompanying file LICENSE_1_0.txt or copy at 9 // http://www.boost.org/LICENSE_1_0.txt) 10 11 #ifndef BOOST_GEOMETRY_ALGORITHMS_DETAIL_RELATE_TOPOLOGY_CHECK_HPP 12 #define BOOST_GEOMETRY_ALGORITHMS_DETAIL_RELATE_TOPOLOGY_CHECK_HPP 13 14 15 #include <boost/geometry/algorithms/detail/equals/point_point.hpp> 16 #include <boost/geometry/algorithms/not_implemented.hpp> 17 18 #include <boost/geometry/policies/compare.hpp> 19 20 #include <boost/geometry/util/has_nan_coordinate.hpp> 21 #include <boost/geometry/util/range.hpp> 22 23 24 namespace boost { namespace geometry { 25 26 #ifndef DOXYGEN_NO_DETAIL 27 namespace detail { namespace relate { 28 29 // TODO: change the name for e.g. something with the word "exterior" 30 31 template 32 < 33 typename Geometry, 34 typename Strategy, 35 typename Tag = typename geometry::tag<Geometry>::type 36 > 37 struct topology_check 38 : not_implemented<Tag> 39 {}; 40 41 //template <typename Point, typename Strategy> 42 //struct topology_check<Point, Strategy, point_tag> 43 //{ 44 // static const char interior = '0'; 45 // static const char boundary = 'F'; 46 // 47 // static const bool has_interior = true; 48 // static const bool has_boundary = false; 49 // 50 // topology_check(Point const&) {} 51 // template <typename IgnoreBoundaryPoint> 52 // topology_check(Point const&, IgnoreBoundaryPoint const&) {} 53 //}; 54 55 template <typename Linestring, typename Strategy> 56 struct topology_check<Linestring, Strategy, linestring_tag> 57 { 58 static const char interior = '1'; 59 static const char boundary = '0'; 60 topology_checkboost::geometry::detail::relate::topology_check61 topology_check(Linestring const& ls, Strategy const& strategy) 62 : m_ls(ls) 63 , m_strategy(strategy) 64 , m_is_initialized(false) 65 {} 66 has_interiorboost::geometry::detail::relate::topology_check67 bool has_interior() const 68 { 69 init(); 70 return m_has_interior; 71 } 72 has_boundaryboost::geometry::detail::relate::topology_check73 bool has_boundary() const 74 { 75 init(); 76 return m_has_boundary; 77 } 78 79 /*template <typename Point> 80 bool check_boundary_point(Point const& point) const 81 { 82 init(); 83 return m_has_boundary 84 && ( equals::equals_point_point(point, range::front(m_ls)) 85 || equals::equals_point_point(point, range::back(m_ls)) ); 86 }*/ 87 88 template <typename Visitor> for_each_boundary_pointboost::geometry::detail::relate::topology_check89 void for_each_boundary_point(Visitor & visitor) const 90 { 91 init(); 92 if (m_has_boundary) 93 { 94 if (visitor.apply(range::front(m_ls), m_strategy)) 95 visitor.apply(range::back(m_ls), m_strategy); 96 } 97 } 98 99 private: initboost::geometry::detail::relate::topology_check100 void init() const 101 { 102 if (m_is_initialized) 103 return; 104 105 std::size_t count = boost::size(m_ls); 106 m_has_interior = count > 0; 107 // NOTE: Linestring with all points equal is treated as 1d linear ring 108 m_has_boundary = count > 1 109 && ! detail::equals::equals_point_point(range::front(m_ls), 110 range::back(m_ls), 111 m_strategy); 112 113 m_is_initialized = true; 114 } 115 116 Linestring const& m_ls; 117 Strategy const& m_strategy; 118 119 mutable bool m_is_initialized; 120 121 mutable bool m_has_interior; 122 mutable bool m_has_boundary; 123 }; 124 125 template <typename MultiLinestring, typename Strategy> 126 struct topology_check<MultiLinestring, Strategy, multi_linestring_tag> 127 { 128 static const char interior = '1'; 129 static const char boundary = '0'; 130 topology_checkboost::geometry::detail::relate::topology_check131 topology_check(MultiLinestring const& mls, Strategy const& strategy) 132 : m_mls(mls) 133 , m_strategy(strategy) 134 , m_is_initialized(false) 135 {} 136 has_interiorboost::geometry::detail::relate::topology_check137 bool has_interior() const 138 { 139 init(); 140 return m_has_interior; 141 } 142 has_boundaryboost::geometry::detail::relate::topology_check143 bool has_boundary() const 144 { 145 init(); 146 return m_has_boundary; 147 } 148 149 template <typename Point> check_boundary_pointboost::geometry::detail::relate::topology_check150 bool check_boundary_point(Point const& point) const 151 { 152 init(); 153 154 if (! m_has_boundary) 155 return false; 156 157 std::size_t count = count_equal(m_endpoints.begin(), m_endpoints.end(), point); 158 159 return count % 2 != 0; // odd count -> boundary 160 } 161 162 template <typename Visitor> for_each_boundary_pointboost::geometry::detail::relate::topology_check163 void for_each_boundary_point(Visitor & visitor) const 164 { 165 init(); 166 if (m_has_boundary) 167 { 168 for_each_boundary_point(m_endpoints.begin(), m_endpoints.end(), visitor); 169 } 170 } 171 172 private: 173 typedef geometry::less<void, -1, typename Strategy::cs_tag> less_type; 174 initboost::geometry::detail::relate::topology_check175 void init() const 176 { 177 if (m_is_initialized) 178 return; 179 180 m_endpoints.reserve(boost::size(m_mls) * 2); 181 182 m_has_interior = false; 183 184 typedef typename boost::range_iterator<MultiLinestring const>::type ls_iterator; 185 for ( ls_iterator it = boost::begin(m_mls) ; it != boost::end(m_mls) ; ++it ) 186 { 187 typename boost::range_reference<MultiLinestring const>::type 188 ls = *it; 189 190 std::size_t count = boost::size(ls); 191 192 if (count > 0) 193 { 194 m_has_interior = true; 195 } 196 197 if (count > 1) 198 { 199 typedef typename boost::range_reference 200 < 201 typename boost::range_value<MultiLinestring const>::type const 202 >::type point_reference; 203 204 point_reference front_pt = range::front(ls); 205 point_reference back_pt = range::back(ls); 206 207 // don't store boundaries of linear rings, this doesn't change anything 208 if (! equals::equals_point_point(front_pt, back_pt, m_strategy)) 209 { 210 // do not add points containing NaN coordinates 211 // because they cannot be reasonably compared, e.g. with MSVC 212 // an assertion failure is reported in std::equal_range() 213 // NOTE: currently ignoring_counter calling std::equal_range() 214 // is not used anywhere in the code, still it's safer this way 215 if (! geometry::has_nan_coordinate(front_pt)) 216 { 217 m_endpoints.push_back(front_pt); 218 } 219 if (! geometry::has_nan_coordinate(back_pt)) 220 { 221 m_endpoints.push_back(back_pt); 222 } 223 } 224 } 225 } 226 227 m_has_boundary = false; 228 229 if (! m_endpoints.empty() ) 230 { 231 std::sort(m_endpoints.begin(), m_endpoints.end(), less_type()); 232 m_has_boundary = find_odd_count(m_endpoints.begin(), m_endpoints.end()); 233 } 234 235 m_is_initialized = true; 236 } 237 238 template <typename It, typename Point> count_equalboost::geometry::detail::relate::topology_check239 static inline std::size_t count_equal(It first, It last, Point const& point) 240 { 241 std::pair<It, It> rng = std::equal_range(first, last, point, less_type()); 242 return (std::size_t)std::distance(rng.first, rng.second); 243 } 244 245 template <typename It> find_odd_countboost::geometry::detail::relate::topology_check246 inline bool find_odd_count(It first, It last) const 247 { 248 interrupting_visitor visitor; 249 for_each_boundary_point(first, last, visitor); 250 return visitor.found; 251 } 252 253 struct interrupting_visitor 254 { 255 bool found; interrupting_visitorboost::geometry::detail::relate::topology_check::interrupting_visitor256 interrupting_visitor() : found(false) {} 257 template <typename Point> applyboost::geometry::detail::relate::topology_check::interrupting_visitor258 bool apply(Point const&, Strategy const&) 259 { 260 found = true; 261 return false; 262 } 263 }; 264 265 template <typename It, typename Visitor> for_each_boundary_pointboost::geometry::detail::relate::topology_check266 void for_each_boundary_point(It first, It last, Visitor& visitor) const 267 { 268 if ( first == last ) 269 return; 270 271 std::size_t count = 1; 272 It prev = first; 273 ++first; 274 for ( ; first != last ; ++first, ++prev ) 275 { 276 // the end of the equal points subrange 277 if ( ! equals::equals_point_point(*first, *prev, m_strategy) ) 278 { 279 // odd count -> boundary 280 if ( count % 2 != 0 ) 281 { 282 if (! visitor.apply(*prev, m_strategy)) 283 { 284 return; 285 } 286 } 287 288 count = 1; 289 } 290 else 291 { 292 ++count; 293 } 294 } 295 296 // odd count -> boundary 297 if ( count % 2 != 0 ) 298 { 299 visitor.apply(*prev, m_strategy); 300 } 301 } 302 303 private: 304 MultiLinestring const& m_mls; 305 Strategy const& m_strategy; 306 307 mutable bool m_is_initialized; 308 309 mutable bool m_has_interior; 310 mutable bool m_has_boundary; 311 312 typedef typename geometry::point_type<MultiLinestring>::type point_type; 313 mutable std::vector<point_type> m_endpoints; 314 }; 315 316 struct topology_check_areal 317 { 318 static const char interior = '2'; 319 static const char boundary = '1'; 320 has_interiorboost::geometry::detail::relate::topology_check_areal321 static bool has_interior() { return true; } has_boundaryboost::geometry::detail::relate::topology_check_areal322 static bool has_boundary() { return true; } 323 }; 324 325 template <typename Ring, typename Strategy> 326 struct topology_check<Ring, Strategy, ring_tag> 327 : topology_check_areal 328 { topology_checkboost::geometry::detail::relate::topology_check329 topology_check(Ring const&, Strategy const&) {} 330 }; 331 332 template <typename Polygon, typename Strategy> 333 struct topology_check<Polygon, Strategy, polygon_tag> 334 : topology_check_areal 335 { topology_checkboost::geometry::detail::relate::topology_check336 topology_check(Polygon const&, Strategy const&) {} 337 }; 338 339 template <typename MultiPolygon, typename Strategy> 340 struct topology_check<MultiPolygon, Strategy, multi_polygon_tag> 341 : topology_check_areal 342 { topology_checkboost::geometry::detail::relate::topology_check343 topology_check(MultiPolygon const&, Strategy const&) {} 344 345 template <typename Point> check_boundary_pointboost::geometry::detail::relate::topology_check346 static bool check_boundary_point(Point const& ) { return true; } 347 }; 348 349 }} // namespace detail::relate 350 #endif // DOXYGEN_NO_DETAIL 351 352 }} // namespace boost::geometry 353 354 #endif // BOOST_GEOMETRY_ALGORITHMS_DETAIL_RELATE_TOPOLOGY_CHECK_HPP 355