]>
Commit | Line | Data |
---|---|---|
7c673cae FG |
1 | // Boost.Geometry (aka GGL, Generic Geometry Library) |
2 | ||
3 | // Copyright (c) 2012-2014 Barend Gehrels, Amsterdam, the Netherlands. | |
4 | ||
5 | // Use, modification and distribution is subject to the Boost Software License, | |
6 | // Version 1.0. (See accompanying file LICENSE_1_0.txt or copy at | |
7 | // http://www.boost.org/LICENSE_1_0.txt) | |
8 | ||
9 | #ifndef BOOST_GEOMETRY_ALGORITHMS_DETAIL_OCCUPATION_INFO_HPP | |
10 | #define BOOST_GEOMETRY_ALGORITHMS_DETAIL_OCCUPATION_INFO_HPP | |
11 | ||
12 | #include <algorithm> | |
13 | #include <boost/range.hpp> | |
14 | ||
15 | #include <boost/geometry/core/assert.hpp> | |
16 | #include <boost/geometry/core/coordinate_type.hpp> | |
17 | #include <boost/geometry/core/point_type.hpp> | |
18 | ||
19 | #include <boost/geometry/policies/compare.hpp> | |
20 | #include <boost/geometry/iterators/closing_iterator.hpp> | |
21 | ||
22 | #include <boost/geometry/algorithms/detail/get_left_turns.hpp> | |
23 | ||
24 | ||
25 | namespace boost { namespace geometry | |
26 | { | |
27 | ||
28 | ||
29 | #ifndef DOXYGEN_NO_DETAIL | |
30 | namespace detail | |
31 | { | |
32 | ||
33 | template <typename Point, typename T> | |
34 | struct angle_info | |
35 | { | |
36 | typedef T angle_type; | |
37 | typedef Point point_type; | |
38 | ||
39 | segment_identifier seg_id; | |
40 | std::size_t turn_index; | |
41 | int operation_index; | |
42 | std::size_t cluster_index; | |
43 | Point intersection_point; | |
44 | Point point; // either incoming or outgoing point | |
45 | bool incoming; | |
46 | bool blocked; | |
47 | bool included; | |
48 | ||
49 | inline angle_info() | |
50 | : blocked(false) | |
51 | , included(false) | |
52 | {} | |
53 | }; | |
54 | ||
55 | template <typename AngleInfo> | |
56 | class occupation_info | |
57 | { | |
58 | public : | |
59 | typedef std::vector<AngleInfo> collection_type; | |
60 | ||
61 | std::size_t count; | |
62 | ||
63 | inline occupation_info() | |
64 | : count(0) | |
65 | {} | |
66 | ||
67 | template <typename RobustPoint> | |
68 | inline void add(RobustPoint const& incoming_point, | |
69 | RobustPoint const& outgoing_point, | |
70 | RobustPoint const& intersection_point, | |
71 | std::size_t turn_index, int operation_index, | |
72 | segment_identifier const& seg_id) | |
73 | { | |
74 | geometry::equal_to<RobustPoint> comparator; | |
75 | if (comparator(incoming_point, intersection_point)) | |
76 | { | |
77 | return; | |
78 | } | |
79 | if (comparator(outgoing_point, intersection_point)) | |
80 | { | |
81 | return; | |
82 | } | |
83 | ||
84 | AngleInfo info; | |
85 | info.seg_id = seg_id; | |
86 | info.turn_index = turn_index; | |
87 | info.operation_index = operation_index; | |
88 | info.intersection_point = intersection_point; | |
89 | ||
90 | { | |
91 | info.point = incoming_point; | |
92 | info.incoming = true; | |
93 | m_angles.push_back(info); | |
94 | } | |
95 | { | |
96 | info.point = outgoing_point; | |
97 | info.incoming = false; | |
98 | m_angles.push_back(info); | |
99 | } | |
100 | } | |
101 | ||
102 | template <typename RobustPoint, typename Turns> | |
103 | inline void get_left_turns(RobustPoint const& origin, Turns& turns) | |
104 | { | |
105 | // Sort on angle | |
106 | std::sort(m_angles.begin(), m_angles.end(), | |
107 | detail::left_turns::angle_less<typename AngleInfo::point_type>(origin)); | |
108 | ||
109 | // Group same-angled elements | |
110 | std::size_t cluster_size = detail::left_turns::assign_cluster_indices(m_angles, origin); | |
111 | // Block all turns on the right side of any turn | |
112 | detail::left_turns::block_turns(m_angles, cluster_size); | |
113 | detail::left_turns::get_left_turns(m_angles, turns); | |
114 | } | |
115 | ||
116 | #if defined(BOOST_GEOMETRY_BUFFER_ENLARGED_CLUSTERS) | |
117 | template <typename RobustPoint> | |
118 | inline bool has_rounding_issues(RobustPoint const& origin) const | |
119 | { | |
120 | return detail::left_turns::has_rounding_issues(angles, origin); | |
121 | } | |
122 | #endif | |
123 | ||
124 | private : | |
125 | collection_type m_angles; // each turn splitted in incoming/outgoing vectors | |
126 | }; | |
127 | ||
128 | template<typename Pieces> | |
129 | inline void move_index(Pieces const& pieces, signed_size_type& index, signed_size_type& piece_index, int direction) | |
130 | { | |
131 | BOOST_GEOMETRY_ASSERT(direction == 1 || direction == -1); | |
132 | BOOST_GEOMETRY_ASSERT( | |
133 | piece_index >= 0 | |
134 | && piece_index < static_cast<signed_size_type>(boost::size(pieces)) ); | |
135 | BOOST_GEOMETRY_ASSERT( | |
136 | index >= 0 | |
137 | && index < static_cast<signed_size_type>(boost::size(pieces[piece_index].robust_ring))); | |
138 | ||
139 | // NOTE: both index and piece_index must be in valid range | |
140 | // this means that then they could be of type std::size_t | |
141 | // if the code below was refactored | |
142 | ||
143 | index += direction; | |
144 | if (direction == -1 && index < 0) | |
145 | { | |
146 | piece_index--; | |
147 | if (piece_index < 0) | |
148 | { | |
149 | piece_index = boost::size(pieces) - 1; | |
150 | } | |
151 | index = boost::size(pieces[piece_index].robust_ring) - 1; | |
152 | } | |
153 | if (direction == 1 | |
154 | && index >= static_cast<signed_size_type>(boost::size(pieces[piece_index].robust_ring))) | |
155 | { | |
156 | piece_index++; | |
157 | if (piece_index >= static_cast<signed_size_type>(boost::size(pieces))) | |
158 | { | |
159 | piece_index = 0; | |
160 | } | |
161 | index = 0; | |
162 | } | |
163 | } | |
164 | ||
165 | ||
166 | template | |
167 | < | |
168 | typename RobustPoint, | |
169 | typename Turn, | |
170 | typename Pieces, | |
171 | typename Info | |
172 | > | |
173 | inline void add_incoming_and_outgoing_angles( | |
174 | RobustPoint const& intersection_point, // rescaled | |
175 | Turn const& turn, | |
176 | Pieces const& pieces, // using rescaled offsets of it | |
177 | int operation_index, | |
178 | segment_identifier seg_id, | |
179 | Info& info) | |
180 | { | |
181 | segment_identifier real_seg_id = seg_id; | |
182 | geometry::equal_to<RobustPoint> comparator; | |
183 | ||
184 | // Move backward and forward | |
185 | RobustPoint direction_points[2]; | |
186 | for (int i = 0; i < 2; i++) | |
187 | { | |
188 | signed_size_type index = turn.operations[operation_index].index_in_robust_ring; | |
189 | signed_size_type piece_index = turn.operations[operation_index].piece_index; | |
190 | while(comparator(pieces[piece_index].robust_ring[index], intersection_point)) | |
191 | { | |
192 | move_index(pieces, index, piece_index, i == 0 ? -1 : 1); | |
193 | } | |
194 | direction_points[i] = pieces[piece_index].robust_ring[index]; | |
195 | } | |
196 | ||
197 | info.add(direction_points[0], direction_points[1], intersection_point, | |
198 | turn.turn_index, operation_index, real_seg_id); | |
199 | } | |
200 | ||
201 | ||
202 | } // namespace detail | |
203 | #endif // DOXYGEN_NO_DETAIL | |
204 | ||
205 | ||
206 | }} // namespace boost::geometry | |
207 | ||
208 | #endif // BOOST_GEOMETRY_ALGORITHMS_DETAIL_OCCUPATION_INFO_HPP |