Server : Apache/2.4.41 (Ubuntu) System : Linux absol.cf 5.4.0-198-generic #218-Ubuntu SMP Fri Sep 27 20:18:53 UTC 2024 x86_64 User : www-data ( 33) PHP Version : 7.4.33 Disable Function : pcntl_alarm,pcntl_fork,pcntl_waitpid,pcntl_wait,pcntl_wifexited,pcntl_wifstopped,pcntl_wifsignaled,pcntl_wifcontinued,pcntl_wexitstatus,pcntl_wtermsig,pcntl_wstopsig,pcntl_signal,pcntl_signal_get_handler,pcntl_signal_dispatch,pcntl_get_last_error,pcntl_strerror,pcntl_sigprocmask,pcntl_sigwaitinfo,pcntl_sigtimedwait,pcntl_exec,pcntl_getpriority,pcntl_setpriority,pcntl_async_signals,pcntl_unshare, Directory : /usr/include/boost/geometry/algorithms/detail/
Upload File :
Current File : //usr/include/boost/geometry/algorithms/detail/get_left_turns.hpp
// 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
Server : Apache/2.4.41 (Ubuntu)