123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315 |
- // Boost.Geometry (aka GGL, Generic Geometry Library)
- // Copyright (c) 2012-2014 Barend Gehrels, Amsterdam, the Netherlands.
- // This file was modified by Oracle on 2017, 2018.
- // Modifications copyright (c) 2017-2018, Oracle and/or its affiliates.
- // Contributed and/or modified by Adam Wulkiewicz, on behalf of Oracle
- // Use, modification and distribution is subject to the Boost Software License,
- // Version 1.0. (See accompanying file LICENSE_1_0.txt or copy at
- // http://www.boost.org/LICENSE_1_0.txt)
- #ifndef BOOST_GEOMETRY_ALGORITHMS_DETAIL_GET_LEFT_TURNS_HPP
- #define BOOST_GEOMETRY_ALGORITHMS_DETAIL_GET_LEFT_TURNS_HPP
- #include <set>
- #include <vector>
- #include <boost/geometry/core/assert.hpp>
- #include <boost/geometry/algorithms/detail/overlay/segment_identifier.hpp>
- #include <boost/geometry/algorithms/detail/overlay/turn_info.hpp>
- #include <boost/geometry/arithmetic/arithmetic.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
- {
- #ifndef DOXYGEN_NO_DETAIL
- namespace detail
- {
- // TODO: move this to /util/
- template <typename T>
- 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);
- }
- namespace left_turns
- {
- template <typename Vector>
- inline int get_quadrant(Vector const& vector)
- {
- // 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 Vector>
- inline int squared_length(Vector const& vector)
- {
- return geometry::get<0>(vector) * geometry::get<0>(vector)
- + geometry::get<1>(vector) * geometry::get<1>(vector)
- ;
- }
- template <typename Point, typename SideStrategy>
- struct angle_less
- {
- typedef Point vector_type;
- angle_less(Point const& origin, SideStrategy const& strategy)
- : m_origin(origin)
- , m_strategy(strategy)
- {}
- template <typename Angle>
- inline bool operator()(Angle const& p, Angle const& q) const
- {
- // 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)
- {
- return quadrant_p < quadrant_q;
- }
- // Same quadrant, check if p is located left of q
- int const side = m_strategy.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;
- }
- private:
- Point m_origin;
- SideStrategy m_strategy;
- };
- template <typename Point, typename SideStrategy>
- struct angle_equal_to
- {
- typedef Point vector_type;
-
- inline angle_equal_to(Point const& origin, SideStrategy const& strategy)
- : m_origin(origin)
- , m_strategy(strategy)
- {}
- template <typename Angle>
- inline bool operator()(Angle const& p, Angle const& q) const
- {
- // 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);
- if (get_quadrant(pv) != get_quadrant(qv))
- {
- return false;
- }
- // Same quadrant, check if p/q are collinear
- int const side = m_strategy.apply(m_origin, q.point, p.point);
- return side == 0;
- }
- private:
- Point m_origin;
- SideStrategy m_strategy;
- };
- template <typename AngleCollection, typename Turns>
- inline void get_left_turns(AngleCollection const& sorted_angles,
- Turns& turns)
- {
- std::set<std::size_t> good_incoming;
- std::set<std::size_t> good_outgoing;
- for (typename boost::range_iterator<AngleCollection const>::type it =
- sorted_angles.begin(); it != sorted_angles.end(); ++it)
- {
- if (!it->blocked)
- {
- if (it->incoming)
- {
- good_incoming.insert(it->turn_index);
- }
- else
- {
- good_outgoing.insert(it->turn_index);
- }
- }
- }
- if (good_incoming.empty() || good_outgoing.empty())
- {
- return;
- }
- for (typename boost::range_iterator<AngleCollection const>::type it =
- sorted_angles.begin(); it != sorted_angles.end(); ++it)
- {
- if (good_incoming.count(it->turn_index) == 0
- || good_outgoing.count(it->turn_index) == 0)
- {
- turns[it->turn_index].remove_on_multi = true;
- }
- }
- }
- //! Returns the number of clusters
- template <typename Point, typename AngleCollection, typename SideStrategy>
- inline std::size_t assign_cluster_indices(AngleCollection& sorted, Point const& origin,
- SideStrategy const& strategy)
- {
- // Assign same cluster_index for all turns in same direction
- BOOST_GEOMETRY_ASSERT(boost::size(sorted) >= 4u);
- angle_equal_to<Point, SideStrategy> comparator(origin, strategy);
- typename boost::range_iterator<AngleCollection>::type it = sorted.begin();
- std::size_t cluster_index = 0;
- it->cluster_index = cluster_index;
- typename boost::range_iterator<AngleCollection>::type previous = it++;
- for (; it != sorted.end(); ++it)
- {
- if (!comparator(*previous, *it))
- {
- cluster_index++;
- previous = it;
- }
- it->cluster_index = cluster_index;
- }
- return cluster_index + 1;
- }
- template <typename AngleCollection>
- inline void block_turns(AngleCollection& sorted, std::size_t cluster_size)
- {
- BOOST_GEOMETRY_ASSERT(boost::size(sorted) >= 4u && cluster_size > 0);
- 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));
- }
- for (typename boost::range_iterator<AngleCollection const>::type it = sorted.begin();
- it != sorted.end(); ++it)
- {
- if (it->incoming)
- {
- directions[it->cluster_index].first = true;
- }
- else
- {
- directions[it->cluster_index].second = true;
- }
- }
- for (typename boost::range_iterator<AngleCollection>::type it = sorted.begin();
- it != sorted.end(); ++it)
- {
- std::size_t const cluster_index = it->cluster_index;
- std::size_t const previous_index
- = cluster_index == 0 ? cluster_size - 1 : cluster_index - 1;
- std::size_t const next_index
- = cluster_index + 1 >= cluster_size ? 0 : cluster_index + 1;
- 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 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)
- {
- // 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
- }} // namespace boost::geometry
- #endif // BOOST_GEOMETRY_ALGORITHMS_DETAIL_GET_LEFT_TURNS_HPP
|