diff options
Diffstat (limited to 'boost/geometry/algorithms/detail/is_valid/polygon.hpp')
| -rw-r--r-- | boost/geometry/algorithms/detail/is_valid/polygon.hpp | 376 |
1 files changed, 376 insertions, 0 deletions
diff --git a/boost/geometry/algorithms/detail/is_valid/polygon.hpp b/boost/geometry/algorithms/detail/is_valid/polygon.hpp new file mode 100644 index 0000000000..3a91999208 --- /dev/null +++ b/boost/geometry/algorithms/detail/is_valid/polygon.hpp @@ -0,0 +1,376 @@ +// Boost.Geometry (aka GGL, Generic Geometry Library) + +// Copyright (c) 2014, Oracle and/or its affiliates. + +// Contributed and/or modified by Menelaos Karavelas, on behalf of Oracle + +// Licensed under the Boost Software License version 1.0. +// http://www.boost.org/users/license.html + +#ifndef BOOST_GEOMETRY_ALGORITHMS_DETAIL_IS_VALID_POLYGON_HPP +#define BOOST_GEOMETRY_ALGORITHMS_DETAIL_IS_VALID_POLYGON_HPP + +#include <cstddef> + +#include <algorithm> +#include <deque> +#include <iterator> +#include <set> +#include <vector> + +#include <boost/assert.hpp> +#include <boost/range.hpp> + +#include <boost/geometry/core/exterior_ring.hpp> +#include <boost/geometry/core/interior_rings.hpp> +#include <boost/geometry/core/ring_type.hpp> +#include <boost/geometry/core/tags.hpp> + +#include <boost/geometry/util/range.hpp> + +#include <boost/geometry/geometries/box.hpp> + +#include <boost/geometry/iterators/point_iterator.hpp> + +#include <boost/geometry/algorithms/covered_by.hpp> +#include <boost/geometry/algorithms/disjoint.hpp> +#include <boost/geometry/algorithms/expand.hpp> +#include <boost/geometry/algorithms/num_interior_rings.hpp> +#include <boost/geometry/algorithms/within.hpp> + +#include <boost/geometry/algorithms/detail/check_iterator_range.hpp> +#include <boost/geometry/algorithms/detail/partition.hpp> + +#include <boost/geometry/algorithms/detail/is_valid/complement_graph.hpp> +#include <boost/geometry/algorithms/detail/is_valid/has_valid_self_turns.hpp> +#include <boost/geometry/algorithms/detail/is_valid/is_acceptable_turn.hpp> +#include <boost/geometry/algorithms/detail/is_valid/ring.hpp> + +#include <boost/geometry/algorithms/detail/is_valid/debug_print_turns.hpp> +#include <boost/geometry/algorithms/detail/is_valid/debug_validity_phase.hpp> +#include <boost/geometry/algorithms/detail/is_valid/debug_complement_graph.hpp> + +#include <boost/geometry/algorithms/dispatch/is_valid.hpp> + + +namespace boost { namespace geometry +{ + + +#ifndef DOXYGEN_NO_DETAIL +namespace detail { namespace is_valid +{ + + +template +< + typename Polygon, + bool AllowDuplicates, + bool CheckRingValidityOnly = false +> +class is_valid_polygon +{ +protected: + typedef debug_validity_phase<Polygon> debug_phase; + + + + template <typename InteriorRings> + static bool has_valid_interior_rings(InteriorRings const& interior_rings) + { + return + detail::check_iterator_range + < + detail::is_valid::is_valid_ring + < + typename boost::range_value<InteriorRings>::type, + AllowDuplicates, + false, // do not check self-intersections + true // indicate that the ring is interior + > + >::apply(boost::begin(interior_rings), + boost::end(interior_rings)); + } + + struct has_valid_rings + { + static inline bool apply(Polygon const& polygon) + { + typedef typename ring_type<Polygon>::type ring_type; + + // check validity of exterior ring + debug_phase::apply(1); + + if ( !detail::is_valid::is_valid_ring + < + ring_type, + AllowDuplicates, + false // do not check self intersections + >::apply(exterior_ring(polygon)) ) + { + return false; + } + + // check validity of interior rings + debug_phase::apply(2); + + return has_valid_interior_rings(geometry::interior_rings(polygon)); + } + }; + + + // structs from partition -- start + struct expand_box + { + template <typename Box, typename Iterator> + static inline void apply(Box& total, Iterator const& it) + { + geometry::expand(total, geometry::return_envelope<Box>(*it)); + } + + }; + + struct overlaps_box + { + template <typename Box, typename Iterator> + static inline bool apply(Box const& box, Iterator const& it) + { + return !geometry::disjoint(*it, box); + } + }; + + + struct item_visitor + { + bool items_overlap; + + item_visitor() : items_overlap(false) {} + + template <typename Item1, typename Item2> + inline void apply(Item1 const& item1, Item2 const& item2) + { + if ( !items_overlap + && (geometry::within(*points_begin(*item1), *item2) + || geometry::within(*points_begin(*item2), *item1)) + ) + { + items_overlap = true; + } + } + }; + // structs for partition -- end + + + template + < + typename RingIterator, + typename ExteriorRing, + typename TurnIterator + > + static inline bool are_holes_inside(RingIterator rings_first, + RingIterator rings_beyond, + ExteriorRing const& exterior_ring, + TurnIterator turns_first, + TurnIterator turns_beyond) + { + // collect the interior ring indices that have turns with the + // exterior ring + std::set<signed_index_type> ring_indices; + for (TurnIterator tit = turns_first; tit != turns_beyond; ++tit) + { + if ( tit->operations[0].seg_id.ring_index == -1 ) + { + BOOST_ASSERT( tit->operations[1].seg_id.ring_index != -1 ); + ring_indices.insert(tit->operations[1].seg_id.ring_index); + } + else if ( tit->operations[1].seg_id.ring_index == -1 ) + { + BOOST_ASSERT( tit->operations[0].seg_id.ring_index != -1 ); + ring_indices.insert(tit->operations[0].seg_id.ring_index); + } + } + + signed_index_type ring_index = 0; + for (RingIterator it = rings_first; it != rings_beyond; + ++it, ++ring_index) + { + // do not examine interior rings that have turns with the + // exterior ring + if ( ring_indices.find(ring_index) == ring_indices.end() + && !geometry::covered_by(range::front(*it), exterior_ring) ) + { + return false; + } + } + + // collect all rings (exterior and/or interior) that have turns + for (TurnIterator tit = turns_first; tit != turns_beyond; ++tit) + { + ring_indices.insert(tit->operations[0].seg_id.ring_index); + ring_indices.insert(tit->operations[1].seg_id.ring_index); + } + + // put iterators for interior rings without turns in a vector + std::vector<RingIterator> ring_iterators; + ring_index = 0; + for (RingIterator it = rings_first; it != rings_beyond; + ++it, ++ring_index) + { + if ( ring_indices.find(ring_index) == ring_indices.end() ) + { + ring_iterators.push_back(it); + } + } + + // call partition to check is interior rings are disjoint from + // each other + item_visitor visitor; + + geometry::partition + < + geometry::model::box<typename point_type<Polygon>::type>, + expand_box, + overlaps_box + >::apply(ring_iterators, visitor); + + return !visitor.items_overlap; + } + + template + < + typename InteriorRings, + typename ExteriorRing, + typename TurnIterator + > + static inline bool are_holes_inside(InteriorRings const& interior_rings, + ExteriorRing const& exterior_ring, + TurnIterator first, + TurnIterator beyond) + { + return are_holes_inside(boost::begin(interior_rings), + boost::end(interior_rings), + exterior_ring, + first, + beyond); + } + + struct has_holes_inside + { + template <typename TurnIterator> + static inline bool apply(Polygon const& polygon, + TurnIterator first, + TurnIterator beyond) + { + return are_holes_inside(geometry::interior_rings(polygon), + geometry::exterior_ring(polygon), + first, + beyond); + } + }; + + + + + struct has_connected_interior + { + template <typename TurnIterator> + static inline bool apply(Polygon const& polygon, + TurnIterator first, + TurnIterator beyond) + { + typedef typename std::iterator_traits + < + TurnIterator + >::value_type turn_type; + typedef complement_graph<typename turn_type::point_type> graph; + + graph g(geometry::num_interior_rings(polygon) + 1); + for (TurnIterator tit = first; tit != beyond; ++tit) + { + typename graph::vertex_handle v1 = g.add_vertex + ( tit->operations[0].seg_id.ring_index + 1 ); + typename graph::vertex_handle v2 = g.add_vertex + ( tit->operations[1].seg_id.ring_index + 1 ); + typename graph::vertex_handle vip = g.add_vertex(tit->point); + + g.add_edge(v1, vip); + g.add_edge(v2, vip); + } + + debug_print_complement_graph(std::cout, g); + + return !g.has_cycles(); + } + }; + +public: + static inline bool apply(Polygon const& polygon) + { + if ( !has_valid_rings::apply(polygon) ) + { + return false; + } + + if ( CheckRingValidityOnly ) + { + return true; + } + + // compute turns and check if all are acceptable + debug_phase::apply(3); + + typedef has_valid_self_turns<Polygon> has_valid_turns; + + std::deque<typename has_valid_turns::turn_type> turns; + bool has_invalid_turns = !has_valid_turns::apply(polygon, turns); + debug_print_turns(turns.begin(), turns.end()); + + if ( has_invalid_turns ) + { + return false; + } + + // check if all interior rings are inside the exterior ring + debug_phase::apply(4); + + if ( !has_holes_inside::apply(polygon, turns.begin(), turns.end()) ) + { + return false; + } + + // check whether the interior of the polygon is a connected set + debug_phase::apply(5); + + return has_connected_interior::apply(polygon, + turns.begin(), + turns.end()); + } +}; + + +}} // namespace detail::is_valid +#endif // DOXYGEN_NO_DETAIL + + + +#ifndef DOXYGEN_NO_DISPATCH +namespace dispatch +{ + + +// A Polygon is always a simple geometric object provided that it is valid. +// +// Reference (for validity of Polygons): OGC 06-103r4 (6.1.11.1) +template <typename Polygon, bool AllowSpikes, bool AllowDuplicates> +struct is_valid<Polygon, polygon_tag, AllowSpikes, AllowDuplicates> + : detail::is_valid::is_valid_polygon<Polygon, AllowDuplicates> +{}; + + +} // namespace dispatch +#endif // DOXYGEN_NO_DISPATCH + + +}} // namespace boost::geometry + +#endif // BOOST_GEOMETRY_ALGORITHMS_DETAIL_IS_VALID_POLYGON_HPP |