123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219 |
- // Boost.Geometry (aka GGL, Generic Geometry Library)
- // Copyright (c) 2012-2014 Barend Gehrels, Amsterdam, the Netherlands.
- // This file was modified by Oracle on 2017.
- // Modifications copyright (c) 2017, 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_OCCUPATION_INFO_HPP
- #define BOOST_GEOMETRY_ALGORITHMS_DETAIL_OCCUPATION_INFO_HPP
- #include <algorithm>
- #include <boost/range.hpp>
- #include <boost/geometry/core/assert.hpp>
- #include <boost/geometry/core/coordinate_type.hpp>
- #include <boost/geometry/core/point_type.hpp>
- #include <boost/geometry/policies/compare.hpp>
- #include <boost/geometry/iterators/closing_iterator.hpp>
- #include <boost/geometry/algorithms/detail/get_left_turns.hpp>
- namespace boost { namespace geometry
- {
- #ifndef DOXYGEN_NO_DETAIL
- namespace detail
- {
- template <typename Point, typename T>
- struct angle_info
- {
- typedef T angle_type;
- typedef Point point_type;
- segment_identifier seg_id;
- std::size_t turn_index;
- int operation_index;
- std::size_t cluster_index;
- Point intersection_point;
- Point point; // either incoming or outgoing point
- bool incoming;
- bool blocked;
- bool included;
- inline angle_info()
- : blocked(false)
- , included(false)
- {}
- };
- template <typename AngleInfo>
- class occupation_info
- {
- public :
- typedef std::vector<AngleInfo> collection_type;
- std::size_t count;
- inline occupation_info()
- : count(0)
- {}
- template <typename RobustPoint>
- inline void add(RobustPoint const& incoming_point,
- RobustPoint const& outgoing_point,
- RobustPoint const& intersection_point,
- std::size_t turn_index, int operation_index,
- segment_identifier const& seg_id)
- {
- geometry::equal_to<RobustPoint> comparator;
- if (comparator(incoming_point, intersection_point))
- {
- return;
- }
- if (comparator(outgoing_point, intersection_point))
- {
- return;
- }
- AngleInfo info;
- info.seg_id = seg_id;
- info.turn_index = turn_index;
- info.operation_index = operation_index;
- info.intersection_point = intersection_point;
- {
- info.point = incoming_point;
- info.incoming = true;
- m_angles.push_back(info);
- }
- {
- info.point = outgoing_point;
- info.incoming = false;
- m_angles.push_back(info);
- }
- }
- template <typename RobustPoint, typename Turns, typename SideStrategy>
- inline void get_left_turns(RobustPoint const& origin, Turns& turns,
- SideStrategy const& strategy)
- {
- typedef detail::left_turns::angle_less
- <
- typename AngleInfo::point_type,
- SideStrategy
- > angle_less;
- // Sort on angle
- std::sort(m_angles.begin(), m_angles.end(), angle_less(origin, strategy));
- // Group same-angled elements
- std::size_t cluster_size = detail::left_turns::assign_cluster_indices(m_angles, origin);
- // Block all turns on the right side of any turn
- detail::left_turns::block_turns(m_angles, cluster_size);
- detail::left_turns::get_left_turns(m_angles, turns);
- }
- #if defined(BOOST_GEOMETRY_BUFFER_ENLARGED_CLUSTERS)
- template <typename RobustPoint>
- inline bool has_rounding_issues(RobustPoint const& origin) const
- {
- return detail::left_turns::has_rounding_issues(angles, origin);
- }
- #endif
- private :
- collection_type m_angles; // each turn splitted in incoming/outgoing vectors
- };
- template<typename Pieces>
- inline void move_index(Pieces const& pieces, signed_size_type& index, signed_size_type& piece_index, int direction)
- {
- BOOST_GEOMETRY_ASSERT(direction == 1 || direction == -1);
- BOOST_GEOMETRY_ASSERT(
- piece_index >= 0
- && piece_index < static_cast<signed_size_type>(boost::size(pieces)) );
- BOOST_GEOMETRY_ASSERT(
- index >= 0
- && index < static_cast<signed_size_type>(boost::size(pieces[piece_index].robust_ring)));
- // NOTE: both index and piece_index must be in valid range
- // this means that then they could be of type std::size_t
- // if the code below was refactored
- index += direction;
- if (direction == -1 && index < 0)
- {
- piece_index--;
- if (piece_index < 0)
- {
- piece_index = boost::size(pieces) - 1;
- }
- index = boost::size(pieces[piece_index].robust_ring) - 1;
- }
- if (direction == 1
- && index >= static_cast<signed_size_type>(boost::size(pieces[piece_index].robust_ring)))
- {
- piece_index++;
- if (piece_index >= static_cast<signed_size_type>(boost::size(pieces)))
- {
- piece_index = 0;
- }
- index = 0;
- }
- }
- template
- <
- typename RobustPoint,
- typename Turn,
- typename Pieces,
- typename Info
- >
- inline void add_incoming_and_outgoing_angles(
- RobustPoint const& intersection_point, // rescaled
- Turn const& turn,
- Pieces const& pieces, // using rescaled offsets of it
- int operation_index,
- segment_identifier seg_id,
- Info& info)
- {
- segment_identifier real_seg_id = seg_id;
- geometry::equal_to<RobustPoint> comparator;
- // Move backward and forward
- RobustPoint direction_points[2];
- for (int i = 0; i < 2; i++)
- {
- signed_size_type index = turn.operations[operation_index].index_in_robust_ring;
- signed_size_type piece_index = turn.operations[operation_index].piece_index;
- while(comparator(pieces[piece_index].robust_ring[index], intersection_point))
- {
- move_index(pieces, index, piece_index, i == 0 ? -1 : 1);
- }
- direction_points[i] = pieces[piece_index].robust_ring[index];
- }
- info.add(direction_points[0], direction_points[1], intersection_point,
- turn.turn_index, operation_index, real_seg_id);
- }
- } // namespace detail
- #endif // DOXYGEN_NO_DETAIL
- }} // namespace boost::geometry
- #endif // BOOST_GEOMETRY_ALGORITHMS_DETAIL_OCCUPATION_INFO_HPP
|