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