1 // Boost.Geometry (aka GGL, Generic Geometry Library)
2 
3 // Copyright (c) 2014, 2021, Oracle and/or its affiliates.
4 
5 // Contributed and/or modified by Menelaos Karavelas, on behalf of Oracle
6 
7 // Licensed under the Boost Software License version 1.0.
8 // http://www.boost.org/users/license.html
9 
10 #ifndef BOOST_GEOMETRY_ALGORITHMS_DETAIL_IS_VALID_POLYGON_HPP
11 #define BOOST_GEOMETRY_ALGORITHMS_DETAIL_IS_VALID_POLYGON_HPP
12 
13 #include <cstddef>
14 #ifdef BOOST_GEOMETRY_TEST_DEBUG
15 #include <iostream>
16 #endif // BOOST_GEOMETRY_TEST_DEBUG
17 
18 #include <algorithm>
19 #include <deque>
20 #include <iterator>
21 #include <set>
22 #include <vector>
23 
24 #include <boost/core/ignore_unused.hpp>
25 #include <boost/range.hpp>
26 
27 #include <boost/geometry/core/assert.hpp>
28 #include <boost/geometry/core/exterior_ring.hpp>
29 #include <boost/geometry/core/interior_rings.hpp>
30 #include <boost/geometry/core/ring_type.hpp>
31 #include <boost/geometry/core/tags.hpp>
32 
33 #include <boost/geometry/util/condition.hpp>
34 #include <boost/geometry/util/range.hpp>
35 
36 #include <boost/geometry/geometries/box.hpp>
37 
38 #include <boost/geometry/iterators/point_iterator.hpp>
39 
40 #include <boost/geometry/algorithms/covered_by.hpp>
41 #include <boost/geometry/algorithms/disjoint.hpp>
42 #include <boost/geometry/algorithms/expand.hpp>
43 #include <boost/geometry/algorithms/num_interior_rings.hpp>
44 #include <boost/geometry/algorithms/validity_failure_type.hpp>
45 #include <boost/geometry/algorithms/within.hpp>
46 
47 #include <boost/geometry/algorithms/detail/check_iterator_range.hpp>
48 #include <boost/geometry/algorithms/detail/partition.hpp>
49 
50 #include <boost/geometry/algorithms/detail/is_valid/complement_graph.hpp>
51 #include <boost/geometry/algorithms/detail/is_valid/has_valid_self_turns.hpp>
52 #include <boost/geometry/algorithms/detail/is_valid/is_acceptable_turn.hpp>
53 #include <boost/geometry/algorithms/detail/is_valid/ring.hpp>
54 
55 #include <boost/geometry/algorithms/detail/is_valid/debug_print_turns.hpp>
56 #include <boost/geometry/algorithms/detail/is_valid/debug_validity_phase.hpp>
57 #include <boost/geometry/algorithms/detail/is_valid/debug_complement_graph.hpp>
58 
59 #include <boost/geometry/algorithms/dispatch/is_valid.hpp>
60 
61 
62 namespace boost { namespace geometry
63 {
64 
65 
66 #ifndef DOXYGEN_NO_DETAIL
67 namespace detail { namespace is_valid
68 {
69 
70 
71 template <typename Polygon, bool CheckRingValidityOnly = false>
72 class is_valid_polygon
73 {
74 protected:
75     typedef debug_validity_phase<Polygon> debug_phase;
76 
77     template <typename VisitPolicy>
78     struct per_ring
79     {
per_ringboost::geometry::detail::is_valid::is_valid_polygon::per_ring80         per_ring(VisitPolicy& policy) : m_policy(policy) {}
81 
82         template <typename Ring>
applyboost::geometry::detail::is_valid::is_valid_polygon::per_ring83         inline bool apply(Ring const& ring) const
84         {
85             return detail::is_valid::is_valid_ring
86                 <
87                     Ring, false, true
88                 >::apply(ring, m_policy);
89         }
90 
91         VisitPolicy& m_policy;
92     };
93 
94     template <typename InteriorRings, typename VisitPolicy>
has_valid_interior_rings(InteriorRings const & interior_rings,VisitPolicy & visitor)95     static bool has_valid_interior_rings(InteriorRings const& interior_rings,
96                                          VisitPolicy& visitor)
97     {
98         return
99             detail::check_iterator_range
100                 <
101                     per_ring<VisitPolicy>,
102                     true // allow for empty interior ring range
103                 >::apply(boost::begin(interior_rings),
104                          boost::end(interior_rings),
105                          per_ring<VisitPolicy>(visitor));
106     }
107 
108     struct has_valid_rings
109     {
110         template <typename VisitPolicy>
applyboost::geometry::detail::is_valid::is_valid_polygon::has_valid_rings111         static inline bool apply(Polygon const& polygon, VisitPolicy& visitor)
112         {
113             typedef typename ring_type<Polygon>::type ring_type;
114 
115             // check validity of exterior ring
116             debug_phase::apply(1);
117 
118             if (! detail::is_valid::is_valid_ring
119                      <
120                          ring_type,
121                          false // do not check self intersections
122                      >::apply(exterior_ring(polygon), visitor))
123             {
124                 return false;
125             }
126 
127             // check validity of interior rings
128             debug_phase::apply(2);
129 
130             return has_valid_interior_rings(geometry::interior_rings(polygon),
131                                             visitor);
132         }
133     };
134 
135 
136     // structs for partition -- start
137     struct expand_box
138     {
139         template <typename Box, typename Iterator>
applyboost::geometry::detail::is_valid::is_valid_polygon::expand_box140         static inline void apply(Box& total, Iterator const& it)
141         {
142             geometry::expand(total, geometry::return_envelope<Box>(*it));
143         }
144 
145     };
146 
147     struct overlaps_box
148     {
149         template <typename Box, typename Iterator>
applyboost::geometry::detail::is_valid::is_valid_polygon::overlaps_box150         static inline bool apply(Box const& box, Iterator const& it)
151         {
152             return ! geometry::disjoint(*it, box);
153         }
154     };
155 
156 
157     struct item_visitor_type
158     {
159         bool items_overlap;
160 
item_visitor_typeboost::geometry::detail::is_valid::is_valid_polygon::item_visitor_type161         item_visitor_type() : items_overlap(false) {}
162 
163         template <typename Item1, typename Item2>
applyboost::geometry::detail::is_valid::is_valid_polygon::item_visitor_type164         inline void apply(Item1 const& item1, Item2 const& item2)
165         {
166             if (! items_overlap
167                 && (geometry::within(*points_begin(*item1), *item2)
168                     || geometry::within(*points_begin(*item2), *item1))
169                 )
170             {
171                 items_overlap = true;
172             }
173         }
174     };
175     // structs for partition -- end
176 
177 
178     template
179     <
180         typename RingIterator,
181         typename ExteriorRing,
182         typename TurnIterator,
183         typename VisitPolicy
184     >
are_holes_inside(RingIterator rings_first,RingIterator rings_beyond,ExteriorRing const & exterior_ring,TurnIterator turns_first,TurnIterator turns_beyond,VisitPolicy & visitor)185     static inline bool are_holes_inside(RingIterator rings_first,
186                                         RingIterator rings_beyond,
187                                         ExteriorRing const& exterior_ring,
188                                         TurnIterator turns_first,
189                                         TurnIterator turns_beyond,
190                                         VisitPolicy& visitor)
191     {
192         boost::ignore_unused(visitor);
193 
194         // collect the interior ring indices that have turns with the
195         // exterior ring
196         std::set<signed_size_type> ring_indices;
197         for (TurnIterator tit = turns_first; tit != turns_beyond; ++tit)
198         {
199             if (tit->operations[0].seg_id.ring_index == -1)
200             {
201                 BOOST_GEOMETRY_ASSERT(tit->operations[1].seg_id.ring_index != -1);
202                 ring_indices.insert(tit->operations[1].seg_id.ring_index);
203             }
204             else if (tit->operations[1].seg_id.ring_index == -1)
205             {
206                 BOOST_GEOMETRY_ASSERT(tit->operations[0].seg_id.ring_index != -1);
207                 ring_indices.insert(tit->operations[0].seg_id.ring_index);
208             }
209         }
210 
211         signed_size_type ring_index = 0;
212         for (RingIterator it = rings_first; it != rings_beyond;
213              ++it, ++ring_index)
214         {
215             // do not examine interior rings that have turns with the
216             // exterior ring
217             if (ring_indices.find(ring_index) == ring_indices.end()
218                 && ! geometry::covered_by(range::front(*it), exterior_ring))
219             {
220                 return visitor.template apply<failure_interior_rings_outside>();
221             }
222         }
223 
224         // collect all rings (exterior and/or interior) that have turns
225         for (TurnIterator tit = turns_first; tit != turns_beyond; ++tit)
226         {
227             ring_indices.insert(tit->operations[0].seg_id.ring_index);
228             ring_indices.insert(tit->operations[1].seg_id.ring_index);
229         }
230 
231         // put iterators for interior rings without turns in a vector
232         std::vector<RingIterator> ring_iterators;
233         ring_index = 0;
234         for (RingIterator it = rings_first; it != rings_beyond;
235              ++it, ++ring_index)
236         {
237             if (ring_indices.find(ring_index) == ring_indices.end())
238             {
239                 ring_iterators.push_back(it);
240             }
241         }
242 
243         // call partition to check is interior rings are disjoint from
244         // each other
245         item_visitor_type item_visitor;
246 
247         geometry::partition
248             <
249                 geometry::model::box<typename point_type<Polygon>::type>,
250                 expand_box,
251                 overlaps_box
252             >::apply(ring_iterators, item_visitor);
253 
254         if (item_visitor.items_overlap)
255         {
256             return visitor.template apply<failure_nested_interior_rings>();
257         }
258         else
259         {
260             return visitor.template apply<no_failure>();
261         }
262     }
263 
264     template
265     <
266         typename InteriorRings,
267         typename ExteriorRing,
268         typename TurnIterator,
269         typename VisitPolicy
270     >
are_holes_inside(InteriorRings const & interior_rings,ExteriorRing const & exterior_ring,TurnIterator first,TurnIterator beyond,VisitPolicy & visitor)271     static inline bool are_holes_inside(InteriorRings const& interior_rings,
272                                         ExteriorRing const& exterior_ring,
273                                         TurnIterator first,
274                                         TurnIterator beyond,
275                                         VisitPolicy& visitor)
276     {
277         return are_holes_inside(boost::begin(interior_rings),
278                                 boost::end(interior_rings),
279                                 exterior_ring,
280                                 first,
281                                 beyond,
282                                 visitor);
283     }
284 
285     struct has_holes_inside
286     {
287         template <typename TurnIterator, typename VisitPolicy>
applyboost::geometry::detail::is_valid::is_valid_polygon::has_holes_inside288         static inline bool apply(Polygon const& polygon,
289                                  TurnIterator first,
290                                  TurnIterator beyond,
291                                  VisitPolicy& visitor)
292         {
293             return are_holes_inside(geometry::interior_rings(polygon),
294                                     geometry::exterior_ring(polygon),
295                                     first,
296                                     beyond,
297                                     visitor);
298         }
299     };
300 
301 
302 
303 
304     struct has_connected_interior
305     {
306         template <typename TurnIterator, typename VisitPolicy>
applyboost::geometry::detail::is_valid::is_valid_polygon::has_connected_interior307         static inline bool apply(Polygon const& polygon,
308                                  TurnIterator first,
309                                  TurnIterator beyond,
310                                  VisitPolicy& visitor)
311         {
312             boost::ignore_unused(visitor);
313 
314             typedef typename std::iterator_traits
315                 <
316                     TurnIterator
317                 >::value_type turn_type;
318             typedef complement_graph<typename turn_type::point_type> graph;
319 
320             graph g(geometry::num_interior_rings(polygon) + 1);
321             for (TurnIterator tit = first; tit != beyond; ++tit)
322             {
323                 typename graph::vertex_handle v1 = g.add_vertex
324                     ( tit->operations[0].seg_id.ring_index + 1 );
325                 typename graph::vertex_handle v2 = g.add_vertex
326                     ( tit->operations[1].seg_id.ring_index + 1 );
327                 typename graph::vertex_handle vip = g.add_vertex(tit->point);
328 
329                 g.add_edge(v1, vip);
330                 g.add_edge(v2, vip);
331             }
332 
333 #ifdef BOOST_GEOMETRY_TEST_DEBUG
334             debug_print_complement_graph(std::cout, g);
335 #endif // BOOST_GEOMETRY_TEST_DEBUG
336 
337             if (g.has_cycles())
338             {
339                 return visitor.template apply<failure_disconnected_interior>();
340             }
341             else
342             {
343                 return visitor.template apply<no_failure>();
344             }
345         }
346     };
347 
348 public:
349     template <typename VisitPolicy>
apply(Polygon const & polygon,VisitPolicy & visitor)350     static inline bool apply(Polygon const& polygon, VisitPolicy& visitor)
351     {
352         if (! has_valid_rings::apply(polygon, visitor))
353         {
354             return false;
355         }
356 
357         if (BOOST_GEOMETRY_CONDITION(CheckRingValidityOnly))
358         {
359             return true;
360         }
361 
362         // compute turns and check if all are acceptable
363         debug_phase::apply(3);
364 
365         typedef has_valid_self_turns<Polygon> has_valid_turns;
366 
367         std::deque<typename has_valid_turns::turn_type> turns;
368         bool has_invalid_turns
369             = ! has_valid_turns::apply(polygon, turns, visitor);
370         debug_print_turns(turns.begin(), turns.end());
371 
372         if (has_invalid_turns)
373         {
374             return false;
375         }
376 
377         // check if all interior rings are inside the exterior ring
378         debug_phase::apply(4);
379 
380         if (! has_holes_inside::apply(polygon,
381                                       turns.begin(), turns.end(),
382                                       visitor))
383         {
384             return false;
385         }
386 
387         // check whether the interior of the polygon is a connected set
388         debug_phase::apply(5);
389 
390         return has_connected_interior::apply(polygon,
391                                              turns.begin(),
392                                              turns.end(),
393                                              visitor);
394     }
395 };
396 
397 
398 }} // namespace detail::is_valid
399 #endif // DOXYGEN_NO_DETAIL
400 
401 
402 
403 #ifndef DOXYGEN_NO_DISPATCH
404 namespace dispatch
405 {
406 
407 
408 // A Polygon is always a simple geometric object provided that it is valid.
409 //
410 // Reference (for validity of Polygons): OGC 06-103r4 (6.1.11.1)
411 template <typename Polygon, bool AllowEmptyMultiGeometries>
412 struct is_valid
413     <
414         Polygon, polygon_tag, AllowEmptyMultiGeometries
415     > : detail::is_valid::is_valid_polygon<Polygon>
416 {};
417 
418 
419 } // namespace dispatch
420 #endif // DOXYGEN_NO_DISPATCH
421 
422 
423 }} // namespace boost::geometry
424 
425 #endif // BOOST_GEOMETRY_ALGORITHMS_DETAIL_IS_VALID_POLYGON_HPP
426