1 // Boost.Geometry (aka GGL, Generic Geometry Library)
2 
3 // Copyright (c) 2017 Adam Wulkiewicz, Lodz, Poland.
4 
5 // Copyright (c) 2014-2019, 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 
80     template <typename VisitPolicy, typename Strategy>
81     struct per_ring
82     {
per_ringboost::geometry::detail::is_valid::is_valid_polygon::per_ring83         per_ring(VisitPolicy& policy, Strategy const& strategy)
84             : m_policy(policy)
85             , m_strategy(strategy)
86         {}
87 
88         template <typename Ring>
applyboost::geometry::detail::is_valid::is_valid_polygon::per_ring89         inline bool apply(Ring const& ring) const
90         {
91             return detail::is_valid::is_valid_ring
92                 <
93                     Ring, false, true
94                 >::apply(ring, m_policy, m_strategy);
95         }
96 
97         VisitPolicy& m_policy;
98         Strategy const& m_strategy;
99     };
100 
101     template <typename InteriorRings, typename VisitPolicy, typename Strategy>
has_valid_interior_rings(InteriorRings const & interior_rings,VisitPolicy & visitor,Strategy const & strategy)102     static bool has_valid_interior_rings(InteriorRings const& interior_rings,
103                                          VisitPolicy& visitor,
104                                          Strategy const& strategy)
105     {
106         return
107             detail::check_iterator_range
108                 <
109                     per_ring<VisitPolicy, Strategy>,
110                     true // allow for empty interior ring range
111                 >::apply(boost::begin(interior_rings),
112                          boost::end(interior_rings),
113                          per_ring<VisitPolicy, Strategy>(visitor, strategy));
114     }
115 
116     struct has_valid_rings
117     {
118         template <typename VisitPolicy, typename Strategy>
applyboost::geometry::detail::is_valid::is_valid_polygon::has_valid_rings119         static inline bool apply(Polygon const& polygon,
120                                  VisitPolicy& visitor,
121                                  Strategy const& strategy)
122         {
123             typedef debug_validity_phase<Polygon> debug_phase;
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     {
partition_itemboost::geometry::detail::is_valid::is_valid_polygon::partition_item152         explicit partition_item(Iterator it)
153             : m_it(it)
154             , m_is_initialized(false)
155         {}
156 
getboost::geometry::detail::is_valid::is_valid_polygon::partition_item157         Iterator get() const
158         {
159             return m_it;
160         }
161 
162         template <typename EnvelopeStrategy>
get_envelopeboost::geometry::detail::is_valid::is_valid_polygon::partition_item163         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     {
expand_boxboost::geometry::detail::is_valid::is_valid_polygon::expand_box183         explicit expand_box(EnvelopeStrategy const& strategy)
184             : m_strategy(strategy)
185         {}
186 
187         template <typename Box, typename Iterator>
applyboost::geometry::detail::is_valid::is_valid_polygon::expand_box188         inline void apply(Box& total, partition_item<Iterator, Box> const& item) const
189         {
190             geometry::expand(total,
191                              item.get_envelope(m_strategy),
192                              m_strategy.get_box_expand_strategy());
193         }
194 
195         EnvelopeStrategy const& m_strategy;
196     };
197 
198     template <typename EnvelopeStrategy, typename DisjointBoxBoxStrategy>
199     struct overlaps_box
200     {
overlaps_boxboost::geometry::detail::is_valid::is_valid_polygon::overlaps_box201         explicit overlaps_box(EnvelopeStrategy const& envelope_strategy,
202                               DisjointBoxBoxStrategy const& disjoint_strategy)
203             : m_envelope_strategy(envelope_strategy)
204             , m_disjoint_strategy(disjoint_strategy)
205         {}
206 
207         template <typename Box, typename Iterator>
applyboost::geometry::detail::is_valid::is_valid_polygon::overlaps_box208         inline bool apply(Box const& box, partition_item<Iterator, Box> const& item) const
209         {
210             return ! geometry::disjoint(item.get_envelope(m_envelope_strategy),
211                                         box,
212                                         m_disjoint_strategy);
213         }
214 
215         EnvelopeStrategy const& m_envelope_strategy;
216         DisjointBoxBoxStrategy const& m_disjoint_strategy;
217     };
218 
219 
220     template <typename WithinStrategy>
221     struct item_visitor_type
222     {
223         bool items_overlap;
224         WithinStrategy const& m_strategy;
225 
item_visitor_typeboost::geometry::detail::is_valid::is_valid_polygon::item_visitor_type226         explicit item_visitor_type(WithinStrategy const& strategy)
227             : items_overlap(false)
228             , m_strategy(strategy)
229         {}
230 
231         template <typename Iterator, typename Box>
applyboost::geometry::detail::is_valid::is_valid_polygon::item_visitor_type232         inline bool apply(partition_item<Iterator, Box> const& item1,
233                           partition_item<Iterator, Box> const& item2)
234         {
235             typedef boost::mpl::vector
236                 <
237                     geometry::de9im::static_mask<'T'>,
238                     geometry::de9im::static_mask<'*', 'T'>,
239                     geometry::de9im::static_mask<'*', '*', '*', 'T'>
240                 > relate_mask_t;
241 
242             if ( ! items_overlap
243               && geometry::relate(*item1.get(), *item2.get(), relate_mask_t(), m_strategy) )
244             {
245                 items_overlap = true;
246                 return false; // interrupt
247             }
248             return true;
249         }
250     };
251     // structs for partition -- end
252 
253 
254     template
255     <
256         typename RingIterator,
257         typename ExteriorRing,
258         typename TurnIterator,
259         typename VisitPolicy,
260         typename Strategy
261     >
are_holes_inside(RingIterator rings_first,RingIterator rings_beyond,ExteriorRing const & exterior_ring,TurnIterator turns_first,TurnIterator turns_beyond,VisitPolicy & visitor,Strategy const & strategy)262     static inline bool are_holes_inside(RingIterator rings_first,
263                                         RingIterator rings_beyond,
264                                         ExteriorRing const& exterior_ring,
265                                         TurnIterator turns_first,
266                                         TurnIterator turns_beyond,
267                                         VisitPolicy& visitor,
268                                         Strategy const& strategy)
269     {
270         boost::ignore_unused(visitor);
271 
272         // collect the interior ring indices that have turns with the
273         // exterior ring
274         std::set<signed_size_type> ring_indices;
275         for (TurnIterator tit = turns_first; tit != turns_beyond; ++tit)
276         {
277             if (tit->operations[0].seg_id.ring_index == -1)
278             {
279                 BOOST_GEOMETRY_ASSERT(tit->operations[1].seg_id.ring_index != -1);
280                 ring_indices.insert(tit->operations[1].seg_id.ring_index);
281             }
282             else if (tit->operations[1].seg_id.ring_index == -1)
283             {
284                 BOOST_GEOMETRY_ASSERT(tit->operations[0].seg_id.ring_index != -1);
285                 ring_indices.insert(tit->operations[0].seg_id.ring_index);
286             }
287         }
288 
289         // prepare strategy
290         typedef typename std::iterator_traits<RingIterator>::value_type inter_ring_type;
291         typename Strategy::template point_in_geometry_strategy
292             <
293                 inter_ring_type, ExteriorRing
294             >::type const in_exterior_strategy
295             = strategy.template get_point_in_geometry_strategy<inter_ring_type, ExteriorRing>();
296 
297         signed_size_type ring_index = 0;
298         for (RingIterator it = rings_first; it != rings_beyond;
299              ++it, ++ring_index)
300         {
301             // do not examine interior rings that have turns with the
302             // exterior ring
303             if (ring_indices.find(ring_index) == ring_indices.end()
304                 && ! geometry::covered_by(range::front(*it), exterior_ring, in_exterior_strategy))
305             {
306                 return visitor.template apply<failure_interior_rings_outside>();
307             }
308         }
309 
310         // collect all rings (exterior and/or interior) that have turns
311         for (TurnIterator tit = turns_first; tit != turns_beyond; ++tit)
312         {
313             ring_indices.insert(tit->operations[0].seg_id.ring_index);
314             ring_indices.insert(tit->operations[1].seg_id.ring_index);
315         }
316 
317         typedef geometry::model::box<typename point_type<Polygon>::type> box_type;
318         typedef partition_item<RingIterator, box_type> item_type;
319 
320         // put iterators for interior rings without turns in a vector
321         std::vector<item_type> ring_iterators;
322         ring_index = 0;
323         for (RingIterator it = rings_first; it != rings_beyond;
324              ++it, ++ring_index)
325         {
326             if (ring_indices.find(ring_index) == ring_indices.end())
327             {
328                 ring_iterators.push_back(item_type(it));
329             }
330         }
331 
332         // prepare strategies
333         typedef typename Strategy::envelope_strategy_type envelope_strategy_type;
334         envelope_strategy_type const envelope_strategy
335             = strategy.get_envelope_strategy();
336         typedef typename Strategy::disjoint_box_box_strategy_type disjoint_box_box_strategy_type;
337         disjoint_box_box_strategy_type const disjoint_strategy
338             = strategy.get_disjoint_box_box_strategy();
339 
340         // call partition to check if interior rings are disjoint from
341         // each other
342         item_visitor_type<Strategy> item_visitor(strategy);
343 
344         geometry::partition
345             <
346                 box_type
347             >::apply(ring_iterators, item_visitor,
348                      expand_box
349                         <
350                             envelope_strategy_type
351                         >(envelope_strategy),
352                      overlaps_box
353                         <
354                             envelope_strategy_type,
355                             disjoint_box_box_strategy_type
356                         >(envelope_strategy, disjoint_strategy));
357 
358         if (item_visitor.items_overlap)
359         {
360             return visitor.template apply<failure_nested_interior_rings>();
361         }
362         else
363         {
364             return visitor.template apply<no_failure>();
365         }
366     }
367 
368     template
369     <
370         typename InteriorRings,
371         typename ExteriorRing,
372         typename TurnIterator,
373         typename VisitPolicy,
374         typename Strategy
375     >
are_holes_inside(InteriorRings const & interior_rings,ExteriorRing const & exterior_ring,TurnIterator first,TurnIterator beyond,VisitPolicy & visitor,Strategy const & strategy)376     static inline bool are_holes_inside(InteriorRings const& interior_rings,
377                                         ExteriorRing const& exterior_ring,
378                                         TurnIterator first,
379                                         TurnIterator beyond,
380                                         VisitPolicy& visitor,
381                                         Strategy const& strategy)
382     {
383         return are_holes_inside(boost::begin(interior_rings),
384                                 boost::end(interior_rings),
385                                 exterior_ring,
386                                 first,
387                                 beyond,
388                                 visitor,
389                                 strategy);
390     }
391 
392     struct has_holes_inside
393     {
394         template <typename TurnIterator, typename VisitPolicy, typename Strategy>
applyboost::geometry::detail::is_valid::is_valid_polygon::has_holes_inside395         static inline bool apply(Polygon const& polygon,
396                                  TurnIterator first,
397                                  TurnIterator beyond,
398                                  VisitPolicy& visitor,
399                                  Strategy const& strategy)
400         {
401             return are_holes_inside(geometry::interior_rings(polygon),
402                                     geometry::exterior_ring(polygon),
403                                     first,
404                                     beyond,
405                                     visitor,
406                                     strategy);
407         }
408     };
409 
410 
411 
412 
413     struct has_connected_interior
414     {
415         template <typename TurnIterator, typename VisitPolicy, typename Strategy>
applyboost::geometry::detail::is_valid::is_valid_polygon::has_connected_interior416         static inline bool apply(Polygon const& polygon,
417                                  TurnIterator first,
418                                  TurnIterator beyond,
419                                  VisitPolicy& visitor,
420                                  Strategy const& )
421         {
422             boost::ignore_unused(visitor);
423 
424             typedef typename std::iterator_traits
425                 <
426                     TurnIterator
427                 >::value_type turn_type;
428             typedef complement_graph
429                 <
430                     typename turn_type::point_type,
431                     typename Strategy::cs_tag
432                 > graph;
433 
434             graph g(geometry::num_interior_rings(polygon) + 1);
435             for (TurnIterator tit = first; tit != beyond; ++tit)
436             {
437                 typename graph::vertex_handle v1 = g.add_vertex
438                     ( tit->operations[0].seg_id.ring_index + 1 );
439                 typename graph::vertex_handle v2 = g.add_vertex
440                     ( tit->operations[1].seg_id.ring_index + 1 );
441                 typename graph::vertex_handle vip = g.add_vertex(tit->point);
442 
443                 g.add_edge(v1, vip);
444                 g.add_edge(v2, vip);
445             }
446 
447 #ifdef BOOST_GEOMETRY_TEST_DEBUG
448             debug_print_complement_graph(std::cout, g);
449 #endif // BOOST_GEOMETRY_TEST_DEBUG
450 
451             if (g.has_cycles())
452             {
453                 return visitor.template apply<failure_disconnected_interior>();
454             }
455             else
456             {
457                 return visitor.template apply<no_failure>();
458             }
459         }
460     };
461 
462 public:
463     template <typename VisitPolicy, typename Strategy>
apply(Polygon const & polygon,VisitPolicy & visitor,Strategy const & strategy)464     static inline bool apply(Polygon const& polygon,
465                              VisitPolicy& visitor,
466                              Strategy const& strategy)
467     {
468         if (! has_valid_rings::apply(polygon, visitor, strategy))
469         {
470             return false;
471         }
472 
473         if (BOOST_GEOMETRY_CONDITION(CheckRingValidityOnly))
474         {
475             return true;
476         }
477 
478         // compute turns and check if all are acceptable
479         typedef debug_validity_phase<Polygon> debug_phase;
480         debug_phase::apply(3);
481 
482         typedef has_valid_self_turns<Polygon, typename Strategy::cs_tag> has_valid_turns;
483 
484         std::deque<typename has_valid_turns::turn_type> turns;
485         bool has_invalid_turns
486             = ! has_valid_turns::apply(polygon, turns, visitor, strategy);
487         debug_print_turns(turns.begin(), turns.end());
488 
489         if (has_invalid_turns)
490         {
491             return false;
492         }
493 
494         // check if all interior rings are inside the exterior ring
495         debug_phase::apply(4);
496 
497         if (! has_holes_inside::apply(polygon,
498                                       turns.begin(), turns.end(),
499                                       visitor,
500                                       strategy))
501         {
502             return false;
503         }
504 
505         // check whether the interior of the polygon is a connected set
506         debug_phase::apply(5);
507 
508         return has_connected_interior::apply(polygon,
509                                              turns.begin(),
510                                              turns.end(),
511                                              visitor,
512                                              strategy);
513     }
514 };
515 
516 
517 }} // namespace detail::is_valid
518 #endif // DOXYGEN_NO_DETAIL
519 
520 
521 
522 #ifndef DOXYGEN_NO_DISPATCH
523 namespace dispatch
524 {
525 
526 
527 // A Polygon is always a simple geometric object provided that it is valid.
528 //
529 // Reference (for validity of Polygons): OGC 06-103r4 (6.1.11.1)
530 template <typename Polygon, bool AllowEmptyMultiGeometries>
531 struct is_valid
532     <
533         Polygon, polygon_tag, AllowEmptyMultiGeometries
534     > : detail::is_valid::is_valid_polygon<Polygon>
535 {};
536 
537 
538 } // namespace dispatch
539 #endif // DOXYGEN_NO_DISPATCH
540 
541 
542 }} // namespace boost::geometry
543 
544 #endif // BOOST_GEOMETRY_ALGORITHMS_DETAIL_IS_VALID_POLYGON_HPP
545