diff options
Diffstat (limited to 'boost/geometry/algorithms/detail/overlay/handle_colocations.hpp')
| -rw-r--r-- | boost/geometry/algorithms/detail/overlay/handle_colocations.hpp | 466 |
1 files changed, 385 insertions, 81 deletions
diff --git a/boost/geometry/algorithms/detail/overlay/handle_colocations.hpp b/boost/geometry/algorithms/detail/overlay/handle_colocations.hpp index 6f332ddff2..ad75127fab 100644 --- a/boost/geometry/algorithms/detail/overlay/handle_colocations.hpp +++ b/boost/geometry/algorithms/detail/overlay/handle_colocations.hpp @@ -16,6 +16,7 @@ #include <boost/range.hpp> #include <boost/geometry/algorithms/detail/overlay/overlay_type.hpp> +#include <boost/geometry/algorithms/detail/overlay/sort_by_side.hpp> #include <boost/geometry/algorithms/detail/overlay/turn_info.hpp> #include <boost/geometry/algorithms/detail/ring_identifier.hpp> #include <boost/geometry/algorithms/detail/overlay/segment_identifier.hpp> @@ -34,6 +35,29 @@ namespace boost { namespace geometry namespace detail { namespace overlay { +template <typename SegmentRatio> +struct segment_fraction +{ + segment_identifier seg_id; + SegmentRatio fraction; + + segment_fraction(segment_identifier const& id, SegmentRatio const& fr) + : seg_id(id) + , fraction(fr) + {} + + segment_fraction() + {} + + bool operator<(segment_fraction<SegmentRatio> const& other) const + { + return seg_id == other.seg_id + ? fraction < other.fraction + : seg_id < other.seg_id; + } + +}; + struct turn_operation_index { turn_operation_index(signed_size_type ti = -1, @@ -43,22 +67,22 @@ struct turn_operation_index {} signed_size_type turn_index; - signed_size_type op_index; // basically only 0,1 + signed_size_type op_index; // only 0,1 }; -template <typename TurnPoints> +template <typename Turns> struct less_by_fraction_and_type { - inline less_by_fraction_and_type(TurnPoints const& turn_points) - : m_turns(turn_points) + inline less_by_fraction_and_type(Turns const& turns) + : m_turns(turns) { } inline bool operator()(turn_operation_index const& left, turn_operation_index const& right) const { - typedef typename boost::range_value<TurnPoints>::type turn_type; + typedef typename boost::range_value<Turns>::type turn_type; typedef typename turn_type::turn_operation_type turn_operation_type; turn_type const& left_turn = m_turns[left.turn_index]; @@ -74,6 +98,29 @@ struct less_by_fraction_and_type return left_op.fraction < right_op.fraction; } + // Order xx first - used to discard any following colocated turn + bool const left_both_xx = left_turn.both(operation_blocked); + bool const right_both_xx = right_turn.both(operation_blocked); + if (left_both_xx && ! right_both_xx) + { + return true; + } + if (! left_both_xx && right_both_xx) + { + return false; + } + + bool const left_both_uu = left_turn.both(operation_union); + bool const right_both_uu = right_turn.both(operation_union); + if (left_both_uu && ! right_both_uu) + { + return true; + } + if (! left_both_uu && right_both_uu) + { + return false; + } + turn_operation_type const& left_other_op = left_turn.operations[1 - left.op_index]; @@ -86,88 +133,219 @@ struct less_by_fraction_and_type } private: - TurnPoints const& m_turns; + Turns const& m_turns; }; -template <overlay_type OverlayType, typename TurnPoints, typename OperationVector> -inline void handle_colocation_cluster(TurnPoints& turn_points, - segment_identifier const& current_ring_seg_id, - OperationVector const& vec) +template <typename Operation, typename ClusterPerSegment> +inline signed_size_type get_cluster_id(Operation const& op, ClusterPerSegment const& cluster_per_segment) +{ + typedef typename ClusterPerSegment::key_type segment_fraction_type; + + segment_fraction_type seg_frac(op.seg_id, op.fraction); + typename ClusterPerSegment::const_iterator it + = cluster_per_segment.find(seg_frac); + + if (it == cluster_per_segment.end()) + { + return -1; + } + return it->second; +} + +template <typename Operation, typename ClusterPerSegment> +inline void add_cluster_id(Operation const& op, + ClusterPerSegment& cluster_per_segment, signed_size_type id) { - typedef typename boost::range_value<TurnPoints>::type turn_type; + typedef typename ClusterPerSegment::key_type segment_fraction_type; + + segment_fraction_type seg_frac(op.seg_id, op.fraction); + + cluster_per_segment[seg_frac] = id; +} + +template <typename Turn, typename ClusterPerSegment> +inline signed_size_type add_turn_to_cluster(Turn const& turn, + ClusterPerSegment& cluster_per_segment, signed_size_type& cluster_id) +{ + signed_size_type cid0 = get_cluster_id(turn.operations[0], cluster_per_segment); + signed_size_type cid1 = get_cluster_id(turn.operations[1], cluster_per_segment); + + if (cid0 == -1 && cid1 == -1) + { + ++cluster_id; + add_cluster_id(turn.operations[0], cluster_per_segment, cluster_id); + add_cluster_id(turn.operations[1], cluster_per_segment, cluster_id); + return cluster_id; + } + else if (cid0 == -1 && cid1 != -1) + { + add_cluster_id(turn.operations[0], cluster_per_segment, cid1); + return cid1; + } + else if (cid0 != -1 && cid1 == -1) + { + add_cluster_id(turn.operations[1], cluster_per_segment, cid0); + return cid0; + } + else if (cid0 == cid1) + { + // Both already added to same cluster, no action + return cid0; + } + + // Both operations.seg_id/fraction were already part of any cluster, and + // these clusters are not the same. Merge of two clusters is necessary + std::cout << " TODO: merge " << cid0 << " and " << cid1 << std::endl; + return cid0; +} + +template +< + bool Reverse1, bool Reverse2, + typename Turns, + typename ClusterPerSegment, + typename Operations, + typename Geometry1, + typename Geometry2 +> +inline void handle_colocation_cluster(Turns& turns, + signed_size_type& cluster_id, + ClusterPerSegment& cluster_per_segment, + Operations const& operations, + Geometry1 const& geometry1, Geometry2 const& geometry2) +{ + typedef typename boost::range_value<Turns>::type turn_type; typedef typename turn_type::turn_operation_type turn_operation_type; - std::vector<turn_operation_index>::const_iterator vit = vec.begin(); + std::vector<turn_operation_index>::const_iterator vit = operations.begin(); - turn_type cluster_turn = turn_points[vit->turn_index]; - turn_operation_type cluster_op - = cluster_turn.operations[vit->op_index]; - segment_identifier cluster_other_id - = cluster_turn.operations[1 - vit->op_index].seg_id; - bool const discard_colocated - = cluster_turn.both(operation_union) - || cluster_turn.combination(operation_blocked, operation_union); + turn_operation_index ref_toi = *vit; + signed_size_type ref_id = -1; - for (++vit; vit != vec.end(); ++vit) + for (++vit; vit != operations.end(); ++vit) { + turn_type& ref_turn = turns[ref_toi.turn_index]; + turn_operation_type const& ref_op + = ref_turn.operations[ref_toi.op_index]; + turn_operation_index const& toi = *vit; - turn_type& turn = turn_points[toi.turn_index]; + turn_type& turn = turns[toi.turn_index]; turn_operation_type const& op = turn.operations[toi.op_index]; - segment_identifier const& other_id - = turn.operations[1 - toi.op_index].seg_id; - if (cluster_op.fraction == op.fraction) + BOOST_ASSERT(ref_op.seg_id == op.seg_id); + + if (ref_op.fraction == op.fraction) { - // Two turns of current ring with same source are colocated, - // one is from exterior ring, one from interior ring - bool const colocated_ext_int - = cluster_other_id.multi_index == other_id.multi_index - && cluster_other_id.ring_index == -1 - && other_id.ring_index >= 0; - - // Turn of current interior ring with other interior ring - bool const touch_int_int - = current_ring_seg_id.ring_index >= 0 - && other_id.ring_index >= 0; - - if (discard_colocated && colocated_ext_int) + turn_operation_type const& other_op = turn.operations[1 - toi.op_index]; + + if (ref_id == -1) { - // If the two turns on this same segment are a - // colocation with two different segments on the - // other geometry, of the same polygon but with - // the outer (u/u or u/x) and the inner ring (non u/u), - // that turn with inner ring should be discarded - turn.discarded = true; - turn.colocated = true; + ref_id = add_turn_to_cluster(ref_turn, cluster_per_segment, cluster_id); } - else if (cluster_turn.colocated - && touch_int_int - && turn.both(operation_intersection)) + BOOST_ASSERT(ref_id != -1); + + // ref_turn (both operations) are already added to cluster, + // so also "op" is already added to cluster, + // We only need to add other_op + signed_size_type id = get_cluster_id(other_op, cluster_per_segment); + if (id != -1 && id != ref_id) { - // Two holes touch each other at a point where the - // exterior ring also touches - turn.discarded = true; - turn.colocated = true; } - else if (OverlayType == overlay_difference - && turn.both(operation_intersection) - && colocated_ext_int) + else if (id == -1) + { + // Add to same cluster + add_cluster_id(other_op, cluster_per_segment, ref_id); + id = ref_id; + } + + // In case of colocated xx turns, all other turns may NOT be + // followed at all. xx cannot be discarded (otherwise colocated + // turns are followed). + if (ref_turn.both(operation_blocked)) { - // For difference (polygon inside out) we need to - // discard i/i instead, in case of colocations turn.discarded = true; - turn.colocated = true; + // We can either set or not set colocated because it is not effective on blocked turns } } else { // Not on same fraction on this segment - // assign for next potential cluster - cluster_turn = turn; - cluster_op = op; - cluster_other_id = other_id; + // assign for next + ref_toi = toi; + ref_id = -1; } + } +} + +template +< + typename Turns, + typename Clusters, + typename ClusterPerSegment +> +inline void assign_cluster_to_turns(Turns& turns, + Clusters& clusters, + ClusterPerSegment const& cluster_per_segment) +{ + typedef typename boost::range_value<Turns>::type turn_type; + typedef typename turn_type::turn_operation_type turn_operation_type; + typedef typename ClusterPerSegment::key_type segment_fraction_type; + signed_size_type turn_index = 0; + for (typename boost::range_iterator<Turns>::type it = turns.begin(); + it != turns.end(); ++it, ++turn_index) + { + turn_type& turn = *it; + + if (turn.discarded) + { + // They were processed (to create proper map) but will not be added + // This might leave a cluster with only 1 turn, which will be fixed + // afterwards + continue; + } + + for (int i = 0; i < 2; i++) + { + turn_operation_type const& op = turn.operations[i]; + segment_fraction_type seg_frac(op.seg_id, op.fraction); + typename ClusterPerSegment::const_iterator it = cluster_per_segment.find(seg_frac); + if (it != cluster_per_segment.end()) + { + if (turn.cluster_id != -1 + && turn.cluster_id != it->second) + { + std::cout << " CONFLICT " << std::endl; + } + turn.cluster_id = it->second; + clusters[turn.cluster_id].insert(turn_index); + } + } + } +} + +template +< + typename Turns, + typename Clusters +> +inline void remove_clusters(Turns& turns, Clusters& clusters) +{ + typename Clusters::iterator it = clusters.begin(); + while (it != clusters.end()) + { + // Hold iterator and increase. We can erase cit, this keeps the + // iterator valid (cf The standard associative-container erase idiom) + typename Clusters::iterator current_it = it; + ++it; + + std::set<signed_size_type> const& turn_indices = current_it->second; + if (turn_indices.size() == 1) + { + signed_size_type turn_index = *turn_indices.begin(); + turns[turn_index].cluster_id = -1; + clusters.erase(current_it); + } } } @@ -179,8 +357,16 @@ inline void handle_colocation_cluster(TurnPoints& turn_points, // This function can be extended to replace handle_tangencies: at each // colocation incoming and outgoing vectors should be inspected -template <overlay_type OverlayType, typename TurnPoints> -inline void handle_colocations(TurnPoints& turn_points) +template +< + bool Reverse1, bool Reverse2, + typename Turns, + typename Clusters, + typename Geometry1, + typename Geometry2 +> +inline bool handle_colocations(Turns& turns, Clusters& clusters, + Geometry1 const& geometry1, Geometry2 const& geometry2) { typedef std::map < @@ -195,9 +381,9 @@ inline void handle_colocations(TurnPoints& turn_points) map_type map; int index = 0; - for (typename boost::range_iterator<TurnPoints>::type - it = boost::begin(turn_points); - it != boost::end(turn_points); + for (typename boost::range_iterator<Turns>::type + it = boost::begin(turns); + it != boost::end(turns); ++it, ++index) { map[it->operations[0].seg_id].push_back(turn_operation_index(index, 0)); @@ -220,27 +406,43 @@ inline void handle_colocations(TurnPoints& turn_points) if (! colocations) { - return; + return false; } // Sort all vectors, per same segment - less_by_fraction_and_type<TurnPoints> less(turn_points); + less_by_fraction_and_type<Turns> less(turns); for (typename map_type::iterator it = map.begin(); it != map.end(); ++it) { std::sort(it->second.begin(), it->second.end(), less); } + typedef typename boost::range_value<Turns>::type turn_type; + typedef typename turn_type::segment_ratio_type segment_ratio_type; + + typedef std::map + < + segment_fraction<segment_ratio_type>, + signed_size_type + > cluster_per_segment_type; + + cluster_per_segment_type cluster_per_segment; + signed_size_type cluster_id = 0; + for (typename map_type::const_iterator it = map.begin(); it != map.end(); ++it) { - if (it->second.size() > 1) + if (it->second.size() > 1u) { - handle_colocation_cluster<OverlayType>(turn_points, - it->first, it->second); + handle_colocation_cluster<Reverse1, Reverse2>(turns, cluster_id, + cluster_per_segment, it->second, + geometry1, geometry2); } } + assign_cluster_to_turns(turns, clusters, cluster_per_segment); + remove_clusters(turns, clusters); + #if defined(BOOST_GEOMETRY_DEBUG_HANDLE_COLOCATIONS) std::cout << "*** Colocations " << map.size() << std::endl; for (typename map_type::const_iterator it = map.begin(); @@ -251,21 +453,123 @@ inline void handle_colocations(TurnPoints& turn_points) = it->second.begin(); vit != it->second.end(); ++vit) { turn_operation_index const& toi = *vit; - std::cout << geometry::wkt(turn_points[toi.turn_index].point) + std::cout << geometry::wkt(turns[toi.turn_index].point) << std::boolalpha - << " discarded=" << turn_points[toi.turn_index].discarded - << " colocated=" << turn_points[toi.turn_index].colocated - << " " << operation_char(turn_points[toi.turn_index].operations[0].operation) - << " " << turn_points[toi.turn_index].operations[0].seg_id - << " " << turn_points[toi.turn_index].operations[0].fraction - << " // " << operation_char(turn_points[toi.turn_index].operations[1].operation) - << " " << turn_points[toi.turn_index].operations[1].seg_id - << " " << turn_points[toi.turn_index].operations[1].fraction + << " discarded=" << turns[toi.turn_index].discarded + << " colocated=" << turns[toi.turn_index].colocated + << " " << operation_char(turns[toi.turn_index].operations[0].operation) + << " " << turns[toi.turn_index].operations[0].seg_id + << " " << turns[toi.turn_index].operations[0].fraction + << " // " << operation_char(turns[toi.turn_index].operations[1].operation) + << " " << turns[toi.turn_index].operations[1].seg_id + << " " << turns[toi.turn_index].operations[1].fraction << std::endl; } } #endif // DEBUG + return true; +} + + +struct is_turn_index +{ + is_turn_index(signed_size_type index) + : m_index(index) + {} + + template <typename Indexed> + inline bool operator()(Indexed const& indexed) const + { + // Indexed is a indexed_turn_operation<Operation> + return indexed.turn_index == m_index; + } + + std::size_t m_index; +}; + + +template +< + bool Reverse1, bool Reverse2, + typename Turns, + typename Clusters, + typename Geometry1, + typename Geometry2 +> +inline void assign_startable_in_clusters(Clusters& clusters, Turns& turns, + operation_type for_operation, + Geometry1 const& geometry1, Geometry2 const& geometry2) +{ + typedef typename boost::range_value<Turns>::type turn_type; + typedef typename turn_type::point_type point_type; + typedef typename turn_type::turn_operation_type turn_operation_type; + + // Define sorter, sorting counter-clockwise such that polygons are on the + // right side + typedef sort_by_side::side_sorter + < + Reverse1, Reverse2, point_type, std::less<int> + > sbs_type; + + for (typename Clusters::iterator mit = clusters.begin(); + mit != clusters.end(); ++mit) + { + std::set<signed_size_type> const& ids = mit->second; + if (ids.empty()) + { + continue; + } + + sbs_type sbs; + point_type turn_point; // should be all the same for all turns in cluster + + bool first = true; + for (typename std::set<signed_size_type>::const_iterator sit = ids.begin(); + sit != ids.end(); ++sit) + { + signed_size_type turn_index = *sit; + turn_type const& turn = turns[turn_index]; + if (first) + { + turn_point = turn.point; + } + for (int i = 0; i < 2; i++) + { + turn_operation_type const& op = turn.operations[i]; + sbs.add(op, turn_index, i, geometry1, geometry2, first); + first = false; + } + } + sbs.apply(turn_point); + + sbs.find_open(); + + // Unset the startable flag for all 'closed' spaces + for (std::size_t i = 0; i < sbs.m_ranked_points.size(); i++) + { + const typename sbs_type::rp& ranked = sbs.m_ranked_points[i]; + turn_type& turn = turns[ranked.turn_index]; + turn_operation_type& op = turn.operations[ranked.op_index]; + + if (ranked.index != sort_by_side::index_to) + { + continue; + } + + op.enriched.count_left = ranked.left_count; + op.enriched.count_right = ranked.right_count; + + if ((for_operation == operation_union + && ranked.left_count != 0) + || (for_operation == operation_intersection + && ranked.right_count != 2)) + { + op.enriched.startable = false; + } + } + + } } |