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-2017, 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     {
  84         per_ring(VisitPolicy& policy, Strategy const& strategy)
  85             : m_policy(policy)
  86             , m_strategy(strategy)
  87         {}
  88
  89         template <typename Ring>
  90         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>
 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>
 120         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     {
 152         explicit partition_item(Iterator it)
 153             : m_it(it)
 154             , m_is_initialized(false)
 155         {}
 156
 157         Iterator get() const
 158         {
 159             return m_it;
 160         }
 161
 162         template <typename EnvelopeStrategy>
 163         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     {
 183         explicit expand_box(EnvelopeStrategy const& strategy) : m_strategy(strategy) {}
 184
 185         template <typename Box, typename Iterator>
 186         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     {
 197         explicit overlaps_box(EnvelopeStrategy const& strategy) : m_strategy(strategy) {}
 198
 199         template <typename Box, typename Iterator>
 200         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
 215         explicit item_visitor_type(WithinStrategy const& strategy)
 216             : items_overlap(false)
 217             , m_strategy(strategy)
 218         {}
 219
 220         template <typename Item>
 221         inline bool is_within(Item const& first, Item const& second)
 222         {
 223             typename point_type<Polygon>::type point;
 224             typedef detail::point_on_border::point_on_range<true> pob;
 225
 226             // TODO: this should check for a point on the interior, instead
 227             // of on border. Or it should check using the overlap function.
 228
 229             return pob::apply(point, points_begin(first), points_end(first))
 230                     && geometry::within(point, second, m_strategy);
 231         }
 232
 233         template <typename Iterator, typename Box>
 234         inline bool apply(partition_item<Iterator, Box> const& item1,
 235                           partition_item<Iterator, Box> const& item2)
 236         {
 237             if (! items_overlap
 238                 && (is_within(*item1.get(), *item2.get())
 239                   || is_within(*item2.get(), *item1.get())))
 240             {
 241                 items_overlap = true;
 242                 return false; // interrupt
 243             }
 244             return true;
 245         }
 246     };
 247     // structs for partition -- end
 248
 249
 250     template
 251     <
 252         typename RingIterator,
 253         typename ExteriorRing,
 254         typename TurnIterator,
 255         typename VisitPolicy,
 256         typename Strategy
 257     >
 258     static inline bool are_holes_inside(RingIterator rings_first,
 259                                         RingIterator rings_beyond,
 260                                         ExteriorRing const& exterior_ring,
 261                                         TurnIterator turns_first,
 262                                         TurnIterator turns_beyond,
 263                                         VisitPolicy& visitor,
 264                                         Strategy const& strategy)
 265     {
 266         boost::ignore_unused(visitor);
 267
 268         // collect the interior ring indices that have turns with the
 269         // exterior ring
 270         std::set<signed_size_type> ring_indices;
 271         for (TurnIterator tit = turns_first; tit != turns_beyond; ++tit)
 272         {
 273             if (tit->operations[0].seg_id.ring_index == -1)
 274             {
 275                 BOOST_GEOMETRY_ASSERT(tit->operations[1].seg_id.ring_index != -1);
 276                 ring_indices.insert(tit->operations[1].seg_id.ring_index);
 277             }
 278             else if (tit->operations[1].seg_id.ring_index == -1)
 279             {
 280                 BOOST_GEOMETRY_ASSERT(tit->operations[0].seg_id.ring_index != -1);
 281                 ring_indices.insert(tit->operations[0].seg_id.ring_index);
 282             }
 283         }
 284
 285         // prepare strategy
 286         typedef typename std::iterator_traits<RingIterator>::value_type inter_ring_type;
 287         typename Strategy::template point_in_geometry_strategy
 288             <
 289                 inter_ring_type, ExteriorRing
 290             >::type const in_exterior_strategy
 291             = strategy.template get_point_in_geometry_strategy<inter_ring_type, ExteriorRing>();
 292
 293         signed_size_type ring_index = 0;
 294         for (RingIterator it = rings_first; it != rings_beyond;
 295              ++it, ++ring_index)
 296         {
 297             // do not examine interior rings that have turns with the
 298             // exterior ring
 299             if (ring_indices.find(ring_index) == ring_indices.end()
 300                 && ! geometry::covered_by(range::front(*it), exterior_ring, in_exterior_strategy))
 301             {
 302                 return visitor.template apply<failure_interior_rings_outside>();
 303             }
 304         }
 305
 306         // collect all rings (exterior and/or interior) that have turns
 307         for (TurnIterator tit = turns_first; tit != turns_beyond; ++tit)
 308         {
 309             ring_indices.insert(tit->operations[0].seg_id.ring_index);
 310             ring_indices.insert(tit->operations[1].seg_id.ring_index);
 311         }
 312
 313         typedef geometry::model::box<typename point_type<Polygon>::type> box_type;
 314         typedef partition_item<RingIterator, box_type> item_type;
 315
 316         // put iterators for interior rings without turns in a vector
 317         std::vector<item_type> ring_iterators;
 318         ring_index = 0;
 319         for (RingIterator it = rings_first; it != rings_beyond;
 320              ++it, ++ring_index)
 321         {
 322             if (ring_indices.find(ring_index) == ring_indices.end())
 323             {
 324                 ring_iterators.push_back(item_type(it));
 325             }
 326         }
 327
 328         // prepare strategies
 329         typedef typename Strategy::template point_in_geometry_strategy
 330             <
 331                 inter_ring_type, inter_ring_type
 332             >::type in_interior_strategy_type;
 333         in_interior_strategy_type const in_interior_strategy
 334             = strategy.template get_point_in_geometry_strategy<inter_ring_type, inter_ring_type>();
 335         typedef typename Strategy::envelope_strategy_type envelope_strategy_type;
 336         envelope_strategy_type const envelope_strategy
 337             = strategy.get_envelope_strategy();
 338
 339         // call partition to check if interior rings are disjoint from
 340         // each other
 341         item_visitor_type<in_interior_strategy_type> item_visitor(in_interior_strategy);
 342
 343         geometry::partition
 344             <
 345                 box_type
 346             >::apply(ring_iterators, item_visitor,
 347                      expand_box<envelope_strategy_type>(envelope_strategy),
 348                      overlaps_box<envelope_strategy_type>(envelope_strategy));
 349
 350         if (item_visitor.items_overlap)
 351         {
 352             return visitor.template apply<failure_nested_interior_rings>();
 353         }
 354         else
 355         {
 356             return visitor.template apply<no_failure>();
 357         }
 358     }
 359
 360     template
 361     <
 362         typename InteriorRings,
 363         typename ExteriorRing,
 364         typename TurnIterator,
 365         typename VisitPolicy,
 366         typename Strategy
 367     >
 368     static inline bool are_holes_inside(InteriorRings const& interior_rings,
 369                                         ExteriorRing const& exterior_ring,
 370                                         TurnIterator first,
 371                                         TurnIterator beyond,
 372                                         VisitPolicy& visitor,
 373                                         Strategy const& strategy)
 374     {
 375         return are_holes_inside(boost::begin(interior_rings),
 376                                 boost::end(interior_rings),
 377                                 exterior_ring,
 378                                 first,
 379                                 beyond,
 380                                 visitor,
 381                                 strategy);
 382     }
 383
 384     struct has_holes_inside
 385     {
 386         template <typename TurnIterator, typename VisitPolicy, typename Strategy>
 387         static inline bool apply(Polygon const& polygon,
 388                                  TurnIterator first,
 389                                  TurnIterator beyond,
 390                                  VisitPolicy& visitor,
 391                                  Strategy const& strategy)
 392         {
 393             return are_holes_inside(geometry::interior_rings(polygon),
 394                                     geometry::exterior_ring(polygon),
 395                                     first,
 396                                     beyond,
 397                                     visitor,
 398                                     strategy);
 399         }
 400     };
 401
 402
 403
 404
 405     struct has_connected_interior
 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& )
 413         {
 414             boost::ignore_unused(visitor);
 415
 416             typedef typename std::iterator_traits
 417                 <
 418                     TurnIterator
 419                 >::value_type turn_type;
 420             typedef complement_graph<typename turn_type::point_type> graph;
 421
 422             graph g(geometry::num_interior_rings(polygon) + 1);
 423             for (TurnIterator tit = first; tit != beyond; ++tit)
 424             {
 425                 typename graph::vertex_handle v1 = g.add_vertex
 426                     ( tit->operations[0].seg_id.ring_index + 1 );
 427                 typename graph::vertex_handle v2 = g.add_vertex
 428                     ( tit->operations[1].seg_id.ring_index + 1 );
 429                 typename graph::vertex_handle vip = g.add_vertex(tit->point);
 430
 431                 g.add_edge(v1, vip);
 432                 g.add_edge(v2, vip);
 433             }
 434
 435 #ifdef BOOST_GEOMETRY_TEST_DEBUG
 436             debug_print_complement_graph(std::cout, g);
 437 #endif // BOOST_GEOMETRY_TEST_DEBUG
 438
 439             if (g.has_cycles())
 440             {
 441                 return visitor.template apply<failure_disconnected_interior>();
 442             }
 443             else
 444             {
 445                 return visitor.template apply<no_failure>();
 446             }
 447         }
 448     };
 449
 450 public:
 451     template <typename VisitPolicy, typename Strategy>
 452     static inline bool apply(Polygon const& polygon,
 453                              VisitPolicy& visitor,
 454                              Strategy const& strategy)
 455     {
 456         if (! has_valid_rings::apply(polygon, visitor, strategy))
 457         {
 458             return false;
 459         }
 460
 461         if (BOOST_GEOMETRY_CONDITION(CheckRingValidityOnly))
 462         {
 463             return true;
 464         }
 465
 466         // compute turns and check if all are acceptable
 467         debug_phase::apply(3);
 468
 469         typedef has_valid_self_turns<Polygon> has_valid_turns;
 470
 471         std::deque<typename has_valid_turns::turn_type> turns;
 472         bool has_invalid_turns
 473             = ! has_valid_turns::apply(polygon, turns, visitor, strategy);
 474         debug_print_turns(turns.begin(), turns.end());
 475
 476         if (has_invalid_turns)
 477         {
 478             return false;
 479         }
 480
 481         // check if all interior rings are inside the exterior ring
 482         debug_phase::apply(4);
 483
 484         if (! has_holes_inside::apply(polygon,
 485                                       turns.begin(), turns.end(),
 486                                       visitor,
 487                                       strategy))
 488         {
 489             return false;
 490         }
 491
 492         // check whether the interior of the polygon is a connected set
 493         debug_phase::apply(5);
 494
 495         return has_connected_interior::apply(polygon,
 496                                              turns.begin(),
 497                                              turns.end(),
 498                                              visitor,
 499                                              strategy);
 500     }
 501 };
 502
 503
 504 }} // namespace detail::is_valid
 505 #endif // DOXYGEN_NO_DETAIL
 506
 507
 508
 509 #ifndef DOXYGEN_NO_DISPATCH
 510 namespace dispatch
 511 {
 512
 513
 514 // A Polygon is always a simple geometric object provided that it is valid.
 515 //
 516 // Reference (for validity of Polygons): OGC 06-103r4 (6.1.11.1)
 517 template <typename Polygon, bool AllowEmptyMultiGeometries>
 518 struct is_valid
 519     <
 520         Polygon, polygon_tag, AllowEmptyMultiGeometries
 521     > : detail::is_valid::is_valid_polygon<Polygon>
 522 {};
 523
 524
 525 } // namespace dispatch
 526 #endif // DOXYGEN_NO_DISPATCH
 527
 528
 529 }} // namespace boost::geometry
 530
 531 #endif // BOOST_GEOMETRY_ALGORITHMS_DETAIL_IS_VALID_POLYGON_HPP