1 // Boost.Geometry (aka GGL, Generic Geometry Library) 2 3 // Copyright (c) 2017 Adam Wulkiewicz, Lodz, Poland. 4 5 // Copyright (c) 2014-2020, Oracle and/or its affiliates. 6 7 // Contributed and/or modified by Menelaos Karavelas, on behalf of Oracle 8 // Contributed and/or modified by Adam Wulkiewicz, on behalf of Oracle 9 10 // Licensed under the Boost Software License version 1.0. 11 // http://www.boost.org/users/license.html 12 13 #ifndef BOOST_GEOMETRY_ALGORITHMS_DETAIL_IS_VALID_POLYGON_HPP 14 #define BOOST_GEOMETRY_ALGORITHMS_DETAIL_IS_VALID_POLYGON_HPP 15 16 #include <cstddef> 17 #ifdef BOOST_GEOMETRY_TEST_DEBUG 18 #include <iostream> 19 #endif // BOOST_GEOMETRY_TEST_DEBUG 20 21 #include <algorithm> 22 #include <deque> 23 #include <iterator> 24 #include <set> 25 #include <vector> 26 27 #include <boost/core/ignore_unused.hpp> 28 #include <boost/range/begin.hpp> 29 #include <boost/range/end.hpp> 30 31 #include <boost/geometry/core/assert.hpp> 32 #include <boost/geometry/core/exterior_ring.hpp> 33 #include <boost/geometry/core/interior_rings.hpp> 34 #include <boost/geometry/core/ring_type.hpp> 35 #include <boost/geometry/core/tags.hpp> 36 37 #include <boost/geometry/util/condition.hpp> 38 #include <boost/geometry/util/range.hpp> 39 #include <boost/geometry/util/sequence.hpp> 40 41 #include <boost/geometry/geometries/box.hpp> 42 43 #include <boost/geometry/iterators/point_iterator.hpp> 44 45 #include <boost/geometry/algorithms/covered_by.hpp> 46 #include <boost/geometry/algorithms/disjoint.hpp> 47 #include <boost/geometry/algorithms/expand.hpp> 48 #include <boost/geometry/algorithms/num_interior_rings.hpp> 49 #include <boost/geometry/algorithms/validity_failure_type.hpp> 50 #include <boost/geometry/algorithms/detail/point_on_border.hpp> 51 #include <boost/geometry/algorithms/within.hpp> 52 53 #include <boost/geometry/algorithms/detail/check_iterator_range.hpp> 54 #include <boost/geometry/algorithms/detail/partition.hpp> 55 56 #include <boost/geometry/algorithms/detail/is_valid/complement_graph.hpp> 57 #include <boost/geometry/algorithms/detail/is_valid/has_valid_self_turns.hpp> 58 #include <boost/geometry/algorithms/detail/is_valid/is_acceptable_turn.hpp> 59 #include <boost/geometry/algorithms/detail/is_valid/ring.hpp> 60 61 #include <boost/geometry/algorithms/detail/is_valid/debug_print_turns.hpp> 62 #include <boost/geometry/algorithms/detail/is_valid/debug_validity_phase.hpp> 63 #include <boost/geometry/algorithms/detail/is_valid/debug_complement_graph.hpp> 64 65 #include <boost/geometry/algorithms/dispatch/is_valid.hpp> 66 67 68 // TEMP 69 #include <boost/geometry/strategies/envelope/cartesian.hpp> 70 #include <boost/geometry/strategies/envelope/geographic.hpp> 71 #include <boost/geometry/strategies/envelope/spherical.hpp> 72 73 74 namespace boost { namespace geometry 75 { 76 77 78 #ifndef DOXYGEN_NO_DETAIL 79 namespace detail { namespace is_valid 80 { 81 82 83 template <typename Polygon, bool CheckRingValidityOnly = false> 84 class is_valid_polygon 85 { 86 protected: 87 88 template <typename VisitPolicy, typename Strategy> 89 struct per_ring 90 { per_ringboost::geometry::detail::is_valid::is_valid_polygon::per_ring91 per_ring(VisitPolicy& policy, Strategy const& strategy) 92 : m_policy(policy) 93 , m_strategy(strategy) 94 {} 95 96 template <typename Ring> applyboost::geometry::detail::is_valid::is_valid_polygon::per_ring97 inline bool apply(Ring const& ring) const 98 { 99 return detail::is_valid::is_valid_ring 100 < 101 Ring, false, true 102 >::apply(ring, m_policy, m_strategy); 103 } 104 105 VisitPolicy& m_policy; 106 Strategy const& m_strategy; 107 }; 108 109 template <typename InteriorRings, typename VisitPolicy, typename Strategy> has_valid_interior_rings(InteriorRings const & interior_rings,VisitPolicy & visitor,Strategy const & strategy)110 static bool has_valid_interior_rings(InteriorRings const& interior_rings, 111 VisitPolicy& visitor, 112 Strategy const& strategy) 113 { 114 return 115 detail::check_iterator_range 116 < 117 per_ring<VisitPolicy, Strategy>, 118 true // allow for empty interior ring range 119 >::apply(boost::begin(interior_rings), 120 boost::end(interior_rings), 121 per_ring<VisitPolicy, Strategy>(visitor, strategy)); 122 } 123 124 struct has_valid_rings 125 { 126 template <typename VisitPolicy, typename Strategy> applyboost::geometry::detail::is_valid::is_valid_polygon::has_valid_rings127 static inline bool apply(Polygon const& polygon, 128 VisitPolicy& visitor, 129 Strategy const& strategy) 130 { 131 typedef debug_validity_phase<Polygon> debug_phase; 132 typedef typename ring_type<Polygon>::type ring_type; 133 134 // check validity of exterior ring 135 debug_phase::apply(1); 136 137 if (! detail::is_valid::is_valid_ring 138 < 139 ring_type, 140 false // do not check self intersections 141 >::apply(exterior_ring(polygon), visitor, strategy)) 142 { 143 return false; 144 } 145 146 // check validity of interior rings 147 debug_phase::apply(2); 148 149 return has_valid_interior_rings(geometry::interior_rings(polygon), 150 visitor, 151 strategy); 152 } 153 }; 154 155 156 // Iterator value_type is a Ring or Polygon 157 template <typename Iterator, typename Box> 158 struct partition_item 159 { partition_itemboost::geometry::detail::is_valid::is_valid_polygon::partition_item160 explicit partition_item(Iterator it) 161 : m_it(it) 162 , m_is_initialized(false) 163 {} 164 getboost::geometry::detail::is_valid::is_valid_polygon::partition_item165 Iterator get() const 166 { 167 return m_it; 168 } 169 170 template <typename EnvelopeStrategy> get_envelopeboost::geometry::detail::is_valid::is_valid_polygon::partition_item171 Box const& get_envelope(EnvelopeStrategy const& strategy) const 172 { 173 if (! m_is_initialized) 174 { 175 m_box = geometry::return_envelope<Box>(*m_it, strategy); 176 m_is_initialized = true; 177 } 178 return m_box; 179 } 180 181 private: 182 Iterator m_it; 183 mutable Box m_box; 184 mutable bool m_is_initialized; 185 }; 186 187 // structs for partition -- start 188 template <typename Strategy> 189 struct expand_box 190 { expand_boxboost::geometry::detail::is_valid::is_valid_polygon::expand_box191 explicit expand_box(Strategy const& strategy) 192 : m_strategy(strategy) 193 {} 194 195 template <typename Box, typename Iterator> applyboost::geometry::detail::is_valid::is_valid_polygon::expand_box196 inline void apply(Box& total, partition_item<Iterator, Box> const& item) const 197 { 198 geometry::expand(total, 199 item.get_envelope(m_strategy), 200 m_strategy); 201 } 202 203 Strategy const& m_strategy; 204 }; 205 206 template <typename Strategy> 207 struct overlaps_box 208 { overlaps_boxboost::geometry::detail::is_valid::is_valid_polygon::overlaps_box209 explicit overlaps_box(Strategy const& strategy) 210 : m_strategy(strategy) 211 {} 212 213 template <typename Box, typename Iterator> applyboost::geometry::detail::is_valid::is_valid_polygon::overlaps_box214 inline bool apply(Box const& box, partition_item<Iterator, Box> const& item) const 215 { 216 return ! geometry::disjoint(item.get_envelope(m_strategy), 217 box, 218 m_strategy); 219 } 220 221 Strategy const& m_strategy; 222 }; 223 224 225 template <typename Strategy> 226 struct item_visitor_type 227 { 228 bool items_overlap; 229 Strategy const& m_strategy; 230 item_visitor_typeboost::geometry::detail::is_valid::is_valid_polygon::item_visitor_type231 explicit item_visitor_type(Strategy const& strategy) 232 : items_overlap(false) 233 , m_strategy(strategy) 234 {} 235 236 template <typename Iterator, typename Box> applyboost::geometry::detail::is_valid::is_valid_polygon::item_visitor_type237 inline bool apply(partition_item<Iterator, Box> const& item1, 238 partition_item<Iterator, Box> const& item2) 239 { 240 typedef util::type_sequence 241 < 242 geometry::de9im::static_mask<'T'>, 243 geometry::de9im::static_mask<'*', 'T'>, 244 geometry::de9im::static_mask<'*', '*', '*', 'T'> 245 > relate_mask_t; 246 247 if ( ! items_overlap 248 && geometry::relate(*item1.get(), *item2.get(), relate_mask_t(), m_strategy) ) 249 { 250 items_overlap = true; 251 return false; // interrupt 252 } 253 return true; 254 } 255 }; 256 // structs for partition -- end 257 258 259 template 260 < 261 typename RingIterator, 262 typename ExteriorRing, 263 typename TurnIterator, 264 typename VisitPolicy, 265 typename Strategy 266 > are_holes_inside(RingIterator rings_first,RingIterator rings_beyond,ExteriorRing const & exterior_ring,TurnIterator turns_first,TurnIterator turns_beyond,VisitPolicy & visitor,Strategy const & strategy)267 static inline bool are_holes_inside(RingIterator rings_first, 268 RingIterator rings_beyond, 269 ExteriorRing const& exterior_ring, 270 TurnIterator turns_first, 271 TurnIterator turns_beyond, 272 VisitPolicy& visitor, 273 Strategy const& strategy) 274 { 275 boost::ignore_unused(visitor); 276 277 // collect the interior ring indices that have turns with the 278 // exterior ring 279 std::set<signed_size_type> ring_indices; 280 for (TurnIterator tit = turns_first; tit != turns_beyond; ++tit) 281 { 282 if (tit->operations[0].seg_id.ring_index == -1) 283 { 284 BOOST_GEOMETRY_ASSERT(tit->operations[1].seg_id.ring_index != -1); 285 ring_indices.insert(tit->operations[1].seg_id.ring_index); 286 } 287 else if (tit->operations[1].seg_id.ring_index == -1) 288 { 289 BOOST_GEOMETRY_ASSERT(tit->operations[0].seg_id.ring_index != -1); 290 ring_indices.insert(tit->operations[0].seg_id.ring_index); 291 } 292 } 293 294 signed_size_type ring_index = 0; 295 for (RingIterator it = rings_first; it != rings_beyond; 296 ++it, ++ring_index) 297 { 298 // do not examine interior rings that have turns with the 299 // exterior ring 300 if (ring_indices.find(ring_index) == ring_indices.end() 301 && ! geometry::covered_by(range::front(*it), exterior_ring, strategy)) 302 { 303 return visitor.template apply<failure_interior_rings_outside>(); 304 } 305 } 306 307 // collect all rings (exterior and/or interior) that have turns 308 for (TurnIterator tit = turns_first; tit != turns_beyond; ++tit) 309 { 310 ring_indices.insert(tit->operations[0].seg_id.ring_index); 311 ring_indices.insert(tit->operations[1].seg_id.ring_index); 312 } 313 314 typedef geometry::model::box<typename point_type<Polygon>::type> box_type; 315 typedef partition_item<RingIterator, box_type> item_type; 316 317 // put iterators for interior rings without turns in a vector 318 std::vector<item_type> ring_iterators; 319 ring_index = 0; 320 for (RingIterator it = rings_first; it != rings_beyond; 321 ++it, ++ring_index) 322 { 323 if (ring_indices.find(ring_index) == ring_indices.end()) 324 { 325 ring_iterators.push_back(item_type(it)); 326 } 327 } 328 329 // call partition to check if interior rings are disjoint from 330 // each other 331 item_visitor_type<Strategy> item_visitor(strategy); 332 333 geometry::partition 334 < 335 box_type 336 >::apply(ring_iterators, item_visitor, 337 expand_box<Strategy>(strategy), 338 overlaps_box<Strategy>(strategy)); 339 340 if (item_visitor.items_overlap) 341 { 342 return visitor.template apply<failure_nested_interior_rings>(); 343 } 344 else 345 { 346 return visitor.template apply<no_failure>(); 347 } 348 } 349 350 template 351 < 352 typename InteriorRings, 353 typename ExteriorRing, 354 typename TurnIterator, 355 typename VisitPolicy, 356 typename Strategy 357 > are_holes_inside(InteriorRings const & interior_rings,ExteriorRing const & exterior_ring,TurnIterator first,TurnIterator beyond,VisitPolicy & visitor,Strategy const & strategy)358 static inline bool are_holes_inside(InteriorRings const& interior_rings, 359 ExteriorRing const& exterior_ring, 360 TurnIterator first, 361 TurnIterator beyond, 362 VisitPolicy& visitor, 363 Strategy const& strategy) 364 { 365 return are_holes_inside(boost::begin(interior_rings), 366 boost::end(interior_rings), 367 exterior_ring, 368 first, 369 beyond, 370 visitor, 371 strategy); 372 } 373 374 struct has_holes_inside 375 { 376 template <typename TurnIterator, typename VisitPolicy, typename Strategy> applyboost::geometry::detail::is_valid::is_valid_polygon::has_holes_inside377 static inline bool apply(Polygon const& polygon, 378 TurnIterator first, 379 TurnIterator beyond, 380 VisitPolicy& visitor, 381 Strategy const& strategy) 382 { 383 return are_holes_inside(geometry::interior_rings(polygon), 384 geometry::exterior_ring(polygon), 385 first, 386 beyond, 387 visitor, 388 strategy); 389 } 390 }; 391 392 393 394 395 struct has_connected_interior 396 { 397 template <typename TurnIterator, typename VisitPolicy, typename Strategy> applyboost::geometry::detail::is_valid::is_valid_polygon::has_connected_interior398 static inline bool apply(Polygon const& polygon, 399 TurnIterator first, 400 TurnIterator beyond, 401 VisitPolicy& visitor, 402 Strategy const& ) 403 { 404 boost::ignore_unused(visitor); 405 406 typedef typename std::iterator_traits 407 < 408 TurnIterator 409 >::value_type turn_type; 410 typedef complement_graph 411 < 412 typename turn_type::point_type, 413 typename Strategy::cs_tag 414 > graph; 415 416 graph g(geometry::num_interior_rings(polygon) + 1); 417 for (TurnIterator tit = first; tit != beyond; ++tit) 418 { 419 typename graph::vertex_handle v1 = g.add_vertex 420 ( tit->operations[0].seg_id.ring_index + 1 ); 421 typename graph::vertex_handle v2 = g.add_vertex 422 ( tit->operations[1].seg_id.ring_index + 1 ); 423 typename graph::vertex_handle vip = g.add_vertex(tit->point); 424 425 g.add_edge(v1, vip); 426 g.add_edge(v2, vip); 427 } 428 429 #ifdef BOOST_GEOMETRY_TEST_DEBUG 430 debug_print_complement_graph(std::cout, g); 431 #endif // BOOST_GEOMETRY_TEST_DEBUG 432 433 if (g.has_cycles()) 434 { 435 return visitor.template apply<failure_disconnected_interior>(); 436 } 437 else 438 { 439 return visitor.template apply<no_failure>(); 440 } 441 } 442 }; 443 444 public: 445 template <typename VisitPolicy, typename Strategy> apply(Polygon const & polygon,VisitPolicy & visitor,Strategy const & strategy)446 static inline bool apply(Polygon const& polygon, 447 VisitPolicy& visitor, 448 Strategy const& strategy) 449 { 450 if (! has_valid_rings::apply(polygon, visitor, strategy)) 451 { 452 return false; 453 } 454 455 if (BOOST_GEOMETRY_CONDITION(CheckRingValidityOnly)) 456 { 457 return true; 458 } 459 460 // compute turns and check if all are acceptable 461 typedef debug_validity_phase<Polygon> debug_phase; 462 debug_phase::apply(3); 463 464 typedef has_valid_self_turns<Polygon, typename Strategy::cs_tag> has_valid_turns; 465 466 std::deque<typename has_valid_turns::turn_type> turns; 467 bool has_invalid_turns 468 = ! has_valid_turns::apply(polygon, turns, visitor, strategy); 469 debug_print_turns(turns.begin(), turns.end()); 470 471 if (has_invalid_turns) 472 { 473 return false; 474 } 475 476 // check if all interior rings are inside the exterior ring 477 debug_phase::apply(4); 478 479 if (! has_holes_inside::apply(polygon, 480 turns.begin(), turns.end(), 481 visitor, 482 strategy)) 483 { 484 return false; 485 } 486 487 // check whether the interior of the polygon is a connected set 488 debug_phase::apply(5); 489 490 return has_connected_interior::apply(polygon, 491 turns.begin(), 492 turns.end(), 493 visitor, 494 strategy); 495 } 496 }; 497 498 499 }} // namespace detail::is_valid 500 #endif // DOXYGEN_NO_DETAIL 501 502 503 504 #ifndef DOXYGEN_NO_DISPATCH 505 namespace dispatch 506 { 507 508 509 // A Polygon is always a simple geometric object provided that it is valid. 510 // 511 // Reference (for validity of Polygons): OGC 06-103r4 (6.1.11.1) 512 template <typename Polygon, bool AllowEmptyMultiGeometries> 513 struct is_valid 514 < 515 Polygon, polygon_tag, AllowEmptyMultiGeometries 516 > : detail::is_valid::is_valid_polygon<Polygon> 517 {}; 518 519 520 } // namespace dispatch 521 #endif // DOXYGEN_NO_DISPATCH 522 523 524 }} // namespace boost::geometry 525 526 #endif // BOOST_GEOMETRY_ALGORITHMS_DETAIL_IS_VALID_POLYGON_HPP 527