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             typedef debug_validity_phase<Polygon> debug_phase;
0126             typedef typename ring_type<Polygon>::type ring_type;
0127
0128             // check validity of exterior ring
0129             debug_phase::apply(1);
0130
0131             if (! detail::is_valid::is_valid_ring
0132                      <
0133                          ring_type,
0134                          false // do not check self intersections
0135                      >::apply(exterior_ring(polygon), visitor, strategy))
0136             {
0137                 return false;
0138             }
0139
0140             // check validity of interior rings
0141             debug_phase::apply(2);
0142
0143             return has_valid_interior_rings(geometry::interior_rings(polygon),
0144                                             visitor,
0145                                             strategy);
0146         }
0147     };
0148
0149
0150     // Iterator value_type is a Ring or Polygon
0151     template <typename Iterator, typename Box>
0152     struct partition_item
0153     {
0154         explicit partition_item(Iterator it)
0155             : m_it(it)
0156             , m_is_initialized(false)
0157         {}
0158
0159         Iterator get() const
0160         {
0161             return m_it;
0162         }
0163
0164         template <typename EnvelopeStrategy>
0165         Box const& get_envelope(EnvelopeStrategy const& strategy) const
0166         {
0167             if (! m_is_initialized)
0168             {
0169                 m_box = geometry::return_envelope<Box>(*m_it, strategy);
0170                 m_is_initialized = true;
0171             }
0172             return m_box;
0173         }
0174
0175     private:
0176         Iterator m_it;
0177         mutable Box m_box;
0178         mutable bool m_is_initialized;
0179     };
0180
0181     // structs for partition -- start
0182     template <typename Strategy>
0183     struct expand_box
0184     {
0185         explicit expand_box(Strategy const& strategy)
0186             : m_strategy(strategy)
0187         {}
0188
0189         template <typename Box, typename Iterator>
0190         inline void apply(Box& total, partition_item<Iterator, Box> const& item) const
0191         {
0192             geometry::expand(total,
0193                              item.get_envelope(m_strategy),
0194                              m_strategy);
0195         }
0196
0197         Strategy const& m_strategy;
0198     };
0199
0200     template <typename Strategy>
0201     struct overlaps_box
0202     {
0203         explicit overlaps_box(Strategy const& strategy)
0204             : m_strategy(strategy)
0205         {}
0206
0207         template <typename Box, typename Iterator>
0208         inline bool apply(Box const& box, partition_item<Iterator, Box> const& item) const
0209         {
0210             return ! geometry::disjoint(item.get_envelope(m_strategy),
0211                                         box,
0212                                         m_strategy);
0213         }
0214
0215         Strategy const& m_strategy;
0216     };
0217
0218
0219     template <typename Strategy>
0220     struct item_visitor_type
0221     {
0222         bool items_overlap;
0223         Strategy const& m_strategy;
0224
0225         explicit item_visitor_type(Strategy const& strategy)
0226             : items_overlap(false)
0227             , m_strategy(strategy)
0228         {}
0229
0230         template <typename Iterator, typename Box>
0231         inline bool apply(partition_item<Iterator, Box> const& item1,
0232                           partition_item<Iterator, Box> const& item2)
0233         {
0234             typedef util::type_sequence
0235                 <
0236                     geometry::de9im::static_mask<'T'>,
0237                     geometry::de9im::static_mask<'*', 'T'>,
0238                     geometry::de9im::static_mask<'*', '*', '*', 'T'>
0239                 > relate_mask_t;
0240
0241             if ( ! items_overlap
0242               && geometry::relate(*item1.get(), *item2.get(), relate_mask_t(), m_strategy) )
0243             {
0244                 items_overlap = true;
0245                 return false; // interrupt
0246             }
0247             return true;
0248         }
0249     };
0250     // structs for partition -- end
0251
0252
0253     template
0254     <
0255         typename RingIterator,
0256         typename ExteriorRing,
0257         typename TurnIterator,
0258         typename VisitPolicy,
0259         typename Strategy
0260     >
0261     static inline bool are_holes_inside(RingIterator rings_first,
0262                                         RingIterator rings_beyond,
0263                                         ExteriorRing const& exterior_ring,
0264                                         TurnIterator turns_first,
0265                                         TurnIterator turns_beyond,
0266                                         VisitPolicy& visitor,
0267                                         Strategy const& strategy)
0268     {
0269         boost::ignore_unused(visitor);
0270
0271         // collect the interior ring indices that have turns with the
0272         // exterior ring
0273         std::set<signed_size_type> ring_indices;
0274         for (TurnIterator tit = turns_first; tit != turns_beyond; ++tit)
0275         {
0276             if (tit->operations[0].seg_id.ring_index == -1)
0277             {
0278                 BOOST_GEOMETRY_ASSERT(tit->operations[1].seg_id.ring_index != -1);
0279                 ring_indices.insert(tit->operations[1].seg_id.ring_index);
0280             }
0281             else if (tit->operations[1].seg_id.ring_index == -1)
0282             {
0283                 BOOST_GEOMETRY_ASSERT(tit->operations[0].seg_id.ring_index != -1);
0284                 ring_indices.insert(tit->operations[0].seg_id.ring_index);
0285             }
0286         }
0287
0288         signed_size_type ring_index = 0;
0289         for (RingIterator it = rings_first; it != rings_beyond;
0290              ++it, ++ring_index)
0291         {
0292             // do not examine interior rings that have turns with the
0293             // exterior ring
0294             if (ring_indices.find(ring_index) == ring_indices.end()
0295                 && ! geometry::covered_by(range::front(*it), exterior_ring, strategy))
0296             {
0297                 return visitor.template apply<failure_interior_rings_outside>();
0298             }
0299         }
0300
0301         // collect all rings (exterior and/or interior) that have turns
0302         for (TurnIterator tit = turns_first; tit != turns_beyond; ++tit)
0303         {
0304             ring_indices.insert(tit->operations[0].seg_id.ring_index);
0305             ring_indices.insert(tit->operations[1].seg_id.ring_index);
0306         }
0307
0308         typedef geometry::model::box<typename point_type<Polygon>::type> box_type;
0309         typedef partition_item<RingIterator, box_type> item_type;
0310
0311         // put iterators for interior rings without turns in a vector
0312         std::vector<item_type> ring_iterators;
0313         ring_index = 0;
0314         for (RingIterator it = rings_first; it != rings_beyond;
0315              ++it, ++ring_index)
0316         {
0317             if (ring_indices.find(ring_index) == ring_indices.end())
0318             {
0319                 ring_iterators.push_back(item_type(it));
0320             }
0321         }
0322
0323         // call partition to check if interior rings are disjoint from
0324         // each other
0325         item_visitor_type<Strategy> item_visitor(strategy);
0326
0327         geometry::partition
0328             <
0329                 box_type
0330             >::apply(ring_iterators, item_visitor,
0331                      expand_box<Strategy>(strategy),
0332                      overlaps_box<Strategy>(strategy));
0333
0334         if (item_visitor.items_overlap)
0335         {
0336             return visitor.template apply<failure_nested_interior_rings>();
0337         }
0338         else
0339         {
0340             return visitor.template apply<no_failure>();
0341         }
0342     }
0343
0344     template
0345     <
0346         typename InteriorRings,
0347         typename ExteriorRing,
0348         typename TurnIterator,
0349         typename VisitPolicy,
0350         typename Strategy
0351     >
0352     static inline bool are_holes_inside(InteriorRings const& interior_rings,
0353                                         ExteriorRing const& exterior_ring,
0354                                         TurnIterator first,
0355                                         TurnIterator beyond,
0356                                         VisitPolicy& visitor,
0357                                         Strategy const& strategy)
0358     {
0359         return are_holes_inside(boost::begin(interior_rings),
0360                                 boost::end(interior_rings),
0361                                 exterior_ring,
0362                                 first,
0363                                 beyond,
0364                                 visitor,
0365                                 strategy);
0366     }
0367
0368     struct has_holes_inside
0369     {
0370         template <typename TurnIterator, typename VisitPolicy, typename Strategy>
0371         static inline bool apply(Polygon const& polygon,
0372                                  TurnIterator first,
0373                                  TurnIterator beyond,
0374                                  VisitPolicy& visitor,
0375                                  Strategy const& strategy)
0376         {
0377             return are_holes_inside(geometry::interior_rings(polygon),
0378                                     geometry::exterior_ring(polygon),
0379                                     first,
0380                                     beyond,
0381                                     visitor,
0382                                     strategy);
0383         }
0384     };
0385
0386
0387
0388
0389     struct has_connected_interior
0390     {
0391         template <typename TurnIterator, typename VisitPolicy, typename Strategy>
0392         static inline bool apply(Polygon const& polygon,
0393                                  TurnIterator first,
0394                                  TurnIterator beyond,
0395                                  VisitPolicy& visitor,
0396                                  Strategy const& )
0397         {
0398             boost::ignore_unused(visitor);
0399
0400             typedef typename std::iterator_traits
0401                 <
0402                     TurnIterator
0403                 >::value_type turn_type;
0404             typedef complement_graph
0405                 <
0406                     typename turn_type::point_type,
0407                     Strategy
0408                 > graph;
0409
0410             graph g(geometry::num_interior_rings(polygon) + 1);
0411             for (TurnIterator tit = first; tit != beyond; ++tit)
0412             {
0413                 typename graph::vertex_handle v1 = g.add_vertex
0414                     ( tit->operations[0].seg_id.ring_index + 1 );
0415                 typename graph::vertex_handle v2 = g.add_vertex
0416                     ( tit->operations[1].seg_id.ring_index + 1 );
0417                 typename graph::vertex_handle vip = g.add_vertex(tit->point);
0418
0419                 g.add_edge(v1, vip);
0420                 g.add_edge(v2, vip);
0421             }
0422
0423 #ifdef BOOST_GEOMETRY_TEST_DEBUG
0424             debug_print_complement_graph(std::cout, g);
0425 #endif // BOOST_GEOMETRY_TEST_DEBUG
0426
0427             if (g.has_cycles())
0428             {
0429                 return visitor.template apply<failure_disconnected_interior>();
0430             }
0431             else
0432             {
0433                 return visitor.template apply<no_failure>();
0434             }
0435         }
0436     };
0437
0438 public:
0439     template <typename VisitPolicy, typename Strategy>
0440     static inline bool apply(Polygon const& polygon,
0441                              VisitPolicy& visitor,
0442                              Strategy const& strategy)
0443     {
0444         if (! has_valid_rings::apply(polygon, visitor, strategy))
0445         {
0446             return false;
0447         }
0448
0449         if BOOST_GEOMETRY_CONSTEXPR (CheckRingValidityOnly)
0450         {
0451             return true;
0452         }
0453
0454         // compute turns and check if all are acceptable
0455         typedef debug_validity_phase<Polygon> debug_phase;
0456         debug_phase::apply(3);
0457
0458         typedef has_valid_self_turns<Polygon, typename Strategy::cs_tag> has_valid_turns;
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 }} // namespace detail::is_valid
0494 #endif // DOXYGEN_NO_DETAIL
0495
0496
0497
0498 #ifndef DOXYGEN_NO_DISPATCH
0499 namespace dispatch
0500 {
0501
0502
0503 // A Polygon is always a simple geometric object provided that it is valid.
0504 //
0505 // Reference (for validity of Polygons): OGC 06-103r4 (6.1.11.1)
0506 template <typename Polygon, bool AllowEmptyMultiGeometries>
0507 struct is_valid
0508     <
0509         Polygon, polygon_tag, AllowEmptyMultiGeometries
0510     > : detail::is_valid::is_valid_polygon<Polygon>
0511 {};
0512
0513
0514 } // namespace dispatch
0515 #endif // DOXYGEN_NO_DISPATCH
0516
0517
0518 }} // namespace boost::geometry
0519
0520 #endif // BOOST_GEOMETRY_ALGORITHMS_DETAIL_IS_VALID_POLYGON_HPP