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