1 // Boost.Geometry (aka GGL, Generic Geometry Library)
3 // Copyright (c) 2014-2015, Oracle and/or its affiliates.
5 // Contributed and/or modified by Menelaos Karavelas, on behalf of Oracle
7 // Licensed under the Boost Software License version 1.0.
8 // http://www.boost.org/users/license.html
10 #ifndef BOOST_GEOMETRY_ALGORITHMS_DETAIL_IS_VALID_POLYGON_HPP
11 #define BOOST_GEOMETRY_ALGORITHMS_DETAIL_IS_VALID_POLYGON_HPP
14 #ifdef BOOST_GEOMETRY_TEST_DEBUG
16 #endif // BOOST_GEOMETRY_TEST_DEBUG
24 #include <boost/core/ignore_unused.hpp>
25 #include <boost/range.hpp>
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>
33 #include <boost/geometry/util/condition.hpp>
34 #include <boost/geometry/util/range.hpp>
36 #include <boost/geometry/geometries/box.hpp>
38 #include <boost/geometry/iterators/point_iterator.hpp>
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>
47 #include <boost/geometry/algorithms/detail/check_iterator_range.hpp>
48 #include <boost/geometry/algorithms/detail/partition.hpp>
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>
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>
59 #include <boost/geometry/algorithms/dispatch/is_valid.hpp>
62 namespace boost { namespace geometry
66 #ifndef DOXYGEN_NO_DETAIL
67 namespace detail { namespace is_valid
71 template <typename Polygon, bool CheckRingValidityOnly = false>
72 class is_valid_polygon
75 typedef debug_validity_phase<Polygon> debug_phase;
77 template <typename VisitPolicy>
80 per_ring(VisitPolicy& policy) : m_policy(policy) {}
82 template <typename Ring>
83 inline bool apply(Ring const& ring) const
85 return detail::is_valid::is_valid_ring
88 >::apply(ring, m_policy);
91 VisitPolicy& m_policy;
94 template <typename InteriorRings, typename VisitPolicy>
95 static bool has_valid_interior_rings(InteriorRings const& interior_rings,
99 detail::check_iterator_range
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));
108 struct has_valid_rings
110 template <typename VisitPolicy>
111 static inline bool apply(Polygon const& polygon, VisitPolicy& visitor)
113 typedef typename ring_type<Polygon>::type ring_type;
115 // check validity of exterior ring
116 debug_phase::apply(1);
118 if (! detail::is_valid::is_valid_ring
121 false // do not check self intersections
122 >::apply(exterior_ring(polygon), visitor))
127 // check validity of interior rings
128 debug_phase::apply(2);
130 return has_valid_interior_rings(geometry::interior_rings(polygon),
136 // structs for partition -- start
139 template <typename Box, typename Iterator>
140 static inline void apply(Box& total, Iterator const& it)
142 geometry::expand(total, geometry::return_envelope<Box>(*it));
149 template <typename Box, typename Iterator>
150 static inline bool apply(Box const& box, Iterator const& it)
152 return ! geometry::disjoint(*it, box);
157 struct item_visitor_type
161 item_visitor_type() : items_overlap(false) {}
163 template <typename Item1, typename Item2>
164 inline void apply(Item1 const& item1, Item2 const& item2)
167 && (geometry::within(*points_begin(*item1), *item2)
168 || geometry::within(*points_begin(*item2), *item1))
171 items_overlap = true;
175 // structs for partition -- end
180 typename RingIterator,
181 typename ExteriorRing,
182 typename TurnIterator,
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)
192 boost::ignore_unused(visitor);
194 // collect the interior ring indices that have turns with the
196 std::set<signed_size_type> ring_indices;
197 for (TurnIterator tit = turns_first; tit != turns_beyond; ++tit)
199 if (tit->operations[0].seg_id.ring_index == -1)
201 BOOST_GEOMETRY_ASSERT(tit->operations[1].seg_id.ring_index != -1);
202 ring_indices.insert(tit->operations[1].seg_id.ring_index);
204 else if (tit->operations[1].seg_id.ring_index == -1)
206 BOOST_GEOMETRY_ASSERT(tit->operations[0].seg_id.ring_index != -1);
207 ring_indices.insert(tit->operations[0].seg_id.ring_index);
211 signed_size_type ring_index = 0;
212 for (RingIterator it = rings_first; it != rings_beyond;
215 // do not examine interior rings that have turns with the
217 if (ring_indices.find(ring_index) == ring_indices.end()
218 && ! geometry::covered_by(range::front(*it), exterior_ring))
220 return visitor.template apply<failure_interior_rings_outside>();
224 // collect all rings (exterior and/or interior) that have turns
225 for (TurnIterator tit = turns_first; tit != turns_beyond; ++tit)
227 ring_indices.insert(tit->operations[0].seg_id.ring_index);
228 ring_indices.insert(tit->operations[1].seg_id.ring_index);
231 // put iterators for interior rings without turns in a vector
232 std::vector<RingIterator> ring_iterators;
234 for (RingIterator it = rings_first; it != rings_beyond;
237 if (ring_indices.find(ring_index) == ring_indices.end())
239 ring_iterators.push_back(it);
243 // call partition to check is interior rings are disjoint from
245 item_visitor_type item_visitor;
249 geometry::model::box<typename point_type<Polygon>::type>,
252 >::apply(ring_iterators, item_visitor);
254 if (item_visitor.items_overlap)
256 return visitor.template apply<failure_nested_interior_rings>();
260 return visitor.template apply<no_failure>();
266 typename InteriorRings,
267 typename ExteriorRing,
268 typename TurnIterator,
271 static inline bool are_holes_inside(InteriorRings const& interior_rings,
272 ExteriorRing const& exterior_ring,
275 VisitPolicy& visitor)
277 return are_holes_inside(boost::begin(interior_rings),
278 boost::end(interior_rings),
285 struct has_holes_inside
287 template <typename TurnIterator, typename VisitPolicy>
288 static inline bool apply(Polygon const& polygon,
291 VisitPolicy& visitor)
293 return are_holes_inside(geometry::interior_rings(polygon),
294 geometry::exterior_ring(polygon),
304 struct has_connected_interior
306 template <typename TurnIterator, typename VisitPolicy>
307 static inline bool apply(Polygon const& polygon,
310 VisitPolicy& visitor)
312 boost::ignore_unused(visitor);
314 typedef typename std::iterator_traits
317 >::value_type turn_type;
318 typedef complement_graph<typename turn_type::point_type> graph;
320 graph g(geometry::num_interior_rings(polygon) + 1);
321 for (TurnIterator tit = first; tit != beyond; ++tit)
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);
333 #ifdef BOOST_GEOMETRY_TEST_DEBUG
334 debug_print_complement_graph(std::cout, g);
335 #endif // BOOST_GEOMETRY_TEST_DEBUG
339 return visitor.template apply<failure_disconnected_interior>();
343 return visitor.template apply<no_failure>();
349 template <typename VisitPolicy>
350 static inline bool apply(Polygon const& polygon, VisitPolicy& visitor)
352 if (! has_valid_rings::apply(polygon, visitor))
357 if (BOOST_GEOMETRY_CONDITION(CheckRingValidityOnly))
362 // compute turns and check if all are acceptable
363 debug_phase::apply(3);
365 typedef has_valid_self_turns<Polygon> has_valid_turns;
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());
372 if (has_invalid_turns)
377 // check if all interior rings are inside the exterior ring
378 debug_phase::apply(4);
380 if (! has_holes_inside::apply(polygon,
381 turns.begin(), turns.end(),
387 // check whether the interior of the polygon is a connected set
388 debug_phase::apply(5);
390 return has_connected_interior::apply(polygon,
398 }} // namespace detail::is_valid
399 #endif // DOXYGEN_NO_DETAIL
403 #ifndef DOXYGEN_NO_DISPATCH
408 // A Polygon is always a simple geometric object provided that it is valid.
410 // Reference (for validity of Polygons): OGC 06-103r4 (6.1.11.1)
411 template <typename Polygon, bool AllowEmptyMultiGeometries>
414 Polygon, polygon_tag, AllowEmptyMultiGeometries
415 > : detail::is_valid::is_valid_polygon<Polygon>
419 } // namespace dispatch
420 #endif // DOXYGEN_NO_DISPATCH
423 }} // namespace boost::geometry
425 #endif // BOOST_GEOMETRY_ALGORITHMS_DETAIL_IS_VALID_POLYGON_HPP