1 // Boost.Geometry (aka GGL, Generic Geometry Library)
2 
3 // Copyright (c) 2017 Adam Wulkiewicz, Lodz, Poland.
4 
5 // Copyright (c) 2014-2017, 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 Item>
is_withinboost::geometry::detail::is_valid::is_valid_polygon::item_visitor_type221         inline bool is_within(Item const& first, Item const& second)
222         {
223             typename point_type<Polygon>::type point;
224             typedef detail::point_on_border::point_on_range<true> pob;
225 
226             // TODO: this should check for a point on the interior, instead
227             // of on border. Or it should check using the overlap function.
228 
229             return pob::apply(point, points_begin(first), points_end(first))
230                     && geometry::within(point, second, m_strategy);
231         }
232 
233         template <typename Iterator, typename Box>
applyboost::geometry::detail::is_valid::is_valid_polygon::item_visitor_type234         inline bool apply(partition_item<Iterator, Box> const& item1,
235                           partition_item<Iterator, Box> const& item2)
236         {
237             if (! items_overlap
238                 && (is_within(*item1.get(), *item2.get())
239                   || is_within(*item2.get(), *item1.get())))
240             {
241                 items_overlap = true;
242                 return false; // interrupt
243             }
244             return true;
245         }
246     };
247     // structs for partition -- end
248 
249 
250     template
251     <
252         typename RingIterator,
253         typename ExteriorRing,
254         typename TurnIterator,
255         typename VisitPolicy,
256         typename Strategy
257     >
are_holes_inside(RingIterator rings_first,RingIterator rings_beyond,ExteriorRing const & exterior_ring,TurnIterator turns_first,TurnIterator turns_beyond,VisitPolicy & visitor,Strategy const & strategy)258     static inline bool are_holes_inside(RingIterator rings_first,
259                                         RingIterator rings_beyond,
260                                         ExteriorRing const& exterior_ring,
261                                         TurnIterator turns_first,
262                                         TurnIterator turns_beyond,
263                                         VisitPolicy& visitor,
264                                         Strategy const& strategy)
265     {
266         boost::ignore_unused(visitor);
267 
268         // collect the interior ring indices that have turns with the
269         // exterior ring
270         std::set<signed_size_type> ring_indices;
271         for (TurnIterator tit = turns_first; tit != turns_beyond; ++tit)
272         {
273             if (tit->operations[0].seg_id.ring_index == -1)
274             {
275                 BOOST_GEOMETRY_ASSERT(tit->operations[1].seg_id.ring_index != -1);
276                 ring_indices.insert(tit->operations[1].seg_id.ring_index);
277             }
278             else if (tit->operations[1].seg_id.ring_index == -1)
279             {
280                 BOOST_GEOMETRY_ASSERT(tit->operations[0].seg_id.ring_index != -1);
281                 ring_indices.insert(tit->operations[0].seg_id.ring_index);
282             }
283         }
284 
285         // prepare strategy
286         typedef typename std::iterator_traits<RingIterator>::value_type inter_ring_type;
287         typename Strategy::template point_in_geometry_strategy
288             <
289                 inter_ring_type, ExteriorRing
290             >::type const in_exterior_strategy
291             = strategy.template get_point_in_geometry_strategy<inter_ring_type, ExteriorRing>();
292 
293         signed_size_type ring_index = 0;
294         for (RingIterator it = rings_first; it != rings_beyond;
295              ++it, ++ring_index)
296         {
297             // do not examine interior rings that have turns with the
298             // exterior ring
299             if (ring_indices.find(ring_index) == ring_indices.end()
300                 && ! geometry::covered_by(range::front(*it), exterior_ring, in_exterior_strategy))
301             {
302                 return visitor.template apply<failure_interior_rings_outside>();
303             }
304         }
305 
306         // collect all rings (exterior and/or interior) that have turns
307         for (TurnIterator tit = turns_first; tit != turns_beyond; ++tit)
308         {
309             ring_indices.insert(tit->operations[0].seg_id.ring_index);
310             ring_indices.insert(tit->operations[1].seg_id.ring_index);
311         }
312 
313         typedef geometry::model::box<typename point_type<Polygon>::type> box_type;
314         typedef partition_item<RingIterator, box_type> item_type;
315 
316         // put iterators for interior rings without turns in a vector
317         std::vector<item_type> ring_iterators;
318         ring_index = 0;
319         for (RingIterator it = rings_first; it != rings_beyond;
320              ++it, ++ring_index)
321         {
322             if (ring_indices.find(ring_index) == ring_indices.end())
323             {
324                 ring_iterators.push_back(item_type(it));
325             }
326         }
327 
328         // prepare strategies
329         typedef typename Strategy::template point_in_geometry_strategy
330             <
331                 inter_ring_type, inter_ring_type
332             >::type in_interior_strategy_type;
333         in_interior_strategy_type const in_interior_strategy
334             = strategy.template get_point_in_geometry_strategy<inter_ring_type, inter_ring_type>();
335         typedef typename Strategy::envelope_strategy_type envelope_strategy_type;
336         envelope_strategy_type const envelope_strategy
337             = strategy.get_envelope_strategy();
338 
339         // call partition to check if interior rings are disjoint from
340         // each other
341         item_visitor_type<in_interior_strategy_type> item_visitor(in_interior_strategy);
342 
343         geometry::partition
344             <
345                 box_type
346             >::apply(ring_iterators, item_visitor,
347                      expand_box<envelope_strategy_type>(envelope_strategy),
348                      overlaps_box<envelope_strategy_type>(envelope_strategy));
349 
350         if (item_visitor.items_overlap)
351         {
352             return visitor.template apply<failure_nested_interior_rings>();
353         }
354         else
355         {
356             return visitor.template apply<no_failure>();
357         }
358     }
359 
360     template
361     <
362         typename InteriorRings,
363         typename ExteriorRing,
364         typename TurnIterator,
365         typename VisitPolicy,
366         typename Strategy
367     >
are_holes_inside(InteriorRings const & interior_rings,ExteriorRing const & exterior_ring,TurnIterator first,TurnIterator beyond,VisitPolicy & visitor,Strategy const & strategy)368     static inline bool are_holes_inside(InteriorRings const& interior_rings,
369                                         ExteriorRing const& exterior_ring,
370                                         TurnIterator first,
371                                         TurnIterator beyond,
372                                         VisitPolicy& visitor,
373                                         Strategy const& strategy)
374     {
375         return are_holes_inside(boost::begin(interior_rings),
376                                 boost::end(interior_rings),
377                                 exterior_ring,
378                                 first,
379                                 beyond,
380                                 visitor,
381                                 strategy);
382     }
383 
384     struct has_holes_inside
385     {
386         template <typename TurnIterator, typename VisitPolicy, typename Strategy>
applyboost::geometry::detail::is_valid::is_valid_polygon::has_holes_inside387         static inline bool apply(Polygon const& polygon,
388                                  TurnIterator first,
389                                  TurnIterator beyond,
390                                  VisitPolicy& visitor,
391                                  Strategy const& strategy)
392         {
393             return are_holes_inside(geometry::interior_rings(polygon),
394                                     geometry::exterior_ring(polygon),
395                                     first,
396                                     beyond,
397                                     visitor,
398                                     strategy);
399         }
400     };
401 
402 
403 
404 
405     struct has_connected_interior
406     {
407         template <typename TurnIterator, typename VisitPolicy, typename Strategy>
applyboost::geometry::detail::is_valid::is_valid_polygon::has_connected_interior408         static inline bool apply(Polygon const& polygon,
409                                  TurnIterator first,
410                                  TurnIterator beyond,
411                                  VisitPolicy& visitor,
412                                  Strategy const& )
413         {
414             boost::ignore_unused(visitor);
415 
416             typedef typename std::iterator_traits
417                 <
418                     TurnIterator
419                 >::value_type turn_type;
420             typedef complement_graph<typename turn_type::point_type> graph;
421 
422             graph g(geometry::num_interior_rings(polygon) + 1);
423             for (TurnIterator tit = first; tit != beyond; ++tit)
424             {
425                 typename graph::vertex_handle v1 = g.add_vertex
426                     ( tit->operations[0].seg_id.ring_index + 1 );
427                 typename graph::vertex_handle v2 = g.add_vertex
428                     ( tit->operations[1].seg_id.ring_index + 1 );
429                 typename graph::vertex_handle vip = g.add_vertex(tit->point);
430 
431                 g.add_edge(v1, vip);
432                 g.add_edge(v2, vip);
433             }
434 
435 #ifdef BOOST_GEOMETRY_TEST_DEBUG
436             debug_print_complement_graph(std::cout, g);
437 #endif // BOOST_GEOMETRY_TEST_DEBUG
438 
439             if (g.has_cycles())
440             {
441                 return visitor.template apply<failure_disconnected_interior>();
442             }
443             else
444             {
445                 return visitor.template apply<no_failure>();
446             }
447         }
448     };
449 
450 public:
451     template <typename VisitPolicy, typename Strategy>
apply(Polygon const & polygon,VisitPolicy & visitor,Strategy const & strategy)452     static inline bool apply(Polygon const& polygon,
453                              VisitPolicy& visitor,
454                              Strategy const& strategy)
455     {
456         if (! has_valid_rings::apply(polygon, visitor, strategy))
457         {
458             return false;
459         }
460 
461         if (BOOST_GEOMETRY_CONDITION(CheckRingValidityOnly))
462         {
463             return true;
464         }
465 
466         // compute turns and check if all are acceptable
467         debug_phase::apply(3);
468 
469         typedef has_valid_self_turns<Polygon> has_valid_turns;
470 
471         std::deque<typename has_valid_turns::turn_type> turns;
472         bool has_invalid_turns
473             = ! has_valid_turns::apply(polygon, turns, visitor, strategy);
474         debug_print_turns(turns.begin(), turns.end());
475 
476         if (has_invalid_turns)
477         {
478             return false;
479         }
480 
481         // check if all interior rings are inside the exterior ring
482         debug_phase::apply(4);
483 
484         if (! has_holes_inside::apply(polygon,
485                                       turns.begin(), turns.end(),
486                                       visitor,
487                                       strategy))
488         {
489             return false;
490         }
491 
492         // check whether the interior of the polygon is a connected set
493         debug_phase::apply(5);
494 
495         return has_connected_interior::apply(polygon,
496                                              turns.begin(),
497                                              turns.end(),
498                                              visitor,
499                                              strategy);
500     }
501 };
502 
503 
504 }} // namespace detail::is_valid
505 #endif // DOXYGEN_NO_DETAIL
506 
507 
508 
509 #ifndef DOXYGEN_NO_DISPATCH
510 namespace dispatch
511 {
512 
513 
514 // A Polygon is always a simple geometric object provided that it is valid.
515 //
516 // Reference (for validity of Polygons): OGC 06-103r4 (6.1.11.1)
517 template <typename Polygon, bool AllowEmptyMultiGeometries>
518 struct is_valid
519     <
520         Polygon, polygon_tag, AllowEmptyMultiGeometries
521     > : detail::is_valid::is_valid_polygon<Polygon>
522 {};
523 
524 
525 } // namespace dispatch
526 #endif // DOXYGEN_NO_DISPATCH
527 
528 
529 }} // namespace boost::geometry
530 
531 #endif // BOOST_GEOMETRY_ALGORITHMS_DETAIL_IS_VALID_POLYGON_HPP
532