ceph/src/boost/boost/geometry/algorithms/detail/is_valid/polygon.hpp

   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     {
  91         per_ring(VisitPolicy& policy, Strategy const& strategy)
  92             : m_policy(policy)
  93             , m_strategy(strategy)
  94         {}
  95
  96         template <typename Ring>
  97         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>
 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>
 127         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     {
 160         explicit partition_item(Iterator it)
 161             : m_it(it)
 162             , m_is_initialized(false)
 163         {}
 164
 165         Iterator get() const
 166         {
 167             return m_it;
 168         }
 169
 170         template <typename EnvelopeStrategy>
 171         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 EnvelopeStrategy>
 189     struct expand_box
 190     {
 191         explicit expand_box(EnvelopeStrategy const& strategy)
 192             : m_strategy(strategy)
 193         {}
 194
 195         template <typename Box, typename Iterator>
 196         inline void apply(Box& total, partition_item<Iterator, Box> const& item) const
 197         {
 198             geometry::expand(total,
 199                              item.get_envelope(m_strategy),
 200                              // TEMP - envelope umbrella strategy also contains
 201                              //        expand strategies
 202                              strategies::envelope::services::strategy_converter
 203                                 <
 204                                     EnvelopeStrategy
 205                                 >::get(m_strategy));
 206         }
 207
 208         EnvelopeStrategy const& m_strategy;
 209     };
 210
 211     template <typename EnvelopeStrategy, typename DisjointBoxBoxStrategy>
 212     struct overlaps_box
 213     {
 214         explicit overlaps_box(EnvelopeStrategy const& envelope_strategy,
 215                               DisjointBoxBoxStrategy const& disjoint_strategy)
 216             : m_envelope_strategy(envelope_strategy)
 217             , m_disjoint_strategy(disjoint_strategy)
 218         {}
 219
 220         template <typename Box, typename Iterator>
 221         inline bool apply(Box const& box, partition_item<Iterator, Box> const& item) const
 222         {
 223             return ! geometry::disjoint(item.get_envelope(m_envelope_strategy),
 224                                         box,
 225                                         m_disjoint_strategy);
 226         }
 227
 228         EnvelopeStrategy const& m_envelope_strategy;
 229         DisjointBoxBoxStrategy const& m_disjoint_strategy;
 230     };
 231
 232
 233     template <typename WithinStrategy>
 234     struct item_visitor_type
 235     {
 236         bool items_overlap;
 237         WithinStrategy const& m_strategy;
 238
 239         explicit item_visitor_type(WithinStrategy const& strategy)
 240             : items_overlap(false)
 241             , m_strategy(strategy)
 242         {}
 243
 244         template <typename Iterator, typename Box>
 245         inline bool apply(partition_item<Iterator, Box> const& item1,
 246                           partition_item<Iterator, Box> const& item2)
 247         {
 248             typedef util::type_sequence
 249                 <
 250                     geometry::de9im::static_mask<'T'>,
 251                     geometry::de9im::static_mask<'*', 'T'>,
 252                     geometry::de9im::static_mask<'*', '*', '*', 'T'>
 253                 > relate_mask_t;
 254
 255             if ( ! items_overlap
 256               && geometry::relate(*item1.get(), *item2.get(), relate_mask_t(), m_strategy) )
 257             {
 258                 items_overlap = true;
 259                 return false; // interrupt
 260             }
 261             return true;
 262         }
 263     };
 264     // structs for partition -- end
 265
 266
 267     template
 268     <
 269         typename RingIterator,
 270         typename ExteriorRing,
 271         typename TurnIterator,
 272         typename VisitPolicy,
 273         typename Strategy
 274     >
 275     static inline bool are_holes_inside(RingIterator rings_first,
 276                                         RingIterator rings_beyond,
 277                                         ExteriorRing const& exterior_ring,
 278                                         TurnIterator turns_first,
 279                                         TurnIterator turns_beyond,
 280                                         VisitPolicy& visitor,
 281                                         Strategy const& strategy)
 282     {
 283         boost::ignore_unused(visitor);
 284
 285         // collect the interior ring indices that have turns with the
 286         // exterior ring
 287         std::set<signed_size_type> ring_indices;
 288         for (TurnIterator tit = turns_first; tit != turns_beyond; ++tit)
 289         {
 290             if (tit->operations[0].seg_id.ring_index == -1)
 291             {
 292                 BOOST_GEOMETRY_ASSERT(tit->operations[1].seg_id.ring_index != -1);
 293                 ring_indices.insert(tit->operations[1].seg_id.ring_index);
 294             }
 295             else if (tit->operations[1].seg_id.ring_index == -1)
 296             {
 297                 BOOST_GEOMETRY_ASSERT(tit->operations[0].seg_id.ring_index != -1);
 298                 ring_indices.insert(tit->operations[0].seg_id.ring_index);
 299             }
 300         }
 301
 302         // prepare strategy
 303         typedef typename std::iterator_traits<RingIterator>::value_type inter_ring_type;
 304         typename Strategy::template point_in_geometry_strategy
 305             <
 306                 inter_ring_type, ExteriorRing
 307             >::type const in_exterior_strategy
 308             = strategy.template get_point_in_geometry_strategy<inter_ring_type, ExteriorRing>();
 309
 310         signed_size_type ring_index = 0;
 311         for (RingIterator it = rings_first; it != rings_beyond;
 312              ++it, ++ring_index)
 313         {
 314             // do not examine interior rings that have turns with the
 315             // exterior ring
 316             if (ring_indices.find(ring_index) == ring_indices.end()
 317                 && ! geometry::covered_by(range::front(*it), exterior_ring, in_exterior_strategy))
 318             {
 319                 return visitor.template apply<failure_interior_rings_outside>();
 320             }
 321         }
 322
 323         // collect all rings (exterior and/or interior) that have turns
 324         for (TurnIterator tit = turns_first; tit != turns_beyond; ++tit)
 325         {
 326             ring_indices.insert(tit->operations[0].seg_id.ring_index);
 327             ring_indices.insert(tit->operations[1].seg_id.ring_index);
 328         }
 329
 330         typedef geometry::model::box<typename point_type<Polygon>::type> box_type;
 331         typedef partition_item<RingIterator, box_type> item_type;
 332
 333         // put iterators for interior rings without turns in a vector
 334         std::vector<item_type> ring_iterators;
 335         ring_index = 0;
 336         for (RingIterator it = rings_first; it != rings_beyond;
 337              ++it, ++ring_index)
 338         {
 339             if (ring_indices.find(ring_index) == ring_indices.end())
 340             {
 341                 ring_iterators.push_back(item_type(it));
 342             }
 343         }
 344
 345         // prepare strategies
 346         typedef typename Strategy::envelope_strategy_type envelope_strategy_type;
 347         envelope_strategy_type const envelope_strategy
 348             = strategy.get_envelope_strategy();
 349         typedef typename Strategy::disjoint_box_box_strategy_type disjoint_box_box_strategy_type;
 350         disjoint_box_box_strategy_type const disjoint_strategy
 351             = strategy.get_disjoint_box_box_strategy();
 352
 353         // call partition to check if interior rings are disjoint from
 354         // each other
 355         item_visitor_type<Strategy> item_visitor(strategy);
 356
 357         geometry::partition
 358             <
 359                 box_type
 360             >::apply(ring_iterators, item_visitor,
 361                      expand_box
 362                         <
 363                             envelope_strategy_type
 364                         >(envelope_strategy),
 365                      overlaps_box
 366                         <
 367                             envelope_strategy_type,
 368                             disjoint_box_box_strategy_type
 369                         >(envelope_strategy, disjoint_strategy));
 370
 371         if (item_visitor.items_overlap)
 372         {
 373             return visitor.template apply<failure_nested_interior_rings>();
 374         }
 375         else
 376         {
 377             return visitor.template apply<no_failure>();
 378         }
 379     }
 380
 381     template
 382     <
 383         typename InteriorRings,
 384         typename ExteriorRing,
 385         typename TurnIterator,
 386         typename VisitPolicy,
 387         typename Strategy
 388     >
 389     static inline bool are_holes_inside(InteriorRings const& interior_rings,
 390                                         ExteriorRing const& exterior_ring,
 391                                         TurnIterator first,
 392                                         TurnIterator beyond,
 393                                         VisitPolicy& visitor,
 394                                         Strategy const& strategy)
 395     {
 396         return are_holes_inside(boost::begin(interior_rings),
 397                                 boost::end(interior_rings),
 398                                 exterior_ring,
 399                                 first,
 400                                 beyond,
 401                                 visitor,
 402                                 strategy);
 403     }
 404
 405     struct has_holes_inside
 406     {
 407         template <typename TurnIterator, typename VisitPolicy, typename Strategy>
 408         static inline bool apply(Polygon const& polygon,
 409                                  TurnIterator first,
 410                                  TurnIterator beyond,
 411                                  VisitPolicy& visitor,
 412                                  Strategy const& strategy)
 413         {
 414             return are_holes_inside(geometry::interior_rings(polygon),
 415                                     geometry::exterior_ring(polygon),
 416                                     first,
 417                                     beyond,
 418                                     visitor,
 419                                     strategy);
 420         }
 421     };
 422
 423
 424
 425
 426     struct has_connected_interior
 427     {
 428         template <typename TurnIterator, typename VisitPolicy, typename Strategy>
 429         static inline bool apply(Polygon const& polygon,
 430                                  TurnIterator first,
 431                                  TurnIterator beyond,
 432                                  VisitPolicy& visitor,
 433                                  Strategy const& )
 434         {
 435             boost::ignore_unused(visitor);
 436
 437             typedef typename std::iterator_traits
 438                 <
 439                     TurnIterator
 440                 >::value_type turn_type;
 441             typedef complement_graph
 442                 <
 443                     typename turn_type::point_type,
 444                     typename Strategy::cs_tag
 445                 > graph;
 446
 447             graph g(geometry::num_interior_rings(polygon) + 1);
 448             for (TurnIterator tit = first; tit != beyond; ++tit)
 449             {
 450                 typename graph::vertex_handle v1 = g.add_vertex
 451                     ( tit->operations[0].seg_id.ring_index + 1 );
 452                 typename graph::vertex_handle v2 = g.add_vertex
 453                     ( tit->operations[1].seg_id.ring_index + 1 );
 454                 typename graph::vertex_handle vip = g.add_vertex(tit->point);
 455
 456                 g.add_edge(v1, vip);
 457                 g.add_edge(v2, vip);
 458             }
 459
 460 #ifdef BOOST_GEOMETRY_TEST_DEBUG
 461             debug_print_complement_graph(std::cout, g);
 462 #endif // BOOST_GEOMETRY_TEST_DEBUG
 463
 464             if (g.has_cycles())
 465             {
 466                 return visitor.template apply<failure_disconnected_interior>();
 467             }
 468             else
 469             {
 470                 return visitor.template apply<no_failure>();
 471             }
 472         }
 473     };
 474
 475 public:
 476     template <typename VisitPolicy, typename Strategy>
 477     static inline bool apply(Polygon const& polygon,
 478                              VisitPolicy& visitor,
 479                              Strategy const& strategy)
 480     {
 481         if (! has_valid_rings::apply(polygon, visitor, strategy))
 482         {
 483             return false;
 484         }
 485
 486         if (BOOST_GEOMETRY_CONDITION(CheckRingValidityOnly))
 487         {
 488             return true;
 489         }
 490
 491         // compute turns and check if all are acceptable
 492         typedef debug_validity_phase<Polygon> debug_phase;
 493         debug_phase::apply(3);
 494
 495         typedef has_valid_self_turns<Polygon, typename Strategy::cs_tag> has_valid_turns;
 496
 497         std::deque<typename has_valid_turns::turn_type> turns;
 498         bool has_invalid_turns
 499             = ! has_valid_turns::apply(polygon, turns, visitor, strategy);
 500         debug_print_turns(turns.begin(), turns.end());
 501
 502         if (has_invalid_turns)
 503         {
 504             return false;
 505         }
 506
 507         // check if all interior rings are inside the exterior ring
 508         debug_phase::apply(4);
 509
 510         if (! has_holes_inside::apply(polygon,
 511                                       turns.begin(), turns.end(),
 512                                       visitor,
 513                                       strategy))
 514         {
 515             return false;
 516         }
 517
 518         // check whether the interior of the polygon is a connected set
 519         debug_phase::apply(5);
 520
 521         return has_connected_interior::apply(polygon,
 522                                              turns.begin(),
 523                                              turns.end(),
 524                                              visitor,
 525                                              strategy);
 526     }
 527 };
 528
 529
 530 }} // namespace detail::is_valid
 531 #endif // DOXYGEN_NO_DETAIL
 532
 533
 534
 535 #ifndef DOXYGEN_NO_DISPATCH
 536 namespace dispatch
 537 {
 538
 539
 540 // A Polygon is always a simple geometric object provided that it is valid.
 541 //
 542 // Reference (for validity of Polygons): OGC 06-103r4 (6.1.11.1)
 543 template <typename Polygon, bool AllowEmptyMultiGeometries>
 544 struct is_valid
 545     <
 546         Polygon, polygon_tag, AllowEmptyMultiGeometries
 547     > : detail::is_valid::is_valid_polygon<Polygon>
 548 {};
 549
 550
 551 } // namespace dispatch
 552 #endif // DOXYGEN_NO_DISPATCH
 553
 554
 555 }} // namespace boost::geometry
 556
 557 #endif // BOOST_GEOMETRY_ALGORITHMS_DETAIL_IS_VALID_POLYGON_HPP