diff options
Diffstat (limited to 'boost/geometry/algorithms/detail/get_left_turns.hpp')
| -rw-r--r-- | boost/geometry/algorithms/detail/get_left_turns.hpp | 487 |
1 files changed, 218 insertions, 269 deletions
diff --git a/boost/geometry/algorithms/detail/get_left_turns.hpp b/boost/geometry/algorithms/detail/get_left_turns.hpp index 62f0f7f0f4..0fd243d8e3 100644 --- a/boost/geometry/algorithms/detail/get_left_turns.hpp +++ b/boost/geometry/algorithms/detail/get_left_turns.hpp @@ -1,6 +1,6 @@ // Boost.Geometry (aka GGL, Generic Geometry Library) -// Copyright (c) 2012 Barend Gehrels, Amsterdam, the Netherlands. +// Copyright (c) 2012-2014 Barend Gehrels, Amsterdam, the Netherlands. // Use, modification and distribution is subject to the Boost Software License, // Version 1.0. (See accompanying file LICENSE_1_0.txt or copy at @@ -9,7 +9,12 @@ #ifndef BOOST_GEOMETRY_ALGORITHMS_DETAIL_GET_LEFT_TURNS_HPP #define BOOST_GEOMETRY_ALGORITHMS_DETAIL_GET_LEFT_TURNS_HPP +#include <boost/geometry/arithmetic/arithmetic.hpp> +#include <boost/geometry/algorithms/detail/overlay/segment_identifier.hpp> +#include <boost/geometry/algorithms/detail/overlay/turn_info.hpp> +#include <boost/geometry/iterators/closing_iterator.hpp> #include <boost/geometry/iterators/ever_circling_iterator.hpp> +#include <boost/geometry/strategies/side.hpp> namespace boost { namespace geometry { @@ -21,342 +26,286 @@ namespace detail // TODO: move this to /util/ template <typename T> -static inline std::pair<T, T> ordered_pair(T const& first, T const& second) +inline std::pair<T, T> ordered_pair(T const& first, T const& second) { return first < second ? std::make_pair(first, second) : std::make_pair(second, first); } -template <typename AngleInfo> -inline void debug_left_turn(AngleInfo const& ai, AngleInfo const& previous) +namespace left_turns { -#ifdef BOOST_GEOMETRY_DEBUG_BUFFER_OCCUPATION - std::cout << "Angle: " << (ai.incoming ? "i" : "o") - << " " << si(ai.seg_id) - << " " << (math::r2d * (ai.angle) ) - << " turn: " << ai.turn_index << "[" << ai.operation_index << "]" - ; - - if (ai.turn_index != previous.turn_index - || ai.operation_index != previous.operation_index) - { - std::cout << " diff: " << math::r2d * math::abs(previous.angle - ai.angle); - } - std::cout << std::endl; -#endif -} - -template <typename AngleInfo> -inline void debug_left_turn(std::string const& caption, AngleInfo const& ai, AngleInfo const& previous, - int code = -99, int code2 = -99, int code3 = -99, int code4 = -99) -{ -#ifdef BOOST_GEOMETRY_DEBUG_BUFFER_OCCUPATION - std::cout << " " << caption - << " turn: " << ai.turn_index << "[" << ai.operation_index << "]" - << " " << si(ai.seg_id) - << " " << (ai.incoming ? "i" : "o") - << " " << (math::r2d * (ai.angle) ) - << " turn: " << previous.turn_index << "[" << previous.operation_index << "]" - << " " << si(previous.seg_id) - << " " << (previous.incoming ? "i" : "o") - << " " << (math::r2d * (previous.angle) ) - ; - if (code != -99) - { - std::cout << " code: " << code << " , " << code2 << " , " << code3 << " , " << code4; - } - std::cout << std::endl; -#endif -} -template <typename Operation> -inline bool include_operation(Operation const& op, - segment_identifier const& outgoing_seg_id, - segment_identifier const& incoming_seg_id) +template <typename Vector> +inline int get_quadrant(Vector const& vector) { - return op.seg_id == outgoing_seg_id - && op.other_id == incoming_seg_id - && (op.operation == detail::overlay::operation_union - ||op.operation == detail::overlay::operation_continue) - ; + // Return quadrant as layouted in the code below: + // 3 | 0 + // ----- + // 2 | 1 + return geometry::get<1>(vector) >= 0 + ? (geometry::get<0>(vector) < 0 ? 3 : 0) + : (geometry::get<0>(vector) < 0 ? 2 : 1) + ; } -template <typename Turn> -inline bool process_include(segment_identifier const& outgoing_seg_id, segment_identifier const& incoming_seg_id, - int turn_index, Turn& turn, - std::set<int>& keep_indices, int priority) +template <typename Vector> +inline int squared_length(Vector const& vector) { - bool result = false; - for (int i = 0; i < 2; i++) - { - if (include_operation(turn.operations[i], outgoing_seg_id, incoming_seg_id)) - { - turn.operations[i].include_in_occupation_map = true; - if (priority > turn.priority) - { - turn.priority = priority; - } - keep_indices.insert(turn_index); - result = true; - } - } - return result; + return geometry::get<0>(vector) * geometry::get<0>(vector) + + geometry::get<1>(vector) * geometry::get<1>(vector) + ; } -template <typename AngleInfo, typename Turns, typename TurnSegmentIndices> -inline bool include_left_turn_of_all( - AngleInfo const& outgoing, AngleInfo const& incoming, - Turns& turns, TurnSegmentIndices const& turn_segment_indices, - std::set<int>& keep_indices, int priority) + +template <typename Point> +struct angle_less { - segment_identifier const& outgoing_seg_id = turns[outgoing.turn_index].operations[outgoing.operation_index].seg_id; - segment_identifier const& incoming_seg_id = turns[incoming.turn_index].operations[incoming.operation_index].seg_id; + typedef Point vector_type; + typedef typename strategy::side::services::default_strategy + < + typename cs_tag<Point>::type + >::type side_strategy_type; - if (outgoing.turn_index == incoming.turn_index) - { - return process_include(outgoing_seg_id, incoming_seg_id, outgoing.turn_index, turns[outgoing.turn_index], keep_indices, priority); - } + angle_less(Point const& origin) + : m_origin(origin) + {} - bool result = false; - std::pair<segment_identifier, segment_identifier> pair = ordered_pair(outgoing_seg_id, incoming_seg_id); - auto it = turn_segment_indices.find(pair); - if (it != turn_segment_indices.end()) + template <typename Angle> + inline bool operator()(Angle const& p, Angle const& q) const { - for (auto sit = it->second.begin(); sit != it->second.end(); ++sit) + // Vector origin -> p and origin -> q + vector_type pv = p.point; + vector_type qv = q.point; + geometry::subtract_point(pv, m_origin); + geometry::subtract_point(qv, m_origin); + + int const quadrant_p = get_quadrant(pv); + int const quadrant_q = get_quadrant(qv); + if (quadrant_p != quadrant_q) { - if (process_include(outgoing_seg_id, incoming_seg_id, *sit, turns[*sit], keep_indices, priority)) - { - result = true; - } + return quadrant_p < quadrant_q; } + // Same quadrant, check if p is located left of q + int const side = side_strategy_type::apply(m_origin, q.point, + p.point); + if (side != 0) + { + return side == 1; + } + // Collinear, check if one is incoming, incoming angles come first + if (p.incoming != q.incoming) + { + return int(p.incoming) < int(q.incoming); + } + // Same quadrant/side/direction, return longest first + // TODO: maybe not necessary, decide this + int const length_p = squared_length(pv); + int const length_q = squared_length(qv); + if (length_p != length_q) + { + return squared_length(pv) > squared_length(qv); + } + // They are still the same. Just compare on seg_id + return p.seg_id < q.seg_id; } - return result; -} -template <std::size_t Index, typename Turn> -inline bool corresponds(Turn const& turn, segment_identifier const& seg_id) +private: + Point m_origin; +}; + +template <typename Point> +struct angle_equal_to { - return turn.operations[Index].operation == detail::overlay::operation_union - && turn.operations[Index].seg_id == seg_id; -} + typedef Point vector_type; + typedef typename strategy::side::services::default_strategy + < + typename cs_tag<Point>::type + >::type side_strategy_type; + inline angle_equal_to(Point const& origin) + : m_origin(origin) + {} -template <typename Turns, typename TurnSegmentIndices> -inline bool prefer_by_other(Turns const& turns, - TurnSegmentIndices const& turn_segment_indices, - std::set<int>& indices) -{ - std::map<segment_identifier, int> map; - for (auto sit = indices.begin(); sit != indices.end(); ++sit) + template <typename Angle> + inline bool operator()(Angle const& p, Angle const& q) const { - map[turns[*sit].operations[0].seg_id]++; - map[turns[*sit].operations[1].seg_id]++; - } + // Vector origin -> p and origin -> q + vector_type pv = p.point; + vector_type qv = q.point; + geometry::subtract_point(pv, m_origin); + geometry::subtract_point(qv, m_origin); - std::set<segment_identifier> segment_occuring_once; - for (auto mit = map.begin(); mit != map.end(); ++mit) - { - if (mit->second == 1) + if (get_quadrant(pv) != get_quadrant(qv)) { - segment_occuring_once.insert(mit->first); + return false; } -#ifdef BOOST_GEOMETRY_DEBUG_BUFFER_PREFER - std::cout << si(mit->first) << " " << mit->second << std::endl; -#endif + // Same quadrant, check if p/q are collinear + int const side = side_strategy_type::apply(m_origin, q.point, + p.point); + return side == 0; } - if (segment_occuring_once.size() == 2) - { - // Try to find within all turns a turn with these two segments +private: + Point m_origin; +}; - std::set<segment_identifier>::const_iterator soo_it = segment_occuring_once.begin(); - segment_identifier front = *soo_it; - soo_it++; - segment_identifier back = *soo_it; +template <typename AngleCollection, typename Turns> +inline void get_left_turns(AngleCollection const& sorted_angles, + Turns& turns) +{ + std::set<int> good_incoming; + std::set<int> good_outgoing; - std::pair<segment_identifier, segment_identifier> pair = ordered_pair(front, back); - auto it = turn_segment_indices.find(pair); - if (it != turn_segment_indices.end()) + for (typename boost::range_iterator<AngleCollection const>::type it = + sorted_angles.begin(); it != sorted_angles.end(); ++it) + { + if (!it->blocked) { - // debug_turns_by_indices("Found", it->second); - // Check which is the union/continue - segment_identifier good; - for (auto sit = it->second.begin(); sit != it->second.end(); ++sit) + if (it->incoming) { - if (turns[*sit].operations[0].operation == detail::overlay::operation_union) - { - good = turns[*sit].operations[0].seg_id; - } - else if (turns[*sit].operations[1].operation == detail::overlay::operation_union) - { - good = turns[*sit].operations[1].seg_id; - } + good_incoming.insert(it->turn_index); } - -#ifdef BOOST_GEOMETRY_DEBUG_BUFFER_PREFER - std::cout << "Good: " << si(good) << std::endl; -#endif - - // Find in indexes-to-keep this segment with the union. Discard the other one - std::set<int> ok_indices; - for (auto sit = indices.begin(); sit != indices.end(); ++sit) + else { - if (corresponds<0>(turns[*sit], good) || corresponds<1>(turns[*sit], good)) - { - ok_indices.insert(*sit); - } - } - if (ok_indices.size() > 0 && ok_indices.size() < indices.size()) - { - indices = ok_indices; - std::cout << "^"; - return true; + good_outgoing.insert(it->turn_index); } } } - return false; -} -template <typename Turns> -inline void prefer_by_priority(Turns const& turns, std::set<int>& indices) -{ - // Find max prio - int min_prio = 1024, max_prio = 0; - for (auto sit = indices.begin(); sit != indices.end(); ++sit) - { - if (turns[*sit].priority > max_prio) - { - max_prio = turns[*sit].priority; - } - if (turns[*sit].priority < min_prio) - { - min_prio = turns[*sit].priority; - } - } - - if (min_prio == max_prio) + if (good_incoming.empty() || good_outgoing.empty()) { return; } - // Only keep indices with high prio - std::set<int> ok_indices; - for (auto sit = indices.begin(); sit != indices.end(); ++sit) + for (typename boost::range_iterator<AngleCollection const>::type it = + sorted_angles.begin(); it != sorted_angles.end(); ++it) { - if (turns[*sit].priority >= max_prio) + if (good_incoming.count(it->turn_index) == 0 + || good_outgoing.count(it->turn_index) == 0) { - ok_indices.insert(*sit); + turns[it->turn_index].remove_on_multi = true; } } - if (ok_indices.size() > 0 && ok_indices.size() < indices.size()) - { - indices = ok_indices; - std::cout << "%"; - } } -template <typename AngleInfo, typename Angles, typename Turns, typename TurnSegmentIndices> -inline void calculate_left_turns(Angles const& angles, - Turns& turns, TurnSegmentIndices const& turn_segment_indices, - std::set<int>& keep_indices) -{ - bool debug_indicate_size = false; - - typedef typename strategy::side::services::default_strategy - < - typename cs_tag<typename AngleInfo::point_type>::type - >::type side_strategy; - std::size_t i = 0; - std::size_t n = boost::size(angles); +//! Returns the number of clusters +template <typename Point, typename AngleCollection> +inline std::size_t assign_cluster_indices(AngleCollection& sorted, Point const& origin) +{ + // Assign same cluster_index for all turns in same direction + BOOST_ASSERT(boost::size(sorted) >= 4u); - typedef geometry::ever_circling_range_iterator<Angles const> circling_iterator; - circling_iterator cit(angles); + angle_equal_to<Point> comparator(origin); + typename boost::range_iterator<AngleCollection>::type it = sorted.begin(); - debug_left_turn(*cit, *cit); - for(circling_iterator prev = cit++; i < n; prev = cit++, i++) + std::size_t cluster_index = 0; + it->cluster_index = cluster_index; + typename boost::range_iterator<AngleCollection>::type previous = it++; + for (; it != sorted.end(); ++it) { - debug_left_turn(*cit, *prev); - - bool const include = ! geometry::math::equals(prev->angle, cit->angle) - && ! prev->incoming - && cit->incoming; - - if (include) + if (!comparator(*previous, *it)) { - // Go back to possibly include more same left outgoing angles: - // Because we check on side too we can take a large "epsilon" - circling_iterator back = prev - 1; - - typename AngleInfo::angle_type eps = 0.00001; - int b = 1; - for(std::size_t d = 0; - math::abs(prev->angle - back->angle) < eps - && ! back->incoming - && d < n; - d++) - { - --back; - ++b; - } + cluster_index++; + previous = it; + } + it->cluster_index = cluster_index; + } + return cluster_index + 1; +} - // Same but forward to possibly include more incoming angles - int f = 1; - circling_iterator forward = cit + 1; - for(std::size_t d = 0; - math::abs(cit->angle - forward->angle) < eps - && forward->incoming - && d < n; - d++) - { - ++forward; - ++f; - } +template <typename AngleCollection> +inline void block_turns(AngleCollection& sorted, std::size_t cluster_size) +{ + BOOST_ASSERT(boost::size(sorted) >= 4u && cluster_size > 0); -#ifdef BOOST_GEOMETRY_DEBUG_BUFFER_OCCUPATION - std::cout << "HANDLE " << b << "/" << f << " ANGLES" << std::endl; -#endif - for(circling_iterator bit = prev; bit != back; --bit) - { - int code = side_strategy::apply(bit->direction_point, prev->intersection_point, prev->direction_point); - int code2 = side_strategy::apply(prev->direction_point, bit->intersection_point, bit->direction_point); - for(circling_iterator fit = cit; fit != forward; ++fit) - { - int code3 = side_strategy::apply(fit->direction_point, cit->intersection_point, cit->direction_point); - int code4 = side_strategy::apply(cit->direction_point, fit->intersection_point, fit->direction_point); - - int priority = 2; - if (code == -1 && code2 == 1) - { - // This segment is lying right of the other one. - // Cannot ignore it (because of robustness, see a.o. #rt_p21 from unit test). - // But if we find more we can prefer later by priority - // (a.o. necessary for #rt_o2 from unit test) - priority = 1; - } - - bool included = include_left_turn_of_all(*bit, *fit, turns, turn_segment_indices, keep_indices, priority); - debug_left_turn(included ? "KEEP" : "SKIP", *fit, *bit, code, code2, code3, code4); - } - } - } + std::vector<std::pair<bool, bool> > directions; + for (std::size_t i = 0; i < cluster_size; i++) + { + directions.push_back(std::make_pair(false, false)); } - if (debug_indicate_size) + for (typename boost::range_iterator<AngleCollection const>::type it = sorted.begin(); + it != sorted.end(); ++it) { - std::cout << " size=" << keep_indices.size(); + if (it->incoming) + { + directions[it->cluster_index].first = true; + } + else + { + directions[it->cluster_index].second = true; + } } - if (keep_indices.size() >= 2) + for (typename boost::range_iterator<AngleCollection>::type it = sorted.begin(); + it != sorted.end(); ++it) { - prefer_by_other(turns, turn_segment_indices, keep_indices); + int cluster_index = it->cluster_index; + int previous_index = cluster_index - 1; + if (previous_index < 0) + { + previous_index = cluster_size - 1; + } + int next_index = cluster_index + 1; + if (next_index >= static_cast<int>(cluster_size)) + { + next_index = 0; + } + + if (directions[cluster_index].first + && directions[cluster_index].second) + { + it->blocked = true; + } + else if (!directions[cluster_index].first + && directions[cluster_index].second + && directions[previous_index].second) + { + // Only outgoing, previous was also outgoing: block this one + it->blocked = true; + } + else if (directions[cluster_index].first + && !directions[cluster_index].second + && !directions[previous_index].first + && directions[previous_index].second) + { + // Only incoming, previous was only outgoing: block this one + it->blocked = true; + } + else if (directions[cluster_index].first + && !directions[cluster_index].second + && directions[next_index].first + && !directions[next_index].second) + { + // Only incoming, next also incoming, block this one + it->blocked = true; + } } - if (keep_indices.size() >= 2) +} + +#if defined(BOOST_GEOMETRY_BUFFER_ENLARGED_CLUSTERS) +template <typename AngleCollection, typename Point> +inline bool has_rounding_issues(AngleCollection const& angles, Point const& origin) +{ + for (typename boost::range_iterator<AngleCollection const>::type it = + angles.begin(); it != angles.end(); ++it) { - prefer_by_priority(turns, keep_indices); + // Vector origin -> p and origin -> q + typedef Point vector_type; + vector_type v = it->point; + geometry::subtract_point(v, origin); + return geometry::math::abs(geometry::get<0>(v)) <= 1 + || geometry::math::abs(geometry::get<1>(v)) <= 1 + ; } + return false; } +#endif + + +} // namespace left_turns } // namespace detail #endif // DOXYGEN_NO_DETAIL |