diff options
Diffstat (limited to 'boost/geometry/algorithms/detail/is_valid/polygon.hpp')
| -rw-r--r-- | boost/geometry/algorithms/detail/is_valid/polygon.hpp | 155 |
1 files changed, 126 insertions, 29 deletions
diff --git a/boost/geometry/algorithms/detail/is_valid/polygon.hpp b/boost/geometry/algorithms/detail/is_valid/polygon.hpp index f7e22fb8d2..5c6229b793 100644 --- a/boost/geometry/algorithms/detail/is_valid/polygon.hpp +++ b/boost/geometry/algorithms/detail/is_valid/polygon.hpp @@ -1,5 +1,7 @@ // Boost.Geometry (aka GGL, Generic Geometry Library) +// Copyright (c) 2017 Adam Wulkiewicz, Lodz, Poland. + // Copyright (c) 2014-2017, Oracle and/or its affiliates. // Contributed and/or modified by Menelaos Karavelas, on behalf of Oracle @@ -43,6 +45,7 @@ #include <boost/geometry/algorithms/expand.hpp> #include <boost/geometry/algorithms/num_interior_rings.hpp> #include <boost/geometry/algorithms/validity_failure_type.hpp> +#include <boost/geometry/algorithms/detail/point_on_border.hpp> #include <boost/geometry/algorithms/within.hpp> #include <boost/geometry/algorithms/detail/check_iterator_range.hpp> @@ -142,43 +145,103 @@ protected: }; + // Iterator value_type is a Ring or Polygon + template <typename Iterator, typename Box> + struct partition_item + { + explicit partition_item(Iterator it) + : m_it(it) + , m_is_initialized(false) + {} + + Iterator get() const + { + return m_it; + } + + template <typename EnvelopeStrategy> + Box const& get_envelope(EnvelopeStrategy const& strategy) const + { + if (! m_is_initialized) + { + m_box = geometry::return_envelope<Box>(*m_it, strategy); + m_is_initialized = true; + } + return m_box; + } + + private: + Iterator m_it; + mutable Box m_box; + mutable bool m_is_initialized; + }; + // structs for partition -- start + template <typename EnvelopeStrategy> struct expand_box { + explicit expand_box(EnvelopeStrategy const& strategy) : m_strategy(strategy) {} + template <typename Box, typename Iterator> - static inline void apply(Box& total, Iterator const& it) + inline void apply(Box& total, partition_item<Iterator, Box> const& item) const { - geometry::expand(total, geometry::return_envelope<Box>(*it)); + geometry::expand(total, item.get_envelope(m_strategy)); } + EnvelopeStrategy const& m_strategy; }; + template <typename EnvelopeStrategy> struct overlaps_box { + explicit overlaps_box(EnvelopeStrategy const& strategy) : m_strategy(strategy) {} + template <typename Box, typename Iterator> - static inline bool apply(Box const& box, Iterator const& it) + inline bool apply(Box const& box, partition_item<Iterator, Box> const& item) const { - return ! geometry::disjoint(*it, box); + return ! geometry::disjoint(item.get_envelope(m_strategy), box); } + + EnvelopeStrategy const& m_strategy; }; + template <typename WithinStrategy> struct item_visitor_type { bool items_overlap; + WithinStrategy const& m_strategy; + + explicit item_visitor_type(WithinStrategy const& strategy) + : items_overlap(false) + , m_strategy(strategy) + {} - item_visitor_type() : items_overlap(false) {} + template <typename Item> + inline bool is_within(Item const& first, Item const& second) + { + typename point_type<Polygon>::type point; + typedef detail::point_on_border::point_on_range<true> pob; + + // TODO: this should check for a point on the interior, instead + // of on border. Or it should check using the overlap function. + + return pob::apply(point, points_begin(first), points_end(first)) + && geometry::within(point, second, m_strategy); + } - template <typename Item1, typename Item2> - inline void apply(Item1 const& item1, Item2 const& item2) + template <typename Iterator, typename Box> + inline bool apply(partition_item<Iterator, Box> const& item1, + partition_item<Iterator, Box> const& item2) { if (! items_overlap - && (geometry::within(*points_begin(*item1), *item2) - || geometry::within(*points_begin(*item2), *item1)) - ) + && (is_within(*item1.get(), *item2.get()) + || is_within(*item2.get(), *item1.get()))) { items_overlap = true; + return false; // interrupt } + return true; } }; // structs for partition -- end @@ -189,14 +252,16 @@ protected: typename RingIterator, typename ExteriorRing, typename TurnIterator, - typename VisitPolicy + typename VisitPolicy, + typename Strategy > static inline bool are_holes_inside(RingIterator rings_first, RingIterator rings_beyond, ExteriorRing const& exterior_ring, TurnIterator turns_first, TurnIterator turns_beyond, - VisitPolicy& visitor) + VisitPolicy& visitor, + Strategy const& strategy) { boost::ignore_unused(visitor); @@ -217,6 +282,14 @@ protected: } } + // prepare strategy + typedef typename std::iterator_traits<RingIterator>::value_type inter_ring_type; + typename Strategy::template point_in_geometry_strategy + < + inter_ring_type, ExteriorRing + >::type const in_exterior_strategy + = strategy.template get_point_in_geometry_strategy<inter_ring_type, ExteriorRing>(); + signed_size_type ring_index = 0; for (RingIterator it = rings_first; it != rings_beyond; ++it, ++ring_index) @@ -224,7 +297,7 @@ protected: // 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)) + && ! geometry::covered_by(range::front(*it), exterior_ring, in_exterior_strategy)) { return visitor.template apply<failure_interior_rings_outside>(); } @@ -237,26 +310,42 @@ protected: ring_indices.insert(tit->operations[1].seg_id.ring_index); } + typedef geometry::model::box<typename point_type<Polygon>::type> box_type; + typedef partition_item<RingIterator, box_type> item_type; + // put iterators for interior rings without turns in a vector - std::vector<RingIterator> ring_iterators; + std::vector<item_type> 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); + ring_iterators.push_back(item_type(it)); } } - // call partition to check is interior rings are disjoint from + // prepare strategies + typedef typename Strategy::template point_in_geometry_strategy + < + inter_ring_type, inter_ring_type + >::type in_interior_strategy_type; + in_interior_strategy_type const in_interior_strategy + = strategy.template get_point_in_geometry_strategy<inter_ring_type, inter_ring_type>(); + typedef typename Strategy::envelope_strategy_type envelope_strategy_type; + envelope_strategy_type const envelope_strategy + = strategy.get_envelope_strategy(); + + // call partition to check if interior rings are disjoint from // each other - item_visitor_type item_visitor; + item_visitor_type<in_interior_strategy_type> item_visitor(in_interior_strategy); geometry::partition < - geometry::model::box<typename point_type<Polygon>::type> - >::apply(ring_iterators, item_visitor, expand_box(), overlaps_box()); + box_type + >::apply(ring_iterators, item_visitor, + expand_box<envelope_strategy_type>(envelope_strategy), + overlaps_box<envelope_strategy_type>(envelope_strategy)); if (item_visitor.items_overlap) { @@ -273,35 +362,40 @@ protected: typename InteriorRings, typename ExteriorRing, typename TurnIterator, - typename VisitPolicy + typename VisitPolicy, + typename Strategy > static inline bool are_holes_inside(InteriorRings const& interior_rings, ExteriorRing const& exterior_ring, TurnIterator first, TurnIterator beyond, - VisitPolicy& visitor) + VisitPolicy& visitor, + Strategy const& strategy) { return are_holes_inside(boost::begin(interior_rings), boost::end(interior_rings), exterior_ring, first, beyond, - visitor); + visitor, + strategy); } struct has_holes_inside { - template <typename TurnIterator, typename VisitPolicy> + template <typename TurnIterator, typename VisitPolicy, typename Strategy> static inline bool apply(Polygon const& polygon, TurnIterator first, TurnIterator beyond, - VisitPolicy& visitor) + VisitPolicy& visitor, + Strategy const& strategy) { return are_holes_inside(geometry::interior_rings(polygon), geometry::exterior_ring(polygon), first, beyond, - visitor); + visitor, + strategy); } }; @@ -310,11 +404,12 @@ protected: struct has_connected_interior { - template <typename TurnIterator, typename VisitPolicy> + template <typename TurnIterator, typename VisitPolicy, typename Strategy> static inline bool apply(Polygon const& polygon, TurnIterator first, TurnIterator beyond, - VisitPolicy& visitor) + VisitPolicy& visitor, + Strategy const& ) { boost::ignore_unused(visitor); @@ -388,7 +483,8 @@ public: if (! has_holes_inside::apply(polygon, turns.begin(), turns.end(), - visitor)) + visitor, + strategy)) { return false; } @@ -399,7 +495,8 @@ public: return has_connected_interior::apply(polygon, turns.begin(), turns.end(), - visitor); + visitor, + strategy); } }; |