diff options
Diffstat (limited to 'boost/geometry/algorithms/detail/overlay/assign_parents.hpp')
| -rw-r--r-- | boost/geometry/algorithms/detail/overlay/assign_parents.hpp | 136 |
1 files changed, 100 insertions, 36 deletions
diff --git a/boost/geometry/algorithms/detail/overlay/assign_parents.hpp b/boost/geometry/algorithms/detail/overlay/assign_parents.hpp index 2408b4b68e..78160f5204 100644 --- a/boost/geometry/algorithms/detail/overlay/assign_parents.hpp +++ b/boost/geometry/algorithms/detail/overlay/assign_parents.hpp @@ -20,7 +20,8 @@ #include <boost/geometry/algorithms/expand.hpp> #include <boost/geometry/algorithms/detail/partition.hpp> #include <boost/geometry/algorithms/detail/overlay/get_ring.hpp> -#include <boost/geometry/algorithms/within.hpp> +#include <boost/geometry/algorithms/detail/overlay/range_in_geometry.hpp> +#include <boost/geometry/algorithms/covered_by.hpp> #include <boost/geometry/geometries/box.hpp> @@ -37,50 +38,88 @@ namespace detail { namespace overlay template < typename Item, + typename InnerGeometry, typename Geometry1, typename Geometry2, - typename RingCollection + typename RingCollection, + typename Strategy +> +static inline bool within_selected_input(Item const& item2, + InnerGeometry const& inner_geometry, + ring_identifier const& outer_id, + Geometry1 const& geometry1, Geometry2 const& geometry2, + RingCollection const& collection, + Strategy const& strategy) +{ + typedef typename geometry::tag<Geometry1>::type tag1; + typedef typename geometry::tag<Geometry2>::type tag2; + + // NOTE: range_in_geometry first checks the item2.point and then + // if this point is on boundary it checks points of inner_geometry + // ring until a point inside/outside other geometry ring is found + switch (outer_id.source_index) + { + // covered_by + case 0 : + return range_in_geometry(item2.point, inner_geometry, + get_ring<tag1>::apply(outer_id, geometry1), strategy) >= 0; + case 1 : + return range_in_geometry(item2.point, inner_geometry, + get_ring<tag2>::apply(outer_id, geometry2), strategy) >= 0; + case 2 : + return range_in_geometry(item2.point, inner_geometry, + get_ring<void>::apply(outer_id, collection), strategy) >= 0; + } + return false; +} + +template +< + typename Item, + typename Geometry1, typename Geometry2, + typename RingCollection, + typename Strategy > -static inline bool within_selected_input(Item const& item2, ring_identifier const& ring_id, +static inline bool within_selected_input(Item const& item2, + ring_identifier const& inner_id, ring_identifier const& outer_id, Geometry1 const& geometry1, Geometry2 const& geometry2, - RingCollection const& collection) + RingCollection const& collection, + Strategy const& strategy) { typedef typename geometry::tag<Geometry1>::type tag1; typedef typename geometry::tag<Geometry2>::type tag2; - switch (ring_id.source_index) + switch (inner_id.source_index) { case 0 : - return geometry::within(item2.point, - get_ring<tag1>::apply(ring_id, geometry1)); - break; + return within_selected_input(item2, + get_ring<tag1>::apply(inner_id, geometry1), + outer_id, geometry1, geometry2, collection, strategy); case 1 : - return geometry::within(item2.point, - get_ring<tag2>::apply(ring_id, geometry2)); - break; + return within_selected_input(item2, + get_ring<tag2>::apply(inner_id, geometry2), + outer_id, geometry1, geometry2, collection, strategy); case 2 : - return geometry::within(item2.point, - get_ring<void>::apply(ring_id, collection)); - break; + return within_selected_input(item2, + get_ring<void>::apply(inner_id, collection), + outer_id, geometry1, geometry2, collection, strategy); } return false; } -template <typename Point> +template <typename Point, typename AreaType> struct ring_info_helper { - typedef typename geometry::default_area_result<Point>::type area_type; - ring_identifier id; - area_type real_area; - area_type abs_area; + AreaType real_area; + AreaType abs_area; model::box<Point> envelope; inline ring_info_helper() : real_area(0), abs_area(0) {} - inline ring_info_helper(ring_identifier i, area_type a) + inline ring_info_helper(ring_identifier i, AreaType const& a) : id(i), real_area(a), abs_area(geometry::math::abs(a)) {} }; @@ -104,7 +143,14 @@ struct ring_info_helper_ovelaps_box } }; -template <typename Geometry1, typename Geometry2, typename Collection, typename RingMap> +template +< + typename Geometry1, + typename Geometry2, + typename Collection, + typename RingMap, + typename Strategy +> struct assign_visitor { typedef typename RingMap::mapped_type ring_info_type; @@ -113,26 +159,27 @@ struct assign_visitor Geometry2 const& m_geometry2; Collection const& m_collection; RingMap& m_ring_map; + Strategy const& m_strategy; bool m_check_for_orientation; - inline assign_visitor(Geometry1 const& g1, Geometry2 const& g2, Collection const& c, - RingMap& map, bool check) + RingMap& map, Strategy const& strategy, bool check) : m_geometry1(g1) , m_geometry2(g2) , m_collection(c) , m_ring_map(map) + , m_strategy(strategy) , m_check_for_orientation(check) {} template <typename Item> - inline void apply(Item const& outer, Item const& inner, bool first = true) + inline bool apply(Item const& outer, Item const& inner, bool first = true) { if (first && outer.abs_area < inner.abs_area) { // Apply with reversed arguments apply(inner, outer, false); - return; + return true; } if (m_check_for_orientation @@ -141,8 +188,10 @@ struct assign_visitor { ring_info_type& inner_in_map = m_ring_map[inner.id]; - if (geometry::within(inner_in_map.point, outer.envelope) - && within_selected_input(inner_in_map, outer.id, m_geometry1, m_geometry2, m_collection) + if (geometry::covered_by(inner_in_map.point, outer.envelope) + && within_selected_input(inner_in_map, inner.id, outer.id, + m_geometry1, m_geometry2, m_collection, + m_strategy) ) { // Assign a parent if there was no earlier parent, or the newly @@ -155,6 +204,8 @@ struct assign_visitor } } } + + return true; } }; @@ -165,12 +216,14 @@ template < typename Geometry1, typename Geometry2, typename RingCollection, - typename RingMap + typename RingMap, + typename Strategy > inline void assign_parents(Geometry1 const& geometry1, Geometry2 const& geometry2, RingCollection const& collection, RingMap& ring_map, + Strategy const& strategy, bool check_for_orientation = false) { typedef typename geometry::tag<Geometry1>::type tag1; @@ -179,11 +232,15 @@ inline void assign_parents(Geometry1 const& geometry1, typedef typename RingMap::mapped_type ring_info_type; typedef typename ring_info_type::point_type point_type; typedef model::box<point_type> box_type; + typedef typename Strategy::template area_strategy + < + point_type + >::type::return_type area_result_type; typedef typename RingMap::iterator map_iterator_type; { - typedef ring_info_helper<point_type> helper; + typedef ring_info_helper<point_type, area_result_type> helper; typedef std::vector<helper> vector_type; typedef typename boost::range_iterator<vector_type const>::type vector_iterator_type; @@ -204,17 +261,21 @@ inline void assign_parents(Geometry1 const& geometry1, { case 0 : geometry::envelope(get_ring<tag1>::apply(it->first, geometry1), - item.envelope); + item.envelope, strategy.get_envelope_strategy()); break; case 1 : geometry::envelope(get_ring<tag2>::apply(it->first, geometry2), - item.envelope); + item.envelope, strategy.get_envelope_strategy()); break; case 2 : geometry::envelope(get_ring<void>::apply(it->first, collection), - item.envelope); + item.envelope, strategy.get_envelope_strategy()); break; } + + // Expand envelope slightly + expand_by_epsilon(item.envelope); + if (item.real_area > 0) { count_positive++; @@ -257,8 +318,9 @@ inline void assign_parents(Geometry1 const& geometry1, assign_visitor < Geometry1, Geometry2, - RingCollection, RingMap - > visitor(geometry1, geometry2, collection, ring_map, check_for_orientation); + RingCollection, RingMap, + Strategy + > visitor(geometry1, geometry2, collection, ring_map, strategy, check_for_orientation); geometry::partition < @@ -315,18 +377,20 @@ template < typename Geometry, typename RingCollection, - typename RingMap + typename RingMap, + typename Strategy > inline void assign_parents(Geometry const& geometry, RingCollection const& collection, RingMap& ring_map, + Strategy const& strategy, bool check_for_orientation) { // Call it with an empty geometry as second geometry (source_id == 1) // (ring_map should be empty for source_id==1) Geometry empty; - assign_parents(geometry, empty, collection, ring_map, check_for_orientation); + assign_parents(geometry, empty, collection, ring_map, strategy, check_for_orientation); } |