1 // Boost.Geometry
2
3 // Copyright (c) 2019, Oracle and/or its affiliates.
4
5 // Contributed and/or modified by Adam Wulkiewicz, on behalf of Oracle
6
7 // Licensed under the Boost Software License version 1.0.
8 // http://www.boost.org/users/license.html
9
10 #ifndef BOOST_GEOMETRY_ALGORITHMS_DETAIL_CALCULATE_POINT_ORDER_HPP
11 #define BOOST_GEOMETRY_ALGORITHMS_DETAIL_CALCULATE_POINT_ORDER_HPP
12
13
14 #include <vector>
15
16 #include <boost/mpl/assert.hpp>
17
18 #include <boost/geometry/algorithms/area.hpp>
19 #include <boost/geometry/core/point_order.hpp>
20 #include <boost/geometry/core/radian_access.hpp>
21 #include <boost/geometry/strategies/geographic/point_order.hpp>
22 #include <boost/geometry/util/math.hpp>
23 #include <boost/geometry/util/range.hpp>
24
25
26 namespace boost { namespace geometry
27 {
28
29 namespace detail
30 {
31
32 template <typename Iter, typename CalcT>
33 struct clean_point
34 {
clean_pointboost::geometry::detail::clean_point35 explicit clean_point(Iter const& iter)
36 : m_iter(iter), m_azi(0), m_razi(0), m_azi_diff(0)
37 , m_is_azi_valid(false), m_is_azi_diff_valid(false)
38 {}
39
refboost::geometry::detail::clean_point40 typename boost::iterators::iterator_reference<Iter>::type ref() const
41 {
42 return *m_iter;
43 }
44
azimuthboost::geometry::detail::clean_point45 CalcT const& azimuth() const
46 {
47 return m_azi;
48 }
49
reverse_azimuthboost::geometry::detail::clean_point50 CalcT const& reverse_azimuth() const
51 {
52 return m_razi;
53 }
54
azimuth_differenceboost::geometry::detail::clean_point55 CalcT const& azimuth_difference() const
56 {
57 return m_azi_diff;
58 }
59
set_azimuthsboost::geometry::detail::clean_point60 void set_azimuths(CalcT const& azi, CalcT const& razi)
61 {
62 m_azi = azi;
63 m_razi = razi;
64 m_is_azi_valid = true;
65 }
66
set_azimuth_invalidboost::geometry::detail::clean_point67 void set_azimuth_invalid()
68 {
69 m_is_azi_valid = false;
70 }
71
is_azimuth_validboost::geometry::detail::clean_point72 bool is_azimuth_valid() const
73 {
74 return m_is_azi_valid;
75 }
76
set_azimuth_differenceboost::geometry::detail::clean_point77 void set_azimuth_difference(CalcT const& diff)
78 {
79 m_azi_diff = diff;
80 m_is_azi_diff_valid = true;
81 }
82
set_azimuth_difference_invalidboost::geometry::detail::clean_point83 void set_azimuth_difference_invalid()
84 {
85 m_is_azi_diff_valid = false;
86 }
87
is_azimuth_difference_validboost::geometry::detail::clean_point88 bool is_azimuth_difference_valid() const
89 {
90 return m_is_azi_diff_valid;
91 }
92
93 private:
94 Iter m_iter;
95 CalcT m_azi;
96 CalcT m_razi;
97 CalcT m_azi_diff;
98 // NOTE: these flags could be removed and replaced with some magic number
99 // assigned to the above variables, e.g. CalcT(1000).
100 bool m_is_azi_valid;
101 bool m_is_azi_diff_valid;
102 };
103
104 struct calculate_point_order_by_azimuth
105 {
106 template <typename Ring, typename Strategy>
applyboost::geometry::detail::calculate_point_order_by_azimuth107 static geometry::order_selector apply(Ring const& ring, Strategy const& strategy)
108 {
109 typedef typename boost::range_iterator<Ring const>::type iter_t;
110 typedef typename Strategy::template result_type<Ring>::type calc_t;
111 typedef clean_point<iter_t, calc_t> clean_point_t;
112 typedef std::vector<clean_point_t> cleaned_container_t;
113 typedef typename cleaned_container_t::iterator cleaned_iter_t;
114
115 calc_t const zero = 0;
116 calc_t const pi = math::pi<calc_t>();
117
118 std::size_t const count = boost::size(ring);
119 if (count < 3)
120 {
121 return geometry::order_undetermined;
122 }
123
124 // non-duplicated, non-spike points
125 cleaned_container_t cleaned;
126 cleaned.reserve(count);
127
128 for (iter_t it = boost::begin(ring); it != boost::end(ring); ++it)
129 {
130 // Add point
131 cleaned.push_back(clean_point_t(it));
132
133 while (cleaned.size() >= 3)
134 {
135 cleaned_iter_t it0 = cleaned.end() - 3;
136 cleaned_iter_t it1 = cleaned.end() - 2;
137 cleaned_iter_t it2 = cleaned.end() - 1;
138
139 calc_t diff;
140 if (get_or_calculate_azimuths_difference(*it0, *it1, *it2, diff, strategy)
141 && ! math::equals(math::abs(diff), pi))
142 {
143 // neither duplicate nor a spike - difference already stored
144 break;
145 }
146 else
147 {
148 // spike detected
149 // TODO: angles have to be invalidated only if spike is detected
150 // for duplicates it'd be ok to leave them
151 it0->set_azimuth_invalid();
152 it0->set_azimuth_difference_invalid();
153 it2->set_azimuth_difference_invalid();
154 cleaned.erase(it1);
155 }
156 }
157 }
158
159 // filter-out duplicates and spikes at the front and back of cleaned
160 cleaned_iter_t cleaned_b = cleaned.begin();
161 cleaned_iter_t cleaned_e = cleaned.end();
162 std::size_t cleaned_count = cleaned.size();
163 bool found = false;
164 do
165 {
166 found = false;
167 while(cleaned_count >= 3)
168 {
169 cleaned_iter_t it0 = cleaned_e - 2;
170 cleaned_iter_t it1 = cleaned_e - 1;
171 cleaned_iter_t it2 = cleaned_b;
172 cleaned_iter_t it3 = cleaned_b + 1;
173
174 calc_t diff = 0;
175 if (! get_or_calculate_azimuths_difference(*it0, *it1, *it2, diff, strategy)
176 || math::equals(math::abs(diff), pi))
177 {
178 // spike at the back
179 // TODO: angles have to be invalidated only if spike is detected
180 // for duplicates it'd be ok to leave them
181 it0->set_azimuth_invalid();
182 it0->set_azimuth_difference_invalid();
183 it2->set_azimuth_difference_invalid();
184 --cleaned_e;
185 --cleaned_count;
186 found = true;
187 }
188 else if (! get_or_calculate_azimuths_difference(*it1, *it2, *it3, diff, strategy)
189 || math::equals(math::abs(diff), pi))
190 {
191 // spike at the front
192 // TODO: angles have to be invalidated only if spike is detected
193 // for duplicates it'd be ok to leave them
194 it1->set_azimuth_invalid();
195 it1->set_azimuth_difference_invalid();
196 it3->set_azimuth_difference_invalid();
197 ++cleaned_b;
198 --cleaned_count;
199 found = true;
200 }
201 else
202 {
203 break;
204 }
205 }
206 }
207 while (found);
208
209 if (cleaned_count < 3)
210 {
211 return geometry::order_undetermined;
212 }
213
214 // calculate the sum of external angles
215 calc_t angles_sum = zero;
216 for (cleaned_iter_t it = cleaned_b; it != cleaned_e; ++it)
217 {
218 cleaned_iter_t it0 = (it == cleaned_b ? cleaned_e - 1 : it - 1);
219 cleaned_iter_t it2 = (it == cleaned_e - 1 ? cleaned_b : it + 1);
220
221 calc_t diff = 0;
222 get_or_calculate_azimuths_difference(*it0, *it, *it2, diff, strategy);
223
224 angles_sum += diff;
225 }
226
227 #ifdef BOOST_GEOMETRY_DEBUG_POINT_ORDER
228 std::cout << angles_sum << " for " << geometry::wkt(ring) << std::endl;
229 #endif
230
231 return angles_sum == zero ? geometry::order_undetermined
232 : angles_sum > zero ? geometry::clockwise
233 : geometry::counterclockwise;
234 }
235
236 private:
237 template <typename Iter, typename T, typename Strategy>
get_or_calculate_azimuths_differenceboost::geometry::detail::calculate_point_order_by_azimuth238 static bool get_or_calculate_azimuths_difference(clean_point<Iter, T> & p0,
239 clean_point<Iter, T> & p1,
240 clean_point<Iter, T> const& p2,
241 T & diff,
242 Strategy const& strategy)
243 {
244 if (p1.is_azimuth_difference_valid())
245 {
246 diff = p1.azimuth_difference();
247 return true;
248 }
249
250 T azi1, razi1, azi2, razi2;
251 if (get_or_calculate_azimuths(p0, p1, azi1, razi1, strategy)
252 && get_or_calculate_azimuths(p1, p2, azi2, razi2, strategy))
253 {
254 diff = strategy.apply(p0.ref(), p1.ref(), p2.ref(), razi1, azi2);
255 p1.set_azimuth_difference(diff);
256 return true;
257 }
258 return false;
259 }
260
261 template <typename Iter, typename T, typename Strategy>
get_or_calculate_azimuthsboost::geometry::detail::calculate_point_order_by_azimuth262 static bool get_or_calculate_azimuths(clean_point<Iter, T> & p0,
263 clean_point<Iter, T> const& p1,
264 T & azi, T & razi,
265 Strategy const& strategy)
266 {
267 if (p0.is_azimuth_valid())
268 {
269 azi = p0.azimuth();
270 razi = p0.reverse_azimuth();
271 return true;
272 }
273
274 if (strategy.apply(p0.ref(), p1.ref(), azi, razi))
275 {
276 p0.set_azimuths(azi, razi);
277 return true;
278 }
279
280 return false;
281 }
282 };
283
284 struct calculate_point_order_by_area
285 {
286 template <typename Ring, typename Strategy>
applyboost::geometry::detail::calculate_point_order_by_area287 static geometry::order_selector apply(Ring const& ring, Strategy const& strategy)
288 {
289 typedef detail::area::ring_area
290 <
291 geometry::order_as_direction<geometry::point_order<Ring>::value>::value,
292 geometry::closure<Ring>::value
293 > ring_area_type;
294
295 typedef typename area_result
296 <
297 Ring, Strategy
298 >::type result_type;
299
300 result_type const result = ring_area_type::apply(ring, strategy);
301
302 result_type const zero = 0;
303 return result == zero ? geometry::order_undetermined
304 : result > zero ? geometry::clockwise
305 : geometry::counterclockwise;
306 }
307 };
308
309 } // namespace detail
310
311 namespace dispatch
312 {
313
314 template
315 <
316 typename Strategy,
317 typename VersionTag = typename Strategy::version_tag
318 >
319 struct calculate_point_order
320 {
321 BOOST_MPL_ASSERT_MSG
322 (
323 false, NOT_IMPLEMENTED_FOR_THIS_TAG, (types<VersionTag>)
324 );
325 };
326
327 template <typename Strategy>
328 struct calculate_point_order<Strategy, strategy::point_order::area_tag>
329 : geometry::detail::calculate_point_order_by_area
330 {};
331
332 template <typename Strategy>
333 struct calculate_point_order<Strategy, strategy::point_order::azimuth_tag>
334 : geometry::detail::calculate_point_order_by_azimuth
335 {};
336
337
338 } // namespace dispatch
339
340 namespace detail
341 {
342
343 template <typename Ring, typename Strategy>
calculate_point_order(Ring const & ring,Strategy const & strategy)344 inline geometry::order_selector calculate_point_order(Ring const& ring, Strategy const& strategy)
345 {
346 concepts::check<Ring>();
347
348 return dispatch::calculate_point_order<Strategy>::apply(ring, strategy);
349 }
350
351 template <typename Ring>
calculate_point_order(Ring const & ring)352 inline geometry::order_selector calculate_point_order(Ring const& ring)
353 {
354 typedef typename strategy::point_order::services::default_strategy
355 <
356 typename geometry::cs_tag<Ring>::type
357 >::type strategy_type;
358
359 concepts::check<Ring>();
360
361 return dispatch::calculate_point_order<strategy_type>::apply(ring, strategy_type());
362 }
363
364
365 } // namespace detail
366
367 }} // namespace boost::geometry
368
369
370 #endif // BOOST_GEOMETRY_ALGORITHMS_DETAIL_CALCULATE_POINT_ORDER_HPP
371