diff options
Diffstat (limited to 'boost/geometry/algorithms/detail/overlay/select_rings.hpp')
| -rw-r--r-- | boost/geometry/algorithms/detail/overlay/select_rings.hpp | 217 |
1 files changed, 120 insertions, 97 deletions
diff --git a/boost/geometry/algorithms/detail/overlay/select_rings.hpp b/boost/geometry/algorithms/detail/overlay/select_rings.hpp index 385658a190..d18e012b2d 100644 --- a/boost/geometry/algorithms/detail/overlay/select_rings.hpp +++ b/boost/geometry/algorithms/detail/overlay/select_rings.hpp @@ -1,6 +1,6 @@ // Boost.Geometry (aka GGL, Generic Geometry Library) -// Copyright (c) 2007-2012 Barend Gehrels, Amsterdam, the Netherlands. +// Copyright (c) 2007-2014 Barend Gehrels, Amsterdam, the Netherlands. // Copyright (c) 2014 Adam Wulkiewicz, Lodz, Poland. // Use, modification and distribution is subject to the Boost Software License, @@ -20,7 +20,6 @@ #include <boost/geometry/algorithms/area.hpp> #include <boost/geometry/algorithms/within.hpp> #include <boost/geometry/algorithms/detail/interior_iterator.hpp> -#include <boost/geometry/algorithms/detail/point_on_border.hpp> #include <boost/geometry/algorithms/detail/ring_identifier.hpp> #include <boost/geometry/algorithms/detail/overlay/ring_properties.hpp> #include <boost/geometry/algorithms/detail/overlay/overlay_type.hpp> @@ -34,6 +33,18 @@ namespace boost { namespace geometry namespace detail { namespace overlay { +struct ring_turn_info +{ + bool has_uu_turn; + bool has_normal_turn; + bool within_other; + + ring_turn_info() + : has_uu_turn(false) + , has_normal_turn(false) + , within_other(false) + {} +}; namespace dispatch { @@ -45,41 +56,41 @@ namespace dispatch template <typename Box> struct select_rings<box_tag, Box> { - template <typename Geometry, typename Map> + template <typename Geometry, typename RingPropertyMap> static inline void apply(Box const& box, Geometry const& , - ring_identifier const& id, Map& map, bool midpoint) + ring_identifier const& id, RingPropertyMap& ring_properties) { - map[id] = typename Map::mapped_type(box, midpoint); + ring_properties[id] = typename RingPropertyMap::mapped_type(box); } - template <typename Map> + template <typename RingPropertyMap> static inline void apply(Box const& box, - ring_identifier const& id, Map& map, bool midpoint) + ring_identifier const& id, RingPropertyMap& ring_properties) { - map[id] = typename Map::mapped_type(box, midpoint); + ring_properties[id] = typename RingPropertyMap::mapped_type(box); } }; template <typename Ring> struct select_rings<ring_tag, Ring> { - template <typename Geometry, typename Map> + template <typename Geometry, typename RingPropertyMap> static inline void apply(Ring const& ring, Geometry const& , - ring_identifier const& id, Map& map, bool midpoint) + ring_identifier const& id, RingPropertyMap& ring_properties) { if (boost::size(ring) > 0) { - map[id] = typename Map::mapped_type(ring, midpoint); + ring_properties[id] = typename RingPropertyMap::mapped_type(ring); } } - template <typename Map> + template <typename RingPropertyMap> static inline void apply(Ring const& ring, - ring_identifier const& id, Map& map, bool midpoint) + ring_identifier const& id, RingPropertyMap& ring_properties) { if (boost::size(ring) > 0) { - map[id] = typename Map::mapped_type(ring, midpoint); + ring_properties[id] = typename RingPropertyMap::mapped_type(ring); } } }; @@ -88,14 +99,14 @@ namespace dispatch template <typename Polygon> struct select_rings<polygon_tag, Polygon> { - template <typename Geometry, typename Map> + template <typename Geometry, typename RingPropertyMap> static inline void apply(Polygon const& polygon, Geometry const& geometry, - ring_identifier id, Map& map, bool midpoint) + ring_identifier id, RingPropertyMap& ring_properties) { typedef typename geometry::ring_type<Polygon>::type ring_type; typedef select_rings<ring_tag, ring_type> per_ring; - per_ring::apply(exterior_ring(polygon), geometry, id, map, midpoint); + per_ring::apply(exterior_ring(polygon), geometry, id, ring_properties); typename interior_return_type<Polygon const>::type rings = interior_rings(polygon); @@ -103,18 +114,18 @@ namespace dispatch it = boost::begin(rings); it != boost::end(rings); ++it) { id.ring_index++; - per_ring::apply(*it, geometry, id, map, midpoint); + per_ring::apply(*it, geometry, id, ring_properties); } } - template <typename Map> + template <typename RingPropertyMap> static inline void apply(Polygon const& polygon, - ring_identifier id, Map& map, bool midpoint) + ring_identifier id, RingPropertyMap& ring_properties) { typedef typename geometry::ring_type<Polygon>::type ring_type; typedef select_rings<ring_tag, ring_type> per_ring; - per_ring::apply(exterior_ring(polygon), id, map, midpoint); + per_ring::apply(exterior_ring(polygon), id, ring_properties); typename interior_return_type<Polygon const>::type rings = interior_rings(polygon); @@ -122,7 +133,7 @@ namespace dispatch it = boost::begin(rings); it != boost::end(rings); ++it) { id.ring_index++; - per_ring::apply(*it, id, map, midpoint); + per_ring::apply(*it, id, ring_properties); } } }; @@ -130,9 +141,9 @@ namespace dispatch template <typename Multi> struct select_rings<multi_polygon_tag, Multi> { - template <typename Geometry, typename Map> + template <typename Geometry, typename RingPropertyMap> static inline void apply(Multi const& multi, Geometry const& geometry, - ring_identifier id, Map& map, bool midpoint) + ring_identifier id, RingPropertyMap& ring_properties) { typedef typename boost::range_iterator < @@ -145,7 +156,7 @@ namespace dispatch for (iterator_type it = boost::begin(multi); it != boost::end(multi); ++it) { id.ring_index = -1; - per_polygon::apply(*it, geometry, id, map, midpoint); + per_polygon::apply(*it, geometry, id, ring_properties); id.multi_index++; } } @@ -161,14 +172,12 @@ struct decide template<> struct decide<overlay_union> { - template <typename Code> - static bool include(ring_identifier const& , Code const& code) + static bool include(ring_identifier const& , ring_turn_info const& info) { - return code.within_code * -1 == 1; + return info.has_uu_turn || ! info.within_other; } - template <typename Code> - static bool reversed(ring_identifier const& , Code const& ) + static bool reversed(ring_identifier const& , ring_turn_info const& ) { return false; } @@ -177,31 +186,43 @@ struct decide<overlay_union> template<> struct decide<overlay_difference> { - template <typename Code> - static bool include(ring_identifier const& id, Code const& code) + static bool include(ring_identifier const& id, ring_turn_info const& info) { - bool is_first = id.source_index == 0; - return code.within_code * -1 * (is_first ? 1 : -1) == 1; + // Difference: A - B + + // If this is A (source_index=0) and there is only a u/u turn, + // then the ring is inside B + // If this is B (source_index=1) and there is only a u/u turn, + // then the ring is NOT inside A + + // If this is A and the ring is within the other geometry, + // then we should NOT include it. + // If this is B then we SHOULD include it. + + bool const is_first = id.source_index == 0; + bool const within_other = info.within_other + || (is_first && info.has_uu_turn); + return is_first ? ! within_other : within_other; } - template <typename Code> - static bool reversed(ring_identifier const& id, Code const& code) + static bool reversed(ring_identifier const& id, ring_turn_info const& info) { - return include(id, code) && id.source_index == 1; + // Difference: A - B + // If this is B, and the ring is included, it should be reversed afterwards + + return id.source_index == 1 && include(id, info); } }; template<> struct decide<overlay_intersection> { - template <typename Code> - static bool include(ring_identifier const& , Code const& code) + static bool include(ring_identifier const& , ring_turn_info const& info) { - return code.within_code * 1 == 1; + return ! info.has_uu_turn && info.within_other; } - template <typename Code> - static bool reversed(ring_identifier const& , Code const& ) + static bool reversed(ring_identifier const& , ring_turn_info const& ) { return false; } @@ -211,61 +232,60 @@ struct decide<overlay_intersection> template < overlay_type OverlayType, - typename Geometry1, typename Geometry2, - typename IntersectionMap, typename SelectionMap + typename Geometry1, + typename Geometry2, + typename TurnInfoMap, + typename RingPropertyMap > -inline void update_selection_map(Geometry1 const& geometry1, +inline void update_ring_selection(Geometry1 const& geometry1, Geometry2 const& geometry2, - IntersectionMap const& intersection_map, - SelectionMap const& map_with_all, SelectionMap& selection_map) + TurnInfoMap const& turn_info_map, + RingPropertyMap const& all_ring_properties, + RingPropertyMap& selected_ring_properties) { - selection_map.clear(); + selected_ring_properties.clear(); - for (typename SelectionMap::const_iterator it = boost::begin(map_with_all); - it != boost::end(map_with_all); + for (typename RingPropertyMap::const_iterator it = boost::begin(all_ring_properties); + it != boost::end(all_ring_properties); ++it) { - /* - int union_code = it->second.within_code * -1; - bool is_first = it->first.source_index == 0; - std::cout << it->first << " " << it->second.area - << ": " << it->second.within_code - << " union: " << union_code - << " intersection: " << (it->second.within_code * 1) - << " G1-G2: " << (union_code * (is_first ? 1 : -1)) - << " G2-G1: " << (union_code * (is_first ? -1 : 1)) - << " -> " << (decide<OverlayType>::include(it->first, it->second) ? "INC" : "") - << decide<OverlayType>::reverse(it->first, it->second) - << std::endl; - */ - - bool found = intersection_map.find(it->first) != intersection_map.end(); - if (! found) + ring_identifier const& id = it->first; + + ring_turn_info info; + + typename TurnInfoMap::const_iterator tcit = turn_info_map.find(id); + if (tcit != turn_info_map.end()) { - ring_identifier const id = it->first; - typename SelectionMap::mapped_type properties = it->second; // Copy by value + info = tcit->second; // Copy by value + } - // Calculate the "within code" (previously this was done earlier but is - // much efficienter here - it can be even more efficient doing it all at once, - // using partition, TODO) - // So though this is less elegant than before, it avoids many unused point-in-poly calculations + if (info.has_normal_turn) + { + // There are normal turns on this ring. It should be traversed, we + // don't include the original ring + continue; + } + + if (! info.has_uu_turn) + { + // Check if the ring is within the other geometry, by taking + // a point lying on the ring switch(id.source_index) { case 0 : - properties.within_code - = geometry::within(properties.point, geometry2) ? 1 : -1; + info.within_other = geometry::within(it->second.point, geometry2); break; case 1 : - properties.within_code - = geometry::within(properties.point, geometry1) ? 1 : -1; + info.within_other = geometry::within(it->second.point, geometry1); break; } + } - if (decide<OverlayType>::include(id, properties)) - { - properties.reversed = decide<OverlayType>::reversed(id, properties); - selection_map[id] = properties; - } + if (decide<OverlayType>::include(id, info)) + { + typename RingPropertyMap::mapped_type properties = it->second; // Copy by value + properties.reversed = decide<OverlayType>::reversed(id, info); + selected_ring_properties[id] = properties; } } } @@ -277,44 +297,47 @@ inline void update_selection_map(Geometry1 const& geometry1, template < overlay_type OverlayType, - typename Geometry1, typename Geometry2, - typename IntersectionMap, typename SelectionMap + typename Geometry1, + typename Geometry2, + typename RingTurnInfoMap, + typename RingPropertyMap > inline void select_rings(Geometry1 const& geometry1, Geometry2 const& geometry2, - IntersectionMap const& intersection_map, - SelectionMap& selection_map, bool midpoint) + RingTurnInfoMap const& turn_info_per_ring, + RingPropertyMap& selected_ring_properties) { typedef typename geometry::tag<Geometry1>::type tag1; typedef typename geometry::tag<Geometry2>::type tag2; - SelectionMap map_with_all; + RingPropertyMap all_ring_properties; dispatch::select_rings<tag1, Geometry1>::apply(geometry1, geometry2, - ring_identifier(0, -1, -1), map_with_all, midpoint); + ring_identifier(0, -1, -1), all_ring_properties); dispatch::select_rings<tag2, Geometry2>::apply(geometry2, geometry1, - ring_identifier(1, -1, -1), map_with_all, midpoint); + ring_identifier(1, -1, -1), all_ring_properties); - update_selection_map<OverlayType>(geometry1, geometry2, intersection_map, - map_with_all, selection_map); + update_ring_selection<OverlayType>(geometry1, geometry2, turn_info_per_ring, + all_ring_properties, selected_ring_properties); } template < overlay_type OverlayType, typename Geometry, - typename IntersectionMap, typename SelectionMap + typename RingTurnInfoMap, + typename RingPropertyMap > inline void select_rings(Geometry const& geometry, - IntersectionMap const& intersection_map, - SelectionMap& selection_map, bool midpoint) + RingTurnInfoMap const& turn_info_per_ring, + RingPropertyMap& selected_ring_properties) { typedef typename geometry::tag<Geometry>::type tag; - SelectionMap map_with_all; + RingPropertyMap all_ring_properties; dispatch::select_rings<tag, Geometry>::apply(geometry, - ring_identifier(0, -1, -1), map_with_all, midpoint); + ring_identifier(0, -1, -1), all_ring_properties); - update_selection_map<OverlayType>(geometry, geometry, intersection_map, - map_with_all, selection_map); + update_ring_selection<OverlayType>(geometry, geometry, turn_info_per_ring, + all_ring_properties, selected_ring_properties); } |