1 // Boost.Geometry (aka GGL, Generic Geometry Library) 2 3 // Copyright (c) 2017 Adam Wulkiewicz, Lodz, Poland. 4 5 // Copyright (c) 2014-2018, 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 typedef debug_validity_phase<Polygon> debug_phase; 80 81 template <typename VisitPolicy, typename Strategy> 82 struct per_ring 83 { per_ringboost::geometry::detail::is_valid::is_valid_polygon::per_ring84 per_ring(VisitPolicy& policy, Strategy const& strategy) 85 : m_policy(policy) 86 , m_strategy(strategy) 87 {} 88 89 template <typename Ring> applyboost::geometry::detail::is_valid::is_valid_polygon::per_ring90 inline bool apply(Ring const& ring) const 91 { 92 return detail::is_valid::is_valid_ring 93 < 94 Ring, false, true 95 >::apply(ring, m_policy, m_strategy); 96 } 97 98 VisitPolicy& m_policy; 99 Strategy const& m_strategy; 100 }; 101 102 template <typename InteriorRings, typename VisitPolicy, typename Strategy> has_valid_interior_rings(InteriorRings const & interior_rings,VisitPolicy & visitor,Strategy const & strategy)103 static bool has_valid_interior_rings(InteriorRings const& interior_rings, 104 VisitPolicy& visitor, 105 Strategy const& strategy) 106 { 107 return 108 detail::check_iterator_range 109 < 110 per_ring<VisitPolicy, Strategy>, 111 true // allow for empty interior ring range 112 >::apply(boost::begin(interior_rings), 113 boost::end(interior_rings), 114 per_ring<VisitPolicy, Strategy>(visitor, strategy)); 115 } 116 117 struct has_valid_rings 118 { 119 template <typename VisitPolicy, typename Strategy> applyboost::geometry::detail::is_valid::is_valid_polygon::has_valid_rings120 static inline bool apply(Polygon const& polygon, 121 VisitPolicy& visitor, 122 Strategy const& strategy) 123 { 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) : m_strategy(strategy) {} 184 185 template <typename Box, typename Iterator> applyboost::geometry::detail::is_valid::is_valid_polygon::expand_box186 inline void apply(Box& total, partition_item<Iterator, Box> const& item) const 187 { 188 geometry::expand(total, item.get_envelope(m_strategy)); 189 } 190 191 EnvelopeStrategy const& m_strategy; 192 }; 193 194 template <typename EnvelopeStrategy> 195 struct overlaps_box 196 { overlaps_boxboost::geometry::detail::is_valid::is_valid_polygon::overlaps_box197 explicit overlaps_box(EnvelopeStrategy const& strategy) : m_strategy(strategy) {} 198 199 template <typename Box, typename Iterator> applyboost::geometry::detail::is_valid::is_valid_polygon::overlaps_box200 inline bool apply(Box const& box, partition_item<Iterator, Box> const& item) const 201 { 202 return ! geometry::disjoint(item.get_envelope(m_strategy), box); 203 } 204 205 EnvelopeStrategy const& m_strategy; 206 }; 207 208 209 template <typename WithinStrategy> 210 struct item_visitor_type 211 { 212 bool items_overlap; 213 WithinStrategy const& m_strategy; 214 item_visitor_typeboost::geometry::detail::is_valid::is_valid_polygon::item_visitor_type215 explicit item_visitor_type(WithinStrategy const& strategy) 216 : items_overlap(false) 217 , m_strategy(strategy) 218 {} 219 220 template <typename Iterator, typename Box> applyboost::geometry::detail::is_valid::is_valid_polygon::item_visitor_type221 inline bool apply(partition_item<Iterator, Box> const& item1, 222 partition_item<Iterator, Box> const& item2) 223 { 224 typedef boost::mpl::vector 225 < 226 geometry::de9im::static_mask<'T'>, 227 geometry::de9im::static_mask<'*', 'T'>, 228 geometry::de9im::static_mask<'*', '*', '*', 'T'> 229 > relate_mask_t; 230 231 if ( ! items_overlap 232 && geometry::relate(*item1.get(), *item2.get(), relate_mask_t(), m_strategy) ) 233 { 234 items_overlap = true; 235 return false; // interrupt 236 } 237 return true; 238 } 239 }; 240 // structs for partition -- end 241 242 243 template 244 < 245 typename RingIterator, 246 typename ExteriorRing, 247 typename TurnIterator, 248 typename VisitPolicy, 249 typename Strategy 250 > are_holes_inside(RingIterator rings_first,RingIterator rings_beyond,ExteriorRing const & exterior_ring,TurnIterator turns_first,TurnIterator turns_beyond,VisitPolicy & visitor,Strategy const & strategy)251 static inline bool are_holes_inside(RingIterator rings_first, 252 RingIterator rings_beyond, 253 ExteriorRing const& exterior_ring, 254 TurnIterator turns_first, 255 TurnIterator turns_beyond, 256 VisitPolicy& visitor, 257 Strategy const& strategy) 258 { 259 boost::ignore_unused(visitor); 260 261 // collect the interior ring indices that have turns with the 262 // exterior ring 263 std::set<signed_size_type> ring_indices; 264 for (TurnIterator tit = turns_first; tit != turns_beyond; ++tit) 265 { 266 if (tit->operations[0].seg_id.ring_index == -1) 267 { 268 BOOST_GEOMETRY_ASSERT(tit->operations[1].seg_id.ring_index != -1); 269 ring_indices.insert(tit->operations[1].seg_id.ring_index); 270 } 271 else if (tit->operations[1].seg_id.ring_index == -1) 272 { 273 BOOST_GEOMETRY_ASSERT(tit->operations[0].seg_id.ring_index != -1); 274 ring_indices.insert(tit->operations[0].seg_id.ring_index); 275 } 276 } 277 278 // prepare strategy 279 typedef typename std::iterator_traits<RingIterator>::value_type inter_ring_type; 280 typename Strategy::template point_in_geometry_strategy 281 < 282 inter_ring_type, ExteriorRing 283 >::type const in_exterior_strategy 284 = strategy.template get_point_in_geometry_strategy<inter_ring_type, ExteriorRing>(); 285 286 signed_size_type ring_index = 0; 287 for (RingIterator it = rings_first; it != rings_beyond; 288 ++it, ++ring_index) 289 { 290 // do not examine interior rings that have turns with the 291 // exterior ring 292 if (ring_indices.find(ring_index) == ring_indices.end() 293 && ! geometry::covered_by(range::front(*it), exterior_ring, in_exterior_strategy)) 294 { 295 return visitor.template apply<failure_interior_rings_outside>(); 296 } 297 } 298 299 // collect all rings (exterior and/or interior) that have turns 300 for (TurnIterator tit = turns_first; tit != turns_beyond; ++tit) 301 { 302 ring_indices.insert(tit->operations[0].seg_id.ring_index); 303 ring_indices.insert(tit->operations[1].seg_id.ring_index); 304 } 305 306 typedef geometry::model::box<typename point_type<Polygon>::type> box_type; 307 typedef partition_item<RingIterator, box_type> item_type; 308 309 // put iterators for interior rings without turns in a vector 310 std::vector<item_type> ring_iterators; 311 ring_index = 0; 312 for (RingIterator it = rings_first; it != rings_beyond; 313 ++it, ++ring_index) 314 { 315 if (ring_indices.find(ring_index) == ring_indices.end()) 316 { 317 ring_iterators.push_back(item_type(it)); 318 } 319 } 320 321 // prepare strategies 322 typedef typename Strategy::envelope_strategy_type envelope_strategy_type; 323 envelope_strategy_type const envelope_strategy 324 = strategy.get_envelope_strategy(); 325 326 // call partition to check if interior rings are disjoint from 327 // each other 328 item_visitor_type<Strategy> item_visitor(strategy); 329 330 geometry::partition 331 < 332 box_type 333 >::apply(ring_iterators, item_visitor, 334 expand_box<envelope_strategy_type>(envelope_strategy), 335 overlaps_box<envelope_strategy_type>(envelope_strategy)); 336 337 if (item_visitor.items_overlap) 338 { 339 return visitor.template apply<failure_nested_interior_rings>(); 340 } 341 else 342 { 343 return visitor.template apply<no_failure>(); 344 } 345 } 346 347 template 348 < 349 typename InteriorRings, 350 typename ExteriorRing, 351 typename TurnIterator, 352 typename VisitPolicy, 353 typename Strategy 354 > are_holes_inside(InteriorRings const & interior_rings,ExteriorRing const & exterior_ring,TurnIterator first,TurnIterator beyond,VisitPolicy & visitor,Strategy const & strategy)355 static inline bool are_holes_inside(InteriorRings const& interior_rings, 356 ExteriorRing const& exterior_ring, 357 TurnIterator first, 358 TurnIterator beyond, 359 VisitPolicy& visitor, 360 Strategy const& strategy) 361 { 362 return are_holes_inside(boost::begin(interior_rings), 363 boost::end(interior_rings), 364 exterior_ring, 365 first, 366 beyond, 367 visitor, 368 strategy); 369 } 370 371 struct has_holes_inside 372 { 373 template <typename TurnIterator, typename VisitPolicy, typename Strategy> applyboost::geometry::detail::is_valid::is_valid_polygon::has_holes_inside374 static inline bool apply(Polygon const& polygon, 375 TurnIterator first, 376 TurnIterator beyond, 377 VisitPolicy& visitor, 378 Strategy const& strategy) 379 { 380 return are_holes_inside(geometry::interior_rings(polygon), 381 geometry::exterior_ring(polygon), 382 first, 383 beyond, 384 visitor, 385 strategy); 386 } 387 }; 388 389 390 391 392 struct has_connected_interior 393 { 394 template <typename TurnIterator, typename VisitPolicy, typename Strategy> applyboost::geometry::detail::is_valid::is_valid_polygon::has_connected_interior395 static inline bool apply(Polygon const& polygon, 396 TurnIterator first, 397 TurnIterator beyond, 398 VisitPolicy& visitor, 399 Strategy const& ) 400 { 401 boost::ignore_unused(visitor); 402 403 typedef typename std::iterator_traits 404 < 405 TurnIterator 406 >::value_type turn_type; 407 typedef complement_graph<typename turn_type::point_type> graph; 408 409 graph g(geometry::num_interior_rings(polygon) + 1); 410 for (TurnIterator tit = first; tit != beyond; ++tit) 411 { 412 typename graph::vertex_handle v1 = g.add_vertex 413 ( tit->operations[0].seg_id.ring_index + 1 ); 414 typename graph::vertex_handle v2 = g.add_vertex 415 ( tit->operations[1].seg_id.ring_index + 1 ); 416 typename graph::vertex_handle vip = g.add_vertex(tit->point); 417 418 g.add_edge(v1, vip); 419 g.add_edge(v2, vip); 420 } 421 422 #ifdef BOOST_GEOMETRY_TEST_DEBUG 423 debug_print_complement_graph(std::cout, g); 424 #endif // BOOST_GEOMETRY_TEST_DEBUG 425 426 if (g.has_cycles()) 427 { 428 return visitor.template apply<failure_disconnected_interior>(); 429 } 430 else 431 { 432 return visitor.template apply<no_failure>(); 433 } 434 } 435 }; 436 437 public: 438 template <typename VisitPolicy, typename Strategy> apply(Polygon const & polygon,VisitPolicy & visitor,Strategy const & strategy)439 static inline bool apply(Polygon const& polygon, 440 VisitPolicy& visitor, 441 Strategy const& strategy) 442 { 443 if (! has_valid_rings::apply(polygon, visitor, strategy)) 444 { 445 return false; 446 } 447 448 if (BOOST_GEOMETRY_CONDITION(CheckRingValidityOnly)) 449 { 450 return true; 451 } 452 453 // compute turns and check if all are acceptable 454 debug_phase::apply(3); 455 456 typedef has_valid_self_turns<Polygon> has_valid_turns; 457 458 std::deque<typename has_valid_turns::turn_type> turns; 459 bool has_invalid_turns 460 = ! has_valid_turns::apply(polygon, turns, visitor, strategy); 461 debug_print_turns(turns.begin(), turns.end()); 462 463 if (has_invalid_turns) 464 { 465 return false; 466 } 467 468 // check if all interior rings are inside the exterior ring 469 debug_phase::apply(4); 470 471 if (! has_holes_inside::apply(polygon, 472 turns.begin(), turns.end(), 473 visitor, 474 strategy)) 475 { 476 return false; 477 } 478 479 // check whether the interior of the polygon is a connected set 480 debug_phase::apply(5); 481 482 return has_connected_interior::apply(polygon, 483 turns.begin(), 484 turns.end(), 485 visitor, 486 strategy); 487 } 488 }; 489 490 491 }} // namespace detail::is_valid 492 #endif // DOXYGEN_NO_DETAIL 493 494 495 496 #ifndef DOXYGEN_NO_DISPATCH 497 namespace dispatch 498 { 499 500 501 // A Polygon is always a simple geometric object provided that it is valid. 502 // 503 // Reference (for validity of Polygons): OGC 06-103r4 (6.1.11.1) 504 template <typename Polygon, bool AllowEmptyMultiGeometries> 505 struct is_valid 506 < 507 Polygon, polygon_tag, AllowEmptyMultiGeometries 508 > : detail::is_valid::is_valid_polygon<Polygon> 509 {}; 510 511 512 } // namespace dispatch 513 #endif // DOXYGEN_NO_DISPATCH 514 515 516 }} // namespace boost::geometry 517 518 #endif // BOOST_GEOMETRY_ALGORITHMS_DETAIL_IS_VALID_POLYGON_HPP 519