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