summaryrefslogtreecommitdiff
path: root/boost/geometry/algorithms/detail/overlay/overlay.hpp
diff options
context:
space:
mode:
authorDongHun Kwak <dh0128.kwak@samsung.com>2017-09-13 11:24:46 +0900
committerDongHun Kwak <dh0128.kwak@samsung.com>2017-09-13 11:25:39 +0900
commit4fadd968fa12130524c8380f33fcfe25d4de79e5 (patch)
treefd26a490cd15388d42fc6652b3c5c13012e7f93e /boost/geometry/algorithms/detail/overlay/overlay.hpp
parentb5c87084afaef42b2d058f68091be31988a6a874 (diff)
downloadboost-4fadd968fa12130524c8380f33fcfe25d4de79e5.tar.gz
boost-4fadd968fa12130524c8380f33fcfe25d4de79e5.tar.bz2
boost-4fadd968fa12130524c8380f33fcfe25d4de79e5.zip
Imported Upstream version 1.65.0upstream/1.65.0
Change-Id: Icf8400b375482cb11bcf77440a6934ba360d6ba4 Signed-off-by: DongHun Kwak <dh0128.kwak@samsung.com>
Diffstat (limited to 'boost/geometry/algorithms/detail/overlay/overlay.hpp')
-rw-r--r--boost/geometry/algorithms/detail/overlay/overlay.hpp134
1 files changed, 108 insertions, 26 deletions
diff --git a/boost/geometry/algorithms/detail/overlay/overlay.hpp b/boost/geometry/algorithms/detail/overlay/overlay.hpp
index f1af2f1949..10829abd4f 100644
--- a/boost/geometry/algorithms/detail/overlay/overlay.hpp
+++ b/boost/geometry/algorithms/detail/overlay/overlay.hpp
@@ -28,9 +28,11 @@
#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/is_self_turn.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>
+#include <boost/geometry/algorithms/detail/overlay/self_turn_points.hpp>
#include <boost/geometry/algorithms/detail/overlay/turn_info.hpp>
#include <boost/geometry/algorithms/detail/recalculate.hpp>
@@ -87,29 +89,58 @@ struct overlay_null_visitor
{}
};
-template <typename Turns, typename TurnInfoMap>
-inline void get_ring_turn_info(TurnInfoMap& turn_info_map, Turns const& turns)
+template
+<
+ overlay_type OverlayType,
+ typename TurnInfoMap,
+ typename Turns,
+ typename Clusters
+>
+inline void get_ring_turn_info(TurnInfoMap& turn_info_map, Turns const& turns, Clusters const& clusters)
{
typedef typename boost::range_value<Turns>::type turn_type;
typedef typename turn_type::container_type container_type;
+ static const operation_type target_operation
+ = operation_from_overlay<OverlayType>::value;
+ static const operation_type opposite_operation
+ = target_operation == operation_union ? operation_intersection : operation_union;
+
+ signed_size_type turn_index = 0;
for (typename boost::range_iterator<Turns const>::type
it = boost::begin(turns);
it != boost::end(turns);
- ++it)
+ ++it, turn_index++)
{
- typename boost::range_value<Turns>::type const& turn_info = *it;
-
- if (turn_info.discarded
- && ! turn_info.any_blocked()
- && ! turn_info.colocated)
+ typename boost::range_value<Turns>::type const& turn = *it;
+
+ bool const colocated_target = target_operation == operation_union
+ ? turn.colocated_uu : turn.colocated_ii;
+ bool const colocated_opp = target_operation == operation_union
+ ? turn.colocated_ii : turn.colocated_uu;
+ bool const both_opposite = turn.both(opposite_operation);
+
+ bool const traversed
+ = turn.operations[0].visited.finalized()
+ || turn.operations[0].visited.rejected()
+ || turn.operations[1].visited.finalized()
+ || turn.operations[1].visited.rejected()
+ || turn.both(operation_blocked)
+ || turn.combination(opposite_operation, operation_blocked);
+
+ bool is_closed = false;
+ if (turn.cluster_id >= 0 && target_operation == operation_union)
{
- continue;
+ typename Clusters::const_iterator mit = clusters.find(turn.cluster_id);
+ BOOST_ASSERT(mit != clusters.end());
+
+ cluster_info const& cinfo = mit->second;
+ is_closed = cinfo.open_count == 0;
}
for (typename boost::range_iterator<container_type const>::type
- op_it = boost::begin(turn_info.operations);
- op_it != boost::end(turn_info.operations);
+ op_it = boost::begin(turn.operations);
+ op_it != boost::end(turn.operations);
++op_it)
{
ring_identifier const ring_id
@@ -118,7 +149,34 @@ inline void get_ring_turn_info(TurnInfoMap& turn_info_map, Turns const& turns)
op_it->seg_id.multi_index,
op_it->seg_id.ring_index
);
- turn_info_map[ring_id].has_normal_turn = true;
+
+ if (traversed || is_closed || ! op_it->enriched.startable)
+ {
+ turn_info_map[ring_id].has_traversed_turn = true;
+ }
+ else if (both_opposite && colocated_target)
+ {
+ // For union: ii, colocated with a uu
+ // For example, two interior rings touch where two exterior rings also touch.
+ // The interior rings are not yet traversed, and should be taken from the input
+
+ // For intersection: uu, colocated with an ii
+ // unless it is two interior inner rings colocated with a uu
+
+ // So don't set has_traversed_turn here
+ }
+ else if (both_opposite && ! is_self_turn<OverlayType>(turn))
+ {
+ // For union, mark any ring with a ii turn as traversed
+ // For intersection, any uu - but not if it is a self-turn
+ turn_info_map[ring_id].has_traversed_turn = true;
+ }
+ else if (colocated_opp && ! colocated_target)
+ {
+ // For union, a turn colocated with ii and NOT with uu/ux
+ // For intersection v.v.
+ turn_info_map[ring_id].has_traversed_turn = true;
+ }
}
}
}
@@ -128,18 +186,27 @@ template
<
typename GeometryOut, overlay_type OverlayType, bool ReverseOut,
typename Geometry1, typename Geometry2,
- typename OutputIterator
+ typename OutputIterator, typename Strategy
>
inline OutputIterator return_if_one_input_is_empty(Geometry1 const& geometry1,
Geometry2 const& geometry2,
- OutputIterator out)
+ OutputIterator out, Strategy const& strategy)
{
typedef std::deque
<
typename geometry::ring_type<GeometryOut>::type
> ring_container_type;
- typedef ring_properties<typename geometry::point_type<Geometry1>::type> properties;
+ typedef typename geometry::point_type<Geometry1>::type point_type1;
+
+ typedef ring_properties
+ <
+ point_type1,
+ typename Strategy::template area_strategy
+ <
+ point_type1
+ >::type::return_type
+ > properties;
// Silence warning C4127: conditional expression is constant
#if defined(_MSC_VER)
@@ -164,9 +231,9 @@ inline OutputIterator return_if_one_input_is_empty(Geometry1 const& geometry1,
std::map<ring_identifier, ring_turn_info> empty;
std::map<ring_identifier, properties> all_of_one_of_them;
- select_rings<OverlayType>(geometry1, geometry2, empty, all_of_one_of_them);
+ select_rings<OverlayType>(geometry1, geometry2, empty, all_of_one_of_them, strategy);
ring_container_type rings;
- assign_parents(geometry1, geometry2, rings, all_of_one_of_them);
+ assign_parents(geometry1, geometry2, rings, all_of_one_of_them, strategy);
return add_rings<GeometryOut>(all_of_one_of_them, geometry1, geometry2, rings, out);
}
@@ -201,7 +268,7 @@ struct overlay
return return_if_one_input_is_empty
<
GeometryOut, OverlayType, ReverseOut
- >(geometry1, geometry2, out);
+ >(geometry1, geometry2, out, strategy);
}
typedef typename geometry::point_type<GeometryOut>::type point_type;
@@ -238,10 +305,20 @@ std::cout << "get turns" << std::endl;
visitor.visit_turns(1, turns);
+#ifdef BOOST_GEOMETRY_INCLUDE_SELF_TURNS
+ {
+ self_get_turn_points::self_turns<Reverse1, assign_null_policy>(geometry1,
+ strategy, robust_policy, turns, policy, 0);
+ self_get_turn_points::self_turns<Reverse2, assign_null_policy>(geometry2,
+ strategy, robust_policy, turns, policy, 1);
+ }
+#endif
+
+
#ifdef BOOST_GEOMETRY_DEBUG_ASSEMBLE
std::cout << "enrich" << std::endl;
#endif
- typename Strategy::side_strategy_type side_strategy;
+ typename Strategy::side_strategy_type side_strategy = strategy.get_side_strategy();
cluster_type clusters;
geometry::enrich_intersection_points<Reverse1, Reverse2, OverlayType>(turns,
@@ -271,33 +348,38 @@ std::cout << "traverse" << std::endl;
);
std::map<ring_identifier, ring_turn_info> turn_info_per_ring;
- get_ring_turn_info(turn_info_per_ring, turns);
+ get_ring_turn_info<OverlayType>(turn_info_per_ring, turns, clusters);
+
+ typedef typename Strategy::template area_strategy<point_type>::type area_strategy_type;
typedef ring_properties
- <
- typename geometry::point_type<GeometryOut>::type
- > properties;
+ <
+ point_type,
+ typename area_strategy_type::return_type
+ > properties;
// Select all rings which are NOT touched by any intersection point
std::map<ring_identifier, properties> selected_ring_properties;
select_rings<OverlayType>(geometry1, geometry2, turn_info_per_ring,
- selected_ring_properties);
+ selected_ring_properties, strategy);
// Add rings created during traversal
{
+ area_strategy_type const area_strategy = strategy.template get_area_strategy<point_type>();
+
ring_identifier id(2, 0, -1);
for (typename boost::range_iterator<ring_container_type>::type
it = boost::begin(rings);
it != boost::end(rings);
++it)
{
- selected_ring_properties[id] = properties(*it);
+ selected_ring_properties[id] = properties(*it, area_strategy);
selected_ring_properties[id].reversed = ReverseOut;
id.multi_index++;
}
}
- assign_parents(geometry1, geometry2, rings, selected_ring_properties);
+ assign_parents(geometry1, geometry2, rings, selected_ring_properties, strategy);
return add_rings<GeometryOut>(selected_ring_properties, geometry1, geometry2, rings, out);
}