1 // Boost.Geometry (aka GGL, Generic Geometry Library)
3 // Copyright (c) 2017 Adam Wulkiewicz, Lodz, Poland.
5 // Copyright (c) 2014-2017, Oracle and/or its affiliates.
7 // Contributed and/or modified by Menelaos Karavelas, on behalf of Oracle
8 // Contributed and/or modified by Adam Wulkiewicz, on behalf of Oracle
10 // Licensed under the Boost Software License version 1.0.
11 // http://www.boost.org/users/license.html
13 #ifndef BOOST_GEOMETRY_ALGORITHMS_DETAIL_IS_VALID_POLYGON_HPP
14 #define BOOST_GEOMETRY_ALGORITHMS_DETAIL_IS_VALID_POLYGON_HPP
17 #ifdef BOOST_GEOMETRY_TEST_DEBUG
19 #endif // BOOST_GEOMETRY_TEST_DEBUG
27 #include <boost/core/ignore_unused.hpp>
28 #include <boost/range.hpp>
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>
36 #include <boost/geometry/util/condition.hpp>
37 #include <boost/geometry/util/range.hpp>
39 #include <boost/geometry/geometries/box.hpp>
41 #include <boost/geometry/iterators/point_iterator.hpp>
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>
51 #include <boost/geometry/algorithms/detail/check_iterator_range.hpp>
52 #include <boost/geometry/algorithms/detail/partition.hpp>
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>
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>
63 #include <boost/geometry/algorithms/dispatch/is_valid.hpp>
66 namespace boost { namespace geometry
70 #ifndef DOXYGEN_NO_DETAIL
71 namespace detail { namespace is_valid
75 template <typename Polygon, bool CheckRingValidityOnly = false>
76 class is_valid_polygon
79 typedef debug_validity_phase<Polygon> debug_phase;
81 template <typename VisitPolicy, typename Strategy>
84 per_ring(VisitPolicy& policy, Strategy const& strategy)
86 , m_strategy(strategy)
89 template <typename Ring>
90 inline bool apply(Ring const& ring) const
92 return detail::is_valid::is_valid_ring
95 >::apply(ring, m_policy, m_strategy);
98 VisitPolicy& m_policy;
99 Strategy const& m_strategy;
102 template <typename InteriorRings, typename VisitPolicy, typename Strategy>
103 static bool has_valid_interior_rings(InteriorRings const& interior_rings,
104 VisitPolicy& visitor,
105 Strategy const& strategy)
108 detail::check_iterator_range
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));
117 struct has_valid_rings
119 template <typename VisitPolicy, typename Strategy>
120 static inline bool apply(Polygon const& polygon,
121 VisitPolicy& visitor,
122 Strategy const& strategy)
124 typedef typename ring_type<Polygon>::type ring_type;
126 // check validity of exterior ring
127 debug_phase::apply(1);
129 if (! detail::is_valid::is_valid_ring
132 false // do not check self intersections
133 >::apply(exterior_ring(polygon), visitor, strategy))
138 // check validity of interior rings
139 debug_phase::apply(2);
141 return has_valid_interior_rings(geometry::interior_rings(polygon),
148 // Iterator value_type is a Ring or Polygon
149 template <typename Iterator, typename Box>
150 struct partition_item
152 explicit partition_item(Iterator it)
154 , m_is_initialized(false)
162 template <typename EnvelopeStrategy>
163 Box const& get_envelope(EnvelopeStrategy const& strategy) const
165 if (! m_is_initialized)
167 m_box = geometry::return_envelope<Box>(*m_it, strategy);
168 m_is_initialized = true;
176 mutable bool m_is_initialized;
179 // structs for partition -- start
180 template <typename EnvelopeStrategy>
183 explicit expand_box(EnvelopeStrategy const& strategy) : m_strategy(strategy) {}
185 template <typename Box, typename Iterator>
186 inline void apply(Box& total, partition_item<Iterator, Box> const& item) const
188 geometry::expand(total, item.get_envelope(m_strategy));
191 EnvelopeStrategy const& m_strategy;
194 template <typename EnvelopeStrategy>
197 explicit overlaps_box(EnvelopeStrategy const& strategy) : m_strategy(strategy) {}
199 template <typename Box, typename Iterator>
200 inline bool apply(Box const& box, partition_item<Iterator, Box> const& item) const
202 return ! geometry::disjoint(item.get_envelope(m_strategy), box);
205 EnvelopeStrategy const& m_strategy;
209 template <typename WithinStrategy>
210 struct item_visitor_type
213 WithinStrategy const& m_strategy;
215 explicit item_visitor_type(WithinStrategy const& strategy)
216 : items_overlap(false)
217 , m_strategy(strategy)
220 template <typename Item>
221 inline bool is_within(Item const& first, Item const& second)
223 typename point_type<Polygon>::type point;
224 typedef detail::point_on_border::point_on_range<true> pob;
226 // TODO: this should check for a point on the interior, instead
227 // of on border. Or it should check using the overlap function.
229 return pob::apply(point, points_begin(first), points_end(first))
230 && geometry::within(point, second, m_strategy);
233 template <typename Iterator, typename Box>
234 inline bool apply(partition_item<Iterator, Box> const& item1,
235 partition_item<Iterator, Box> const& item2)
238 && (is_within(*item1.get(), *item2.get())
239 || is_within(*item2.get(), *item1.get())))
241 items_overlap = true;
242 return false; // interrupt
247 // structs for partition -- end
252 typename RingIterator,
253 typename ExteriorRing,
254 typename TurnIterator,
255 typename VisitPolicy,
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)
266 boost::ignore_unused(visitor);
268 // collect the interior ring indices that have turns with the
270 std::set<signed_size_type> ring_indices;
271 for (TurnIterator tit = turns_first; tit != turns_beyond; ++tit)
273 if (tit->operations[0].seg_id.ring_index == -1)
275 BOOST_GEOMETRY_ASSERT(tit->operations[1].seg_id.ring_index != -1);
276 ring_indices.insert(tit->operations[1].seg_id.ring_index);
278 else if (tit->operations[1].seg_id.ring_index == -1)
280 BOOST_GEOMETRY_ASSERT(tit->operations[0].seg_id.ring_index != -1);
281 ring_indices.insert(tit->operations[0].seg_id.ring_index);
286 typedef typename std::iterator_traits<RingIterator>::value_type inter_ring_type;
287 typename Strategy::template point_in_geometry_strategy
289 inter_ring_type, ExteriorRing
290 >::type const in_exterior_strategy
291 = strategy.template get_point_in_geometry_strategy<inter_ring_type, ExteriorRing>();
293 signed_size_type ring_index = 0;
294 for (RingIterator it = rings_first; it != rings_beyond;
297 // do not examine interior rings that have turns with the
299 if (ring_indices.find(ring_index) == ring_indices.end()
300 && ! geometry::covered_by(range::front(*it), exterior_ring, in_exterior_strategy))
302 return visitor.template apply<failure_interior_rings_outside>();
306 // collect all rings (exterior and/or interior) that have turns
307 for (TurnIterator tit = turns_first; tit != turns_beyond; ++tit)
309 ring_indices.insert(tit->operations[0].seg_id.ring_index);
310 ring_indices.insert(tit->operations[1].seg_id.ring_index);
313 typedef geometry::model::box<typename point_type<Polygon>::type> box_type;
314 typedef partition_item<RingIterator, box_type> item_type;
316 // put iterators for interior rings without turns in a vector
317 std::vector<item_type> ring_iterators;
319 for (RingIterator it = rings_first; it != rings_beyond;
322 if (ring_indices.find(ring_index) == ring_indices.end())
324 ring_iterators.push_back(item_type(it));
328 // prepare strategies
329 typedef typename Strategy::template point_in_geometry_strategy
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();
339 // call partition to check if interior rings are disjoint from
341 item_visitor_type<in_interior_strategy_type> item_visitor(in_interior_strategy);
346 >::apply(ring_iterators, item_visitor,
347 expand_box<envelope_strategy_type>(envelope_strategy),
348 overlaps_box<envelope_strategy_type>(envelope_strategy));
350 if (item_visitor.items_overlap)
352 return visitor.template apply<failure_nested_interior_rings>();
356 return visitor.template apply<no_failure>();
362 typename InteriorRings,
363 typename ExteriorRing,
364 typename TurnIterator,
365 typename VisitPolicy,
368 static inline bool are_holes_inside(InteriorRings const& interior_rings,
369 ExteriorRing const& exterior_ring,
372 VisitPolicy& visitor,
373 Strategy const& strategy)
375 return are_holes_inside(boost::begin(interior_rings),
376 boost::end(interior_rings),
384 struct has_holes_inside
386 template <typename TurnIterator, typename VisitPolicy, typename Strategy>
387 static inline bool apply(Polygon const& polygon,
390 VisitPolicy& visitor,
391 Strategy const& strategy)
393 return are_holes_inside(geometry::interior_rings(polygon),
394 geometry::exterior_ring(polygon),
405 struct has_connected_interior
407 template <typename TurnIterator, typename VisitPolicy, typename Strategy>
408 static inline bool apply(Polygon const& polygon,
411 VisitPolicy& visitor,
414 boost::ignore_unused(visitor);
416 typedef typename std::iterator_traits
419 >::value_type turn_type;
420 typedef complement_graph<typename turn_type::point_type> graph;
422 graph g(geometry::num_interior_rings(polygon) + 1);
423 for (TurnIterator tit = first; tit != beyond; ++tit)
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);
435 #ifdef BOOST_GEOMETRY_TEST_DEBUG
436 debug_print_complement_graph(std::cout, g);
437 #endif // BOOST_GEOMETRY_TEST_DEBUG
441 return visitor.template apply<failure_disconnected_interior>();
445 return visitor.template apply<no_failure>();
451 template <typename VisitPolicy, typename Strategy>
452 static inline bool apply(Polygon const& polygon,
453 VisitPolicy& visitor,
454 Strategy const& strategy)
456 if (! has_valid_rings::apply(polygon, visitor, strategy))
461 if (BOOST_GEOMETRY_CONDITION(CheckRingValidityOnly))
466 // compute turns and check if all are acceptable
467 debug_phase::apply(3);
469 typedef has_valid_self_turns<Polygon> has_valid_turns;
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());
476 if (has_invalid_turns)
481 // check if all interior rings are inside the exterior ring
482 debug_phase::apply(4);
484 if (! has_holes_inside::apply(polygon,
485 turns.begin(), turns.end(),
492 // check whether the interior of the polygon is a connected set
493 debug_phase::apply(5);
495 return has_connected_interior::apply(polygon,
504 }} // namespace detail::is_valid
505 #endif // DOXYGEN_NO_DETAIL
509 #ifndef DOXYGEN_NO_DISPATCH
514 // A Polygon is always a simple geometric object provided that it is valid.
516 // Reference (for validity of Polygons): OGC 06-103r4 (6.1.11.1)
517 template <typename Polygon, bool AllowEmptyMultiGeometries>
520 Polygon, polygon_tag, AllowEmptyMultiGeometries
521 > : detail::is_valid::is_valid_polygon<Polygon>
525 } // namespace dispatch
526 #endif // DOXYGEN_NO_DISPATCH
529 }} // namespace boost::geometry
531 #endif // BOOST_GEOMETRY_ALGORITHMS_DETAIL_IS_VALID_POLYGON_HPP