1 // Boost.Geometry (aka GGL, Generic Geometry Library)
2
3 // Copyright (c) 2012-2014 Barend Gehrels, Amsterdam, the Netherlands.
4
5 // This file was modified by Oracle on 2017.
6 // Modifications copyright (c) 2017, Oracle and/or its affiliates.
7
8 // Contributed and/or modified by Adam Wulkiewicz, on behalf of Oracle
9
10 // Use, modification and distribution is subject to the Boost Software License,
11 // Version 1.0. (See accompanying file LICENSE_1_0.txt or copy at
12 // http://www.boost.org/LICENSE_1_0.txt)
13
14 #ifndef BOOST_GEOMETRY_ALGORITHMS_DETAIL_GET_LEFT_TURNS_HPP
15 #define BOOST_GEOMETRY_ALGORITHMS_DETAIL_GET_LEFT_TURNS_HPP
16
17 #include <boost/geometry/core/assert.hpp>
18
19 #include <boost/geometry/arithmetic/arithmetic.hpp>
20 #include <boost/geometry/algorithms/detail/overlay/segment_identifier.hpp>
21 #include <boost/geometry/algorithms/detail/overlay/turn_info.hpp>
22 #include <boost/geometry/iterators/closing_iterator.hpp>
23 #include <boost/geometry/iterators/ever_circling_iterator.hpp>
24 #include <boost/geometry/strategies/side.hpp>
25
26 namespace boost { namespace geometry
27 {
28
29
30 #ifndef DOXYGEN_NO_DETAIL
31 namespace detail
32 {
33
34 // TODO: move this to /util/
35 template <typename T>
ordered_pair(T const & first,T const & second)36 inline std::pair<T, T> ordered_pair(T const& first, T const& second)
37 {
38 return first < second ? std::make_pair(first, second) : std::make_pair(second, first);
39 }
40
41 namespace left_turns
42 {
43
44
45
46 template <typename Vector>
get_quadrant(Vector const & vector)47 inline int get_quadrant(Vector const& vector)
48 {
49 // Return quadrant as layouted in the code below:
50 // 3 | 0
51 // -----
52 // 2 | 1
53 return geometry::get<1>(vector) >= 0
54 ? (geometry::get<0>(vector) < 0 ? 3 : 0)
55 : (geometry::get<0>(vector) < 0 ? 2 : 1)
56 ;
57 }
58
59 template <typename Vector>
squared_length(Vector const & vector)60 inline int squared_length(Vector const& vector)
61 {
62 return geometry::get<0>(vector) * geometry::get<0>(vector)
63 + geometry::get<1>(vector) * geometry::get<1>(vector)
64 ;
65 }
66
67
68 template <typename Point, typename SideStrategy>
69 struct angle_less
70 {
71 typedef Point vector_type;
72
angle_lessboost::geometry::detail::left_turns::angle_less73 angle_less(Point const& origin, SideStrategy const& strategy)
74 : m_origin(origin)
75 , m_strategy(strategy)
76 {}
77
78 template <typename Angle>
operator ()boost::geometry::detail::left_turns::angle_less79 inline bool operator()(Angle const& p, Angle const& q) const
80 {
81 // Vector origin -> p and origin -> q
82 vector_type pv = p.point;
83 vector_type qv = q.point;
84 geometry::subtract_point(pv, m_origin);
85 geometry::subtract_point(qv, m_origin);
86
87 int const quadrant_p = get_quadrant(pv);
88 int const quadrant_q = get_quadrant(qv);
89 if (quadrant_p != quadrant_q)
90 {
91 return quadrant_p < quadrant_q;
92 }
93 // Same quadrant, check if p is located left of q
94 int const side = m_strategy.apply(m_origin, q.point, p.point);
95 if (side != 0)
96 {
97 return side == 1;
98 }
99 // Collinear, check if one is incoming, incoming angles come first
100 if (p.incoming != q.incoming)
101 {
102 return int(p.incoming) < int(q.incoming);
103 }
104 // Same quadrant/side/direction, return longest first
105 // TODO: maybe not necessary, decide this
106 int const length_p = squared_length(pv);
107 int const length_q = squared_length(qv);
108 if (length_p != length_q)
109 {
110 return squared_length(pv) > squared_length(qv);
111 }
112 // They are still the same. Just compare on seg_id
113 return p.seg_id < q.seg_id;
114 }
115
116 private:
117 Point m_origin;
118 SideStrategy m_strategy;
119 };
120
121 template <typename Point, typename SideStrategy>
122 struct angle_equal_to
123 {
124 typedef Point vector_type;
125
angle_equal_toboost::geometry::detail::left_turns::angle_equal_to126 inline angle_equal_to(Point const& origin, SideStrategy const& strategy)
127 : m_origin(origin)
128 , m_strategy(strategy)
129 {}
130
131 template <typename Angle>
operator ()boost::geometry::detail::left_turns::angle_equal_to132 inline bool operator()(Angle const& p, Angle const& q) const
133 {
134 // Vector origin -> p and origin -> q
135 vector_type pv = p.point;
136 vector_type qv = q.point;
137 geometry::subtract_point(pv, m_origin);
138 geometry::subtract_point(qv, m_origin);
139
140 if (get_quadrant(pv) != get_quadrant(qv))
141 {
142 return false;
143 }
144 // Same quadrant, check if p/q are collinear
145 int const side = m_strategy.apply(m_origin, q.point, p.point);
146 return side == 0;
147 }
148
149 private:
150 Point m_origin;
151 SideStrategy m_strategy;
152 };
153
154 template <typename AngleCollection, typename Turns>
get_left_turns(AngleCollection const & sorted_angles,Turns & turns)155 inline void get_left_turns(AngleCollection const& sorted_angles,
156 Turns& turns)
157 {
158 std::set<std::size_t> good_incoming;
159 std::set<std::size_t> good_outgoing;
160
161 for (typename boost::range_iterator<AngleCollection const>::type it =
162 sorted_angles.begin(); it != sorted_angles.end(); ++it)
163 {
164 if (!it->blocked)
165 {
166 if (it->incoming)
167 {
168 good_incoming.insert(it->turn_index);
169 }
170 else
171 {
172 good_outgoing.insert(it->turn_index);
173 }
174 }
175 }
176
177 if (good_incoming.empty() || good_outgoing.empty())
178 {
179 return;
180 }
181
182 for (typename boost::range_iterator<AngleCollection const>::type it =
183 sorted_angles.begin(); it != sorted_angles.end(); ++it)
184 {
185 if (good_incoming.count(it->turn_index) == 0
186 || good_outgoing.count(it->turn_index) == 0)
187 {
188 turns[it->turn_index].remove_on_multi = true;
189 }
190 }
191 }
192
193
194 //! Returns the number of clusters
195 template <typename Point, typename AngleCollection, typename SideStrategy>
assign_cluster_indices(AngleCollection & sorted,Point const & origin,SideStrategy const & strategy)196 inline std::size_t assign_cluster_indices(AngleCollection& sorted, Point const& origin,
197 SideStrategy const& strategy)
198 {
199 // Assign same cluster_index for all turns in same direction
200 BOOST_GEOMETRY_ASSERT(boost::size(sorted) >= 4u);
201
202 angle_equal_to<Point, SideStrategy> comparator(origin, strategy);
203 typename boost::range_iterator<AngleCollection>::type it = sorted.begin();
204
205 std::size_t cluster_index = 0;
206 it->cluster_index = cluster_index;
207 typename boost::range_iterator<AngleCollection>::type previous = it++;
208 for (; it != sorted.end(); ++it)
209 {
210 if (!comparator(*previous, *it))
211 {
212 cluster_index++;
213 previous = it;
214 }
215 it->cluster_index = cluster_index;
216 }
217 return cluster_index + 1;
218 }
219
220 template <typename AngleCollection>
block_turns(AngleCollection & sorted,std::size_t cluster_size)221 inline void block_turns(AngleCollection& sorted, std::size_t cluster_size)
222 {
223 BOOST_GEOMETRY_ASSERT(boost::size(sorted) >= 4u && cluster_size > 0);
224
225 std::vector<std::pair<bool, bool> > directions;
226 for (std::size_t i = 0; i < cluster_size; i++)
227 {
228 directions.push_back(std::make_pair(false, false));
229 }
230
231 for (typename boost::range_iterator<AngleCollection const>::type it = sorted.begin();
232 it != sorted.end(); ++it)
233 {
234 if (it->incoming)
235 {
236 directions[it->cluster_index].first = true;
237 }
238 else
239 {
240 directions[it->cluster_index].second = true;
241 }
242 }
243
244 for (typename boost::range_iterator<AngleCollection>::type it = sorted.begin();
245 it != sorted.end(); ++it)
246 {
247 signed_size_type cluster_index = static_cast<signed_size_type>(it->cluster_index);
248 signed_size_type previous_index = cluster_index - 1;
249 if (previous_index < 0)
250 {
251 previous_index = cluster_size - 1;
252 }
253 signed_size_type next_index = cluster_index + 1;
254 if (next_index >= static_cast<signed_size_type>(cluster_size))
255 {
256 next_index = 0;
257 }
258
259 if (directions[cluster_index].first
260 && directions[cluster_index].second)
261 {
262 it->blocked = true;
263 }
264 else if (!directions[cluster_index].first
265 && directions[cluster_index].second
266 && directions[previous_index].second)
267 {
268 // Only outgoing, previous was also outgoing: block this one
269 it->blocked = true;
270 }
271 else if (directions[cluster_index].first
272 && !directions[cluster_index].second
273 && !directions[previous_index].first
274 && directions[previous_index].second)
275 {
276 // Only incoming, previous was only outgoing: block this one
277 it->blocked = true;
278 }
279 else if (directions[cluster_index].first
280 && !directions[cluster_index].second
281 && directions[next_index].first
282 && !directions[next_index].second)
283 {
284 // Only incoming, next also incoming, block this one
285 it->blocked = true;
286 }
287 }
288 }
289
290 #if defined(BOOST_GEOMETRY_BUFFER_ENLARGED_CLUSTERS)
291 template <typename AngleCollection, typename Point>
has_rounding_issues(AngleCollection const & angles,Point const & origin)292 inline bool has_rounding_issues(AngleCollection const& angles, Point const& origin)
293 {
294 for (typename boost::range_iterator<AngleCollection const>::type it =
295 angles.begin(); it != angles.end(); ++it)
296 {
297 // Vector origin -> p and origin -> q
298 typedef Point vector_type;
299 vector_type v = it->point;
300 geometry::subtract_point(v, origin);
301 return geometry::math::abs(geometry::get<0>(v)) <= 1
302 || geometry::math::abs(geometry::get<1>(v)) <= 1
303 ;
304 }
305 return false;
306 }
307 #endif
308
309
310 } // namespace left_turns
311
312 } // namespace detail
313 #endif // DOXYGEN_NO_DETAIL
314
315
316 }} // namespace boost::geometry
317
318 #endif // BOOST_GEOMETRY_ALGORITHMS_DETAIL_GET_LEFT_TURNS_HPP
319