detail/is_valid/polygon.hpp

0001 // Boost.Geometry (aka GGL, Generic Geometry Library)
0002
0003 // Copyright (c) 2017-2023 Adam Wulkiewicz, Lodz, Poland.
0004
0005 // Copyright (c) 2014-2023, Oracle and/or its affiliates.
0006 // Contributed and/or modified by Vissarion Fysikopoulos, on behalf of Oracle
0007 // Contributed and/or modified by Menelaos Karavelas, on behalf of Oracle
0008 // Contributed and/or modified by Adam Wulkiewicz, on behalf of Oracle
0009
0010 // Licensed under the Boost Software License version 1.0.
0011 // http://www.boost.org/users/license.html
0012
0013 #ifndef BOOST_GEOMETRY_ALGORITHMS_DETAIL_IS_VALID_POLYGON_HPP
0014 #define BOOST_GEOMETRY_ALGORITHMS_DETAIL_IS_VALID_POLYGON_HPP
0015
0016 #include <cstddef>
0017 #ifdef BOOST_GEOMETRY_TEST_DEBUG
0018 #include <iostream>
0019 #endif // BOOST_GEOMETRY_TEST_DEBUG
0020
0021 #include <algorithm>
0022 #include <deque>
0023 #include <iterator>
0024 #include <set>
0025 #include <vector>
0026
0027 #include <boost/core/ignore_unused.hpp>
0028 #include <boost/range/begin.hpp>
0029 #include <boost/range/end.hpp>
0030
0031 #include <boost/geometry/core/assert.hpp>
0032 #include <boost/geometry/core/exterior_ring.hpp>
0033 #include <boost/geometry/core/interior_rings.hpp>
0034 #include <boost/geometry/core/ring_type.hpp>
0035 #include <boost/geometry/core/tags.hpp>
0036
0037 #include <boost/geometry/util/constexpr.hpp>
0038 #include <boost/geometry/util/range.hpp>
0039 #include <boost/geometry/util/sequence.hpp>
0040
0041 #include <boost/geometry/geometries/box.hpp>
0042
0043 #include <boost/geometry/iterators/point_iterator.hpp>
0044
0045 #include <boost/geometry/algorithms/covered_by.hpp>
0046 #include <boost/geometry/algorithms/disjoint.hpp>
0047 #include <boost/geometry/algorithms/expand.hpp>
0048 #include <boost/geometry/algorithms/num_interior_rings.hpp>
0049 #include <boost/geometry/algorithms/validity_failure_type.hpp>
0050 #include <boost/geometry/algorithms/detail/point_on_border.hpp>
0051 #include <boost/geometry/algorithms/within.hpp>
0052
0053 #include <boost/geometry/algorithms/detail/partition.hpp>
0054
0055 #include <boost/geometry/algorithms/detail/is_valid/complement_graph.hpp>
0056 #include <boost/geometry/algorithms/detail/is_valid/has_valid_self_turns.hpp>
0057 #include <boost/geometry/algorithms/detail/is_valid/is_acceptable_turn.hpp>
0058 #include <boost/geometry/algorithms/detail/is_valid/ring.hpp>
0059
0060 #include <boost/geometry/algorithms/detail/is_valid/debug_print_turns.hpp>
0061 #include <boost/geometry/algorithms/detail/is_valid/debug_validity_phase.hpp>
0062 #include <boost/geometry/algorithms/detail/is_valid/debug_complement_graph.hpp>
0063
0064 #include <boost/geometry/algorithms/dispatch/is_valid.hpp>
0065
0066
0067 // TEMP
0068 #include <boost/geometry/strategies/envelope/cartesian.hpp>
0069 #include <boost/geometry/strategies/envelope/geographic.hpp>
0070 #include <boost/geometry/strategies/envelope/spherical.hpp>
0071
0072
0073 namespace boost { namespace geometry
0074 {
0075
0076
0077 #ifndef DOXYGEN_NO_DETAIL
0078 namespace detail { namespace is_valid
0079 {
0080
0081
0082 template <typename Polygon, bool CheckRingValidityOnly = false>
0083 class is_valid_polygon
0084 {
0085 protected:
0086
0087     template <typename VisitPolicy, typename Strategy>
0088     struct is_invalid_ring
0089     {
0090         is_invalid_ring(VisitPolicy& policy, Strategy const& strategy)
0091             : m_policy(policy)
0092             , m_strategy(strategy)
0093         {}
0094
0095         template <typename Ring>
0096         inline bool operator()(Ring const& ring) const
0097         {
0098             return ! detail::is_valid::is_valid_ring
0099                 <
0100                     Ring, false, true
0101                 >::apply(ring, m_policy, m_strategy);
0102         }
0103
0104         VisitPolicy& m_policy;
0105         Strategy const& m_strategy;
0106     };
0107
0108     template <typename InteriorRings, typename VisitPolicy, typename Strategy>
0109     static bool has_valid_interior_rings(InteriorRings const& interior_rings,
0110                                          VisitPolicy& visitor,
0111                                          Strategy const& strategy)
0112     {
0113         return std::none_of(boost::begin(interior_rings),
0114                             boost::end(interior_rings),
0115                             is_invalid_ring<VisitPolicy, Strategy>(visitor, strategy));
0116     }
0117
0118     struct has_valid_rings
0119     {
0120         template <typename VisitPolicy, typename Strategy>
0121         static inline bool apply(Polygon const& polygon,
0122                                  VisitPolicy& visitor,
0123                                  Strategy const& strategy)
0124         {
0125             using debug_phase = debug_validity_phase<Polygon>;
0126
0127             // check validity of exterior ring
0128             debug_phase::apply(1);
0129
0130             if (! detail::is_valid::is_valid_ring
0131                      <
0132                          ring_type_t<Polygon>,
0133                          false // do not check self intersections
0134                      >::apply(exterior_ring(polygon), visitor, strategy))
0135             {
0136                 return false;
0137             }
0138
0139             // check validity of interior rings
0140             debug_phase::apply(2);
0141
0142             return has_valid_interior_rings(geometry::interior_rings(polygon),
0143                                             visitor,
0144                                             strategy);
0145         }
0146     };
0147
0148
0149     // Iterator value_type is a Ring or Polygon
0150     template <typename Iterator, typename Box>
0151     struct partition_item
0152     {
0153         explicit partition_item(Iterator it)
0154             : m_it(it)
0155             , m_is_initialized(false)
0156         {}
0157
0158         Iterator get() const
0159         {
0160             return m_it;
0161         }
0162
0163         template <typename EnvelopeStrategy>
0164         Box const& get_envelope(EnvelopeStrategy const& strategy) const
0165         {
0166             if (! m_is_initialized)
0167             {
0168                 m_box = geometry::return_envelope<Box>(*m_it, strategy);
0169                 m_is_initialized = true;
0170             }
0171             return m_box;
0172         }
0173
0174     private:
0175         Iterator m_it;
0176         mutable Box m_box;
0177         mutable bool m_is_initialized;
0178     };
0179
0180     // structs for partition -- start
0181     template <typename Strategy>
0182     struct expand_box
0183     {
0184         explicit expand_box(Strategy const& strategy)
0185             : m_strategy(strategy)
0186         {}
0187
0188         template <typename Box, typename Iterator>
0189         inline void apply(Box& total, partition_item<Iterator, Box> const& item) const
0190         {
0191             geometry::expand(total,
0192                              item.get_envelope(m_strategy),
0193                              m_strategy);
0194         }
0195
0196         Strategy const& m_strategy;
0197     };
0198
0199     template <typename Strategy>
0200     struct overlaps_box
0201     {
0202         explicit overlaps_box(Strategy const& strategy)
0203             : m_strategy(strategy)
0204         {}
0205
0206         template <typename Box, typename Iterator>
0207         inline bool apply(Box const& box, partition_item<Iterator, Box> const& item) const
0208         {
0209             return ! geometry::disjoint(item.get_envelope(m_strategy),
0210                                         box,
0211                                         m_strategy);
0212         }
0213
0214         Strategy const& m_strategy;
0215     };
0216
0217
0218     template <typename Strategy>
0219     struct item_visitor_type
0220     {
0221         bool items_overlap;
0222         Strategy const& m_strategy;
0223
0224         explicit item_visitor_type(Strategy const& strategy)
0225             : items_overlap(false)
0226             , m_strategy(strategy)
0227         {}
0228
0229         template <typename Iterator, typename Box>
0230         inline bool apply(partition_item<Iterator, Box> const& item1,
0231                           partition_item<Iterator, Box> const& item2)
0232         {
0233             typedef util::type_sequence
0234                 <
0235                     geometry::de9im::static_mask<'T'>,
0236                     geometry::de9im::static_mask<'*', 'T'>,
0237                     geometry::de9im::static_mask<'*', '*', '*', 'T'>
0238                 > relate_mask_t;
0239
0240             if ( ! items_overlap
0241               && geometry::relate(*item1.get(), *item2.get(), relate_mask_t(), m_strategy) )
0242             {
0243                 items_overlap = true;
0244                 return false; // interrupt
0245             }
0246             return true;
0247         }
0248     };
0249     // structs for partition -- end
0250
0251
0252     template
0253     <
0254         typename RingIterator,
0255         typename ExteriorRing,
0256         typename TurnIterator,
0257         typename VisitPolicy,
0258         typename Strategy
0259     >
0260     static inline bool are_holes_inside(RingIterator rings_first,
0261                                         RingIterator rings_beyond,
0262                                         ExteriorRing const& exterior_ring,
0263                                         TurnIterator turns_first,
0264                                         TurnIterator turns_beyond,
0265                                         VisitPolicy& visitor,
0266                                         Strategy const& strategy)
0267     {
0268         boost::ignore_unused(visitor);
0269
0270         // collect the interior ring indices that have turns with the
0271         // exterior ring
0272         std::set<signed_size_type> ring_indices;
0273         for (TurnIterator tit = turns_first; tit != turns_beyond; ++tit)
0274         {
0275             if (tit->operations[0].seg_id.ring_index == -1)
0276             {
0277                 BOOST_GEOMETRY_ASSERT(tit->operations[1].seg_id.ring_index != -1);
0278                 ring_indices.insert(tit->operations[1].seg_id.ring_index);
0279             }
0280             else if (tit->operations[1].seg_id.ring_index == -1)
0281             {
0282                 BOOST_GEOMETRY_ASSERT(tit->operations[0].seg_id.ring_index != -1);
0283                 ring_indices.insert(tit->operations[0].seg_id.ring_index);
0284             }
0285         }
0286
0287         signed_size_type ring_index = 0;
0288         for (RingIterator it = rings_first; it != rings_beyond;
0289              ++it, ++ring_index)
0290         {
0291             // do not examine interior rings that have turns with the
0292             // exterior ring
0293             if (ring_indices.find(ring_index) == ring_indices.end()
0294                 && ! geometry::covered_by(range::front(*it), exterior_ring, strategy))
0295             {
0296                 return visitor.template apply<failure_interior_rings_outside>();
0297             }
0298         }
0299
0300         // collect all rings (exterior and/or interior) that have turns
0301         for (TurnIterator tit = turns_first; tit != turns_beyond; ++tit)
0302         {
0303             ring_indices.insert(tit->operations[0].seg_id.ring_index);
0304             ring_indices.insert(tit->operations[1].seg_id.ring_index);
0305         }
0306
0307         using box_type = geometry::model::box<point_type_t<Polygon>>;
0308         using item_type = partition_item<RingIterator, box_type>;
0309
0310         // put iterators for interior rings without turns in a vector
0311         std::vector<item_type> ring_iterators;
0312         ring_index = 0;
0313         for (RingIterator it = rings_first; it != rings_beyond;
0314              ++it, ++ring_index)
0315         {
0316             if (ring_indices.find(ring_index) == ring_indices.end())
0317             {
0318                 ring_iterators.push_back(item_type(it));
0319             }
0320         }
0321
0322         // call partition to check if interior rings are disjoint from
0323         // each other
0324         item_visitor_type<Strategy> item_visitor(strategy);
0325
0326         geometry::partition
0327             <
0328                 box_type
0329             >::apply(ring_iterators, item_visitor,
0330                      expand_box<Strategy>(strategy),
0331                      overlaps_box<Strategy>(strategy));
0332
0333         if (item_visitor.items_overlap)
0334         {
0335             return visitor.template apply<failure_nested_interior_rings>();
0336         }
0337         else
0338         {
0339             return visitor.template apply<no_failure>();
0340         }
0341     }
0342
0343     template
0344     <
0345         typename InteriorRings,
0346         typename ExteriorRing,
0347         typename TurnIterator,
0348         typename VisitPolicy,
0349         typename Strategy
0350     >
0351     static inline bool are_holes_inside(InteriorRings const& interior_rings,
0352                                         ExteriorRing const& exterior_ring,
0353                                         TurnIterator first,
0354                                         TurnIterator beyond,
0355                                         VisitPolicy& visitor,
0356                                         Strategy const& strategy)
0357     {
0358         return are_holes_inside(boost::begin(interior_rings),
0359                                 boost::end(interior_rings),
0360                                 exterior_ring,
0361                                 first,
0362                                 beyond,
0363                                 visitor,
0364                                 strategy);
0365     }
0366
0367     struct has_holes_inside
0368     {
0369         template <typename TurnIterator, typename VisitPolicy, typename Strategy>
0370         static inline bool apply(Polygon const& polygon,
0371                                  TurnIterator first,
0372                                  TurnIterator beyond,
0373                                  VisitPolicy& visitor,
0374                                  Strategy const& strategy)
0375         {
0376             return are_holes_inside(geometry::interior_rings(polygon),
0377                                     geometry::exterior_ring(polygon),
0378                                     first,
0379                                     beyond,
0380                                     visitor,
0381                                     strategy);
0382         }
0383     };
0384
0385
0386
0387
0388     struct has_connected_interior
0389     {
0390         template <typename TurnIterator, typename VisitPolicy, typename Strategy>
0391         static inline bool apply(Polygon const& polygon,
0392                                  TurnIterator first,
0393                                  TurnIterator beyond,
0394                                  VisitPolicy& visitor,
0395                                  Strategy const& )
0396         {
0397             boost::ignore_unused(visitor);
0398
0399             typedef typename std::iterator_traits
0400                 <
0401                     TurnIterator
0402                 >::value_type turn_type;
0403             typedef complement_graph
0404                 <
0405                     typename turn_type::point_type,
0406                     Strategy
0407                 > graph;
0408
0409             graph g(geometry::num_interior_rings(polygon) + 1);
0410             for (TurnIterator tit = first; tit != beyond; ++tit)
0411             {
0412                 typename graph::vertex_handle v1 = g.add_vertex
0413                     ( tit->operations[0].seg_id.ring_index + 1 );
0414                 typename graph::vertex_handle v2 = g.add_vertex
0415                     ( tit->operations[1].seg_id.ring_index + 1 );
0416                 typename graph::vertex_handle vip = g.add_vertex(tit->point);
0417
0418                 g.add_edge(v1, vip);
0419                 g.add_edge(v2, vip);
0420             }
0421
0422 #ifdef BOOST_GEOMETRY_TEST_DEBUG
0423             debug_print_complement_graph(std::cout, g);
0424 #endif // BOOST_GEOMETRY_TEST_DEBUG
0425
0426             if (g.has_cycles())
0427             {
0428                 return visitor.template apply<failure_disconnected_interior>();
0429             }
0430             else
0431             {
0432                 return visitor.template apply<no_failure>();
0433             }
0434         }
0435     };
0436
0437 public:
0438     template <typename VisitPolicy, typename Strategy>
0439     static inline bool apply(Polygon const& polygon,
0440                              VisitPolicy& visitor,
0441                              Strategy const& strategy)
0442     {
0443         if (! has_valid_rings::apply(polygon, visitor, strategy))
0444         {
0445             return false;
0446         }
0447
0448         if BOOST_GEOMETRY_CONSTEXPR (CheckRingValidityOnly)
0449         {
0450             return true;
0451         }
0452         else // else prevents unreachable code warning
0453         {
0454             // compute turns and check if all are acceptable
0455             using debug_phase = debug_validity_phase<Polygon>;
0456             debug_phase::apply(3);
0457
0458             using has_valid_turns = has_valid_self_turns<Polygon, typename Strategy::cs_tag>;
0459
0460             std::deque<typename has_valid_turns::turn_type> turns;
0461             bool has_invalid_turns
0462                 = ! has_valid_turns::apply(polygon, turns, visitor, strategy);
0463             debug_print_turns(turns.begin(), turns.end());
0464
0465             if (has_invalid_turns)
0466             {
0467                 return false;
0468             }
0469
0470             // check if all interior rings are inside the exterior ring
0471             debug_phase::apply(4);
0472
0473             if (! has_holes_inside::apply(polygon,
0474                                           turns.begin(), turns.end(),
0475                                           visitor,
0476                                           strategy))
0477             {
0478                 return false;
0479             }
0480
0481             // check whether the interior of the polygon is a connected set
0482             debug_phase::apply(5);
0483
0484             return has_connected_interior::apply(polygon,
0485                                                  turns.begin(),
0486                                                  turns.end(),
0487                                                  visitor,
0488                                                  strategy);
0489         }
0490     }
0491 };
0492
0493
0494 }} // namespace detail::is_valid
0495 #endif // DOXYGEN_NO_DETAIL
0496
0497
0498
0499 #ifndef DOXYGEN_NO_DISPATCH
0500 namespace dispatch
0501 {
0502
0503
0504 // A Polygon is always a simple geometric object provided that it is valid.
0505 //
0506 // Reference (for validity of Polygons): OGC 06-103r4 (6.1.11.1)
0507 template <typename Polygon, bool AllowEmptyMultiGeometries>
0508 struct is_valid
0509     <
0510         Polygon, polygon_tag, AllowEmptyMultiGeometries
0511     > : detail::is_valid::is_valid_polygon<Polygon>
0512 {};
0513
0514
0515 } // namespace dispatch
0516 #endif // DOXYGEN_NO_DISPATCH
0517
0518
0519 }} // namespace boost::geometry
0520
0521 #endif // BOOST_GEOMETRY_ALGORITHMS_DETAIL_IS_VALID_POLYGON_HPP