1 // Boost.Geometry (aka GGL, Generic Geometry Library) 2 3 // Copyright (c) 2014, 2021, Oracle and/or its affiliates. 4 5 // Contributed and/or modified by Menelaos Karavelas, on behalf of Oracle 6 7 // Licensed under the Boost Software License version 1.0. 8 // http://www.boost.org/users/license.html 9 10 #ifndef BOOST_GEOMETRY_ALGORITHMS_DETAIL_IS_VALID_POLYGON_HPP 11 #define BOOST_GEOMETRY_ALGORITHMS_DETAIL_IS_VALID_POLYGON_HPP 12 13 #include <cstddef> 14 #ifdef BOOST_GEOMETRY_TEST_DEBUG 15 #include <iostream> 16 #endif // BOOST_GEOMETRY_TEST_DEBUG 17 18 #include <algorithm> 19 #include <deque> 20 #include <iterator> 21 #include <set> 22 #include <vector> 23 24 #include <boost/core/ignore_unused.hpp> 25 #include <boost/range.hpp> 26 27 #include <boost/geometry/core/assert.hpp> 28 #include <boost/geometry/core/exterior_ring.hpp> 29 #include <boost/geometry/core/interior_rings.hpp> 30 #include <boost/geometry/core/ring_type.hpp> 31 #include <boost/geometry/core/tags.hpp> 32 33 #include <boost/geometry/util/condition.hpp> 34 #include <boost/geometry/util/range.hpp> 35 36 #include <boost/geometry/geometries/box.hpp> 37 38 #include <boost/geometry/iterators/point_iterator.hpp> 39 40 #include <boost/geometry/algorithms/covered_by.hpp> 41 #include <boost/geometry/algorithms/disjoint.hpp> 42 #include <boost/geometry/algorithms/expand.hpp> 43 #include <boost/geometry/algorithms/num_interior_rings.hpp> 44 #include <boost/geometry/algorithms/validity_failure_type.hpp> 45 #include <boost/geometry/algorithms/within.hpp> 46 47 #include <boost/geometry/algorithms/detail/check_iterator_range.hpp> 48 #include <boost/geometry/algorithms/detail/partition.hpp> 49 50 #include <boost/geometry/algorithms/detail/is_valid/complement_graph.hpp> 51 #include <boost/geometry/algorithms/detail/is_valid/has_valid_self_turns.hpp> 52 #include <boost/geometry/algorithms/detail/is_valid/is_acceptable_turn.hpp> 53 #include <boost/geometry/algorithms/detail/is_valid/ring.hpp> 54 55 #include <boost/geometry/algorithms/detail/is_valid/debug_print_turns.hpp> 56 #include <boost/geometry/algorithms/detail/is_valid/debug_validity_phase.hpp> 57 #include <boost/geometry/algorithms/detail/is_valid/debug_complement_graph.hpp> 58 59 #include <boost/geometry/algorithms/dispatch/is_valid.hpp> 60 61 62 namespace boost { namespace geometry 63 { 64 65 66 #ifndef DOXYGEN_NO_DETAIL 67 namespace detail { namespace is_valid 68 { 69 70 71 template <typename Polygon, bool CheckRingValidityOnly = false> 72 class is_valid_polygon 73 { 74 protected: 75 typedef debug_validity_phase<Polygon> debug_phase; 76 77 template <typename VisitPolicy> 78 struct per_ring 79 { per_ringboost::geometry::detail::is_valid::is_valid_polygon::per_ring80 per_ring(VisitPolicy& policy) : m_policy(policy) {} 81 82 template <typename Ring> applyboost::geometry::detail::is_valid::is_valid_polygon::per_ring83 inline bool apply(Ring const& ring) const 84 { 85 return detail::is_valid::is_valid_ring 86 < 87 Ring, false, true 88 >::apply(ring, m_policy); 89 } 90 91 VisitPolicy& m_policy; 92 }; 93 94 template <typename InteriorRings, typename VisitPolicy> has_valid_interior_rings(InteriorRings const & interior_rings,VisitPolicy & visitor)95 static bool has_valid_interior_rings(InteriorRings const& interior_rings, 96 VisitPolicy& visitor) 97 { 98 return 99 detail::check_iterator_range 100 < 101 per_ring<VisitPolicy>, 102 true // allow for empty interior ring range 103 >::apply(boost::begin(interior_rings), 104 boost::end(interior_rings), 105 per_ring<VisitPolicy>(visitor)); 106 } 107 108 struct has_valid_rings 109 { 110 template <typename VisitPolicy> applyboost::geometry::detail::is_valid::is_valid_polygon::has_valid_rings111 static inline bool apply(Polygon const& polygon, VisitPolicy& visitor) 112 { 113 typedef typename ring_type<Polygon>::type ring_type; 114 115 // check validity of exterior ring 116 debug_phase::apply(1); 117 118 if (! detail::is_valid::is_valid_ring 119 < 120 ring_type, 121 false // do not check self intersections 122 >::apply(exterior_ring(polygon), visitor)) 123 { 124 return false; 125 } 126 127 // check validity of interior rings 128 debug_phase::apply(2); 129 130 return has_valid_interior_rings(geometry::interior_rings(polygon), 131 visitor); 132 } 133 }; 134 135 136 // structs for partition -- start 137 struct expand_box 138 { 139 template <typename Box, typename Iterator> applyboost::geometry::detail::is_valid::is_valid_polygon::expand_box140 static inline void apply(Box& total, Iterator const& it) 141 { 142 geometry::expand(total, geometry::return_envelope<Box>(*it)); 143 } 144 145 }; 146 147 struct overlaps_box 148 { 149 template <typename Box, typename Iterator> applyboost::geometry::detail::is_valid::is_valid_polygon::overlaps_box150 static inline bool apply(Box const& box, Iterator const& it) 151 { 152 return ! geometry::disjoint(*it, box); 153 } 154 }; 155 156 157 struct item_visitor_type 158 { 159 bool items_overlap; 160 item_visitor_typeboost::geometry::detail::is_valid::is_valid_polygon::item_visitor_type161 item_visitor_type() : items_overlap(false) {} 162 163 template <typename Item1, typename Item2> applyboost::geometry::detail::is_valid::is_valid_polygon::item_visitor_type164 inline void apply(Item1 const& item1, Item2 const& item2) 165 { 166 if (! items_overlap 167 && (geometry::within(*points_begin(*item1), *item2) 168 || geometry::within(*points_begin(*item2), *item1)) 169 ) 170 { 171 items_overlap = true; 172 } 173 } 174 }; 175 // structs for partition -- end 176 177 178 template 179 < 180 typename RingIterator, 181 typename ExteriorRing, 182 typename TurnIterator, 183 typename VisitPolicy 184 > are_holes_inside(RingIterator rings_first,RingIterator rings_beyond,ExteriorRing const & exterior_ring,TurnIterator turns_first,TurnIterator turns_beyond,VisitPolicy & visitor)185 static inline bool are_holes_inside(RingIterator rings_first, 186 RingIterator rings_beyond, 187 ExteriorRing const& exterior_ring, 188 TurnIterator turns_first, 189 TurnIterator turns_beyond, 190 VisitPolicy& visitor) 191 { 192 boost::ignore_unused(visitor); 193 194 // collect the interior ring indices that have turns with the 195 // exterior ring 196 std::set<signed_size_type> ring_indices; 197 for (TurnIterator tit = turns_first; tit != turns_beyond; ++tit) 198 { 199 if (tit->operations[0].seg_id.ring_index == -1) 200 { 201 BOOST_GEOMETRY_ASSERT(tit->operations[1].seg_id.ring_index != -1); 202 ring_indices.insert(tit->operations[1].seg_id.ring_index); 203 } 204 else if (tit->operations[1].seg_id.ring_index == -1) 205 { 206 BOOST_GEOMETRY_ASSERT(tit->operations[0].seg_id.ring_index != -1); 207 ring_indices.insert(tit->operations[0].seg_id.ring_index); 208 } 209 } 210 211 signed_size_type ring_index = 0; 212 for (RingIterator it = rings_first; it != rings_beyond; 213 ++it, ++ring_index) 214 { 215 // do not examine interior rings that have turns with the 216 // exterior ring 217 if (ring_indices.find(ring_index) == ring_indices.end() 218 && ! geometry::covered_by(range::front(*it), exterior_ring)) 219 { 220 return visitor.template apply<failure_interior_rings_outside>(); 221 } 222 } 223 224 // collect all rings (exterior and/or interior) that have turns 225 for (TurnIterator tit = turns_first; tit != turns_beyond; ++tit) 226 { 227 ring_indices.insert(tit->operations[0].seg_id.ring_index); 228 ring_indices.insert(tit->operations[1].seg_id.ring_index); 229 } 230 231 // put iterators for interior rings without turns in a vector 232 std::vector<RingIterator> ring_iterators; 233 ring_index = 0; 234 for (RingIterator it = rings_first; it != rings_beyond; 235 ++it, ++ring_index) 236 { 237 if (ring_indices.find(ring_index) == ring_indices.end()) 238 { 239 ring_iterators.push_back(it); 240 } 241 } 242 243 // call partition to check is interior rings are disjoint from 244 // each other 245 item_visitor_type item_visitor; 246 247 geometry::partition 248 < 249 geometry::model::box<typename point_type<Polygon>::type>, 250 expand_box, 251 overlaps_box 252 >::apply(ring_iterators, item_visitor); 253 254 if (item_visitor.items_overlap) 255 { 256 return visitor.template apply<failure_nested_interior_rings>(); 257 } 258 else 259 { 260 return visitor.template apply<no_failure>(); 261 } 262 } 263 264 template 265 < 266 typename InteriorRings, 267 typename ExteriorRing, 268 typename TurnIterator, 269 typename VisitPolicy 270 > are_holes_inside(InteriorRings const & interior_rings,ExteriorRing const & exterior_ring,TurnIterator first,TurnIterator beyond,VisitPolicy & visitor)271 static inline bool are_holes_inside(InteriorRings const& interior_rings, 272 ExteriorRing const& exterior_ring, 273 TurnIterator first, 274 TurnIterator beyond, 275 VisitPolicy& visitor) 276 { 277 return are_holes_inside(boost::begin(interior_rings), 278 boost::end(interior_rings), 279 exterior_ring, 280 first, 281 beyond, 282 visitor); 283 } 284 285 struct has_holes_inside 286 { 287 template <typename TurnIterator, typename VisitPolicy> applyboost::geometry::detail::is_valid::is_valid_polygon::has_holes_inside288 static inline bool apply(Polygon const& polygon, 289 TurnIterator first, 290 TurnIterator beyond, 291 VisitPolicy& visitor) 292 { 293 return are_holes_inside(geometry::interior_rings(polygon), 294 geometry::exterior_ring(polygon), 295 first, 296 beyond, 297 visitor); 298 } 299 }; 300 301 302 303 304 struct has_connected_interior 305 { 306 template <typename TurnIterator, typename VisitPolicy> applyboost::geometry::detail::is_valid::is_valid_polygon::has_connected_interior307 static inline bool apply(Polygon const& polygon, 308 TurnIterator first, 309 TurnIterator beyond, 310 VisitPolicy& visitor) 311 { 312 boost::ignore_unused(visitor); 313 314 typedef typename std::iterator_traits 315 < 316 TurnIterator 317 >::value_type turn_type; 318 typedef complement_graph<typename turn_type::point_type> graph; 319 320 graph g(geometry::num_interior_rings(polygon) + 1); 321 for (TurnIterator tit = first; tit != beyond; ++tit) 322 { 323 typename graph::vertex_handle v1 = g.add_vertex 324 ( tit->operations[0].seg_id.ring_index + 1 ); 325 typename graph::vertex_handle v2 = g.add_vertex 326 ( tit->operations[1].seg_id.ring_index + 1 ); 327 typename graph::vertex_handle vip = g.add_vertex(tit->point); 328 329 g.add_edge(v1, vip); 330 g.add_edge(v2, vip); 331 } 332 333 #ifdef BOOST_GEOMETRY_TEST_DEBUG 334 debug_print_complement_graph(std::cout, g); 335 #endif // BOOST_GEOMETRY_TEST_DEBUG 336 337 if (g.has_cycles()) 338 { 339 return visitor.template apply<failure_disconnected_interior>(); 340 } 341 else 342 { 343 return visitor.template apply<no_failure>(); 344 } 345 } 346 }; 347 348 public: 349 template <typename VisitPolicy> apply(Polygon const & polygon,VisitPolicy & visitor)350 static inline bool apply(Polygon const& polygon, VisitPolicy& visitor) 351 { 352 if (! has_valid_rings::apply(polygon, visitor)) 353 { 354 return false; 355 } 356 357 if (BOOST_GEOMETRY_CONDITION(CheckRingValidityOnly)) 358 { 359 return true; 360 } 361 362 // compute turns and check if all are acceptable 363 debug_phase::apply(3); 364 365 typedef has_valid_self_turns<Polygon> has_valid_turns; 366 367 std::deque<typename has_valid_turns::turn_type> turns; 368 bool has_invalid_turns 369 = ! has_valid_turns::apply(polygon, turns, visitor); 370 debug_print_turns(turns.begin(), turns.end()); 371 372 if (has_invalid_turns) 373 { 374 return false; 375 } 376 377 // check if all interior rings are inside the exterior ring 378 debug_phase::apply(4); 379 380 if (! has_holes_inside::apply(polygon, 381 turns.begin(), turns.end(), 382 visitor)) 383 { 384 return false; 385 } 386 387 // check whether the interior of the polygon is a connected set 388 debug_phase::apply(5); 389 390 return has_connected_interior::apply(polygon, 391 turns.begin(), 392 turns.end(), 393 visitor); 394 } 395 }; 396 397 398 }} // namespace detail::is_valid 399 #endif // DOXYGEN_NO_DETAIL 400 401 402 403 #ifndef DOXYGEN_NO_DISPATCH 404 namespace dispatch 405 { 406 407 408 // A Polygon is always a simple geometric object provided that it is valid. 409 // 410 // Reference (for validity of Polygons): OGC 06-103r4 (6.1.11.1) 411 template <typename Polygon, bool AllowEmptyMultiGeometries> 412 struct is_valid 413 < 414 Polygon, polygon_tag, AllowEmptyMultiGeometries 415 > : detail::is_valid::is_valid_polygon<Polygon> 416 {}; 417 418 419 } // namespace dispatch 420 #endif // DOXYGEN_NO_DISPATCH 421 422 423 }} // namespace boost::geometry 424 425 #endif // BOOST_GEOMETRY_ALGORITHMS_DETAIL_IS_VALID_POLYGON_HPP 426