diff options
Diffstat (limited to 'boost/geometry/algorithms/detail/overlay/overlay.hpp')
| -rw-r--r-- | boost/geometry/algorithms/detail/overlay/overlay.hpp | 139 |
1 files changed, 98 insertions, 41 deletions
diff --git a/boost/geometry/algorithms/detail/overlay/overlay.hpp b/boost/geometry/algorithms/detail/overlay/overlay.hpp index 6eb0b8864c..c3ecaa0b01 100644 --- a/boost/geometry/algorithms/detail/overlay/overlay.hpp +++ b/boost/geometry/algorithms/detail/overlay/overlay.hpp @@ -26,6 +26,7 @@ #include <boost/geometry/algorithms/detail/overlay/enrich_intersection_points.hpp> #include <boost/geometry/algorithms/detail/overlay/enrichment_info.hpp> #include <boost/geometry/algorithms/detail/overlay/get_turns.hpp> +#include <boost/geometry/algorithms/detail/overlay/handle_touch.hpp> #include <boost/geometry/algorithms/detail/overlay/overlay_type.hpp> #include <boost/geometry/algorithms/detail/overlay/traverse.hpp> #include <boost/geometry/algorithms/detail/overlay/traversal_info.hpp> @@ -59,28 +60,50 @@ namespace detail { namespace overlay { -template <typename TurnPoints, typename TurnInfoMap> -inline void get_ring_turn_info(TurnInfoMap& turn_info_map, - TurnPoints const& turn_points) +//! Default visitor for overlay, doing nothing +struct overlay_null_visitor { - typedef typename boost::range_value<TurnPoints>::type turn_point_type; - typedef typename turn_point_type::container_type container_type; + void print(char const* ) {} - for (typename boost::range_iterator<TurnPoints const>::type - it = boost::begin(turn_points); - it != boost::end(turn_points); + template <typename Turns> + void print(char const* , Turns const& , int) {} + + template <typename Turns> + void print(char const* , Turns const& , int , int ) {} + + template <typename Turns> + void visit_turns(int , Turns const& ) {} + + template <typename Clusters, typename Turns> + void visit_clusters(Clusters const& , Turns const& ) {} + + template <typename Turns, typename Turn, typename Operation> + void visit_traverse(Turns const& , Turn const& , Operation const& , char const*) + {} + + template <typename Turns, typename Turn, typename Operation> + void visit_traverse_reject(Turns const& , Turn const& , Operation const& , traverse_error_type ) + {} +}; + +template <typename Turns, typename TurnInfoMap> +inline void get_ring_turn_info(TurnInfoMap& turn_info_map, Turns const& turns) +{ + typedef typename boost::range_value<Turns>::type turn_type; + typedef typename turn_type::container_type container_type; + + for (typename boost::range_iterator<Turns const>::type + it = boost::begin(turns); + it != boost::end(turns); ++it) { - typename boost::range_value<TurnPoints>::type const& turn_info = *it; - bool both_uu = turn_info.both(operation_union); - bool skip = (turn_info.discarded || both_uu) - && ! turn_info.any_blocked() - && ! turn_info.both(operation_intersection) - ; + typename boost::range_value<Turns>::type const& turn_info = *it; - if (! both_uu && turn_info.colocated) + if (turn_info.discarded + && ! turn_info.any_blocked() + && ! turn_info.colocated) { - skip = true; + continue; } for (typename boost::range_iterator<container_type const>::type @@ -88,21 +111,13 @@ inline void get_ring_turn_info(TurnInfoMap& turn_info_map, op_it != boost::end(turn_info.operations); ++op_it) { - ring_identifier ring_id + ring_identifier const ring_id ( op_it->seg_id.source_index, op_it->seg_id.multi_index, op_it->seg_id.ring_index ); - - if (! skip) - { - turn_info_map[ring_id].has_normal_turn = true; - } - else if (both_uu) - { - turn_info_map[ring_id].has_uu_turn = true; - } + turn_info_map[ring_id].has_normal_turn = true; } } } @@ -164,12 +179,13 @@ template > struct overlay { - template <typename RobustPolicy, typename OutputIterator, typename Strategy> + template <typename RobustPolicy, typename OutputIterator, typename Strategy, typename Visitor> static inline OutputIterator apply( Geometry1 const& geometry1, Geometry2 const& geometry2, RobustPolicy const& robust_policy, OutputIterator out, - Strategy const& ) + Strategy const& , + Visitor& visitor) { bool const is_empty1 = geometry::is_empty(geometry1); bool const is_empty2 = geometry::is_empty(geometry2); @@ -193,14 +209,23 @@ struct overlay point_type, typename geometry::segment_ratio_type<point_type, RobustPolicy>::type > turn_info; - typedef std::deque<turn_info> container_type; + typedef std::deque<turn_info> turn_container_type; typedef std::deque < typename geometry::ring_type<GeometryOut>::type > ring_container_type; - container_type turn_points; + // Define the clusters, mapping cluster_id -> turns + typedef std::map + < + signed_size_type, + std::set<signed_size_type> + > cluster_type; + + cluster_type clusters; + + turn_container_type turns; #ifdef BOOST_GEOMETRY_DEBUG_ASSEMBLE std::cout << "get turns" << std::endl; @@ -210,20 +235,42 @@ std::cout << "get turns" << std::endl; < Reverse1, Reverse2, detail::overlay::assign_null_policy - >(geometry1, geometry2, robust_policy, turn_points, policy); + >(geometry1, geometry2, robust_policy, turns, policy); + + visitor.visit_turns(1, turns); + + static const operation_type op_type + = OverlayType == overlay_union + ? geometry::detail::overlay::operation_union + : geometry::detail::overlay::operation_intersection; #ifdef BOOST_GEOMETRY_DEBUG_ASSEMBLE std::cout << "enrich" << std::endl; #endif typename Strategy::side_strategy_type side_strategy; - geometry::enrich_intersection_points<Reverse1, Reverse2, OverlayType>(turn_points, - OverlayType == overlay_union - ? geometry::detail::overlay::operation_union - : geometry::detail::overlay::operation_intersection, + geometry::enrich_intersection_points<Reverse1, Reverse2, OverlayType>(turns, + clusters, op_type, geometry1, geometry2, robust_policy, side_strategy); + visitor.visit_turns(2, turns); + + visitor.visit_clusters(clusters, turns); + + +#if 0 + // TODO: does not work always correctly, move to traverse and fix + if (op_type == geometry::detail::overlay::operation_union) + { + #ifdef BOOST_GEOMETRY_DEBUG_ASSEMBLE + std::cout << "handle_touch" << std::endl; + #endif + + handle_touch(op_type, turns, visitor); + } +#endif + #ifdef BOOST_GEOMETRY_DEBUG_ASSEMBLE std::cout << "traverse" << std::endl; #endif @@ -231,18 +278,17 @@ std::cout << "traverse" << std::endl; // Note that these rings are always in clockwise order, even in CCW polygons, // and are marked as "to be reversed" below ring_container_type rings; - traverse<Reverse1, Reverse2, Geometry1, Geometry2>::apply + traverse<Reverse1, Reverse2, Geometry1, Geometry2, op_type>::apply ( geometry1, geometry2, - OverlayType == overlay_union - ? geometry::detail::overlay::operation_union - : geometry::detail::overlay::operation_intersection, robust_policy, - turn_points, rings + turns, rings, + clusters, + visitor ); std::map<ring_identifier, ring_turn_info> turn_info_per_ring; - get_ring_turn_info(turn_info_per_ring, turn_points); + get_ring_turn_info(turn_info_per_ring, turns); typedef ring_properties < @@ -272,6 +318,17 @@ std::cout << "traverse" << std::endl; return add_rings<GeometryOut>(selected_ring_properties, geometry1, geometry2, rings, out); } + + template <typename RobustPolicy, typename OutputIterator, typename Strategy> + static inline OutputIterator apply( + Geometry1 const& geometry1, Geometry2 const& geometry2, + RobustPolicy const& robust_policy, + OutputIterator out, + Strategy const& strategy) + { + overlay_null_visitor visitor; + return apply(geometry1, geometry2, robust_policy, out, strategy, visitor); + } }; |