]>
Commit | Line | Data |
---|---|---|
7c673cae FG |
1 | // Boost.Geometry (aka GGL, Generic Geometry Library) |
2 | ||
3 | // Copyright (c) 2007-2013 Barend Gehrels, Amsterdam, the Netherlands. | |
4 | // Copyright (c) 2008-2013 Bruno Lalande, Paris, France. | |
5 | // Copyright (c) 2009-2013 Mateusz Loskot, London, UK. | |
11fdf7f2 | 6 | // Copyright (c) 2013-2017 Adam Wulkiewicz, Lodz, Poland. |
7c673cae | 7 | |
92f5a8d4 TL |
8 | // This file was modified by Oracle on 2017, 2018. |
9 | // Modifications copyright (c) 2017-2018 Oracle and/or its affiliates. | |
b32b8144 FG |
10 | |
11 | // Contributed and/or modified by Adam Wulkiewicz, on behalf of Oracle | |
12 | ||
7c673cae FG |
13 | // Use, modification and distribution is subject to the Boost Software License, |
14 | // Version 1.0. (See accompanying file LICENSE_1_0.txt or copy at | |
15 | // http://www.boost.org/LICENSE_1_0.txt) | |
16 | ||
17 | #ifndef BOOST_GEOMETRY_ALGORITHMS_DETAIL_EXTREME_POINTS_HPP | |
18 | #define BOOST_GEOMETRY_ALGORITHMS_DETAIL_EXTREME_POINTS_HPP | |
19 | ||
20 | ||
21 | #include <cstddef> | |
22 | ||
23 | #include <boost/range.hpp> | |
24 | ||
25 | #include <boost/geometry/algorithms/detail/interior_iterator.hpp> | |
26 | ||
27 | #include <boost/geometry/core/cs.hpp> | |
92f5a8d4 | 28 | #include <boost/geometry/core/point_order.hpp> |
7c673cae FG |
29 | #include <boost/geometry/core/point_type.hpp> |
30 | #include <boost/geometry/core/ring_type.hpp> | |
31 | #include <boost/geometry/core/tags.hpp> | |
32 | ||
33 | #include <boost/geometry/geometries/concepts/check.hpp> | |
34 | #include <boost/geometry/iterators/ever_circling_iterator.hpp> | |
35 | ||
36 | #include <boost/geometry/algorithms/detail/assign_box_corners.hpp> | |
37 | ||
38 | #include <boost/geometry/strategies/side.hpp> | |
39 | ||
40 | #include <boost/geometry/util/math.hpp> | |
41 | ||
42 | ||
43 | namespace boost { namespace geometry | |
44 | { | |
45 | ||
46 | ||
47 | #ifndef DOXYGEN_NO_DETAIL | |
48 | namespace detail { namespace extreme_points | |
49 | { | |
50 | ||
51 | template <std::size_t Dimension> | |
52 | struct compare | |
53 | { | |
54 | template <typename Point> | |
55 | inline bool operator()(Point const& lhs, Point const& rhs) | |
56 | { | |
57 | return geometry::get<Dimension>(lhs) < geometry::get<Dimension>(rhs); | |
58 | } | |
59 | }; | |
60 | ||
61 | ||
62 | template <std::size_t Dimension, typename PointType, typename CoordinateType> | |
63 | inline void move_along_vector(PointType& point, PointType const& extreme, CoordinateType const& base_value) | |
64 | { | |
65 | // Moves a point along the vector (point, extreme) in the direction of the extreme point | |
66 | // This adapts the possibly uneven legs of the triangle (or trapezium-like shape) | |
67 | // _____extreme _____ | |
68 | // / \ / \ . | |
69 | // /base \ => / \ point . | |
70 | // \ point . | |
71 | // | |
72 | // For so-called intruders, it can be used to adapt both legs to the level of "base" | |
73 | // For the base, it can be used to adapt both legs to the level of the max-value of the intruders | |
74 | // If there are 2 or more extreme values, use the one close to 'point' to have a correct vector | |
75 | ||
76 | CoordinateType const value = geometry::get<Dimension>(point); | |
77 | //if (geometry::math::equals(value, base_value)) | |
78 | if (value >= base_value) | |
79 | { | |
80 | return; | |
81 | } | |
82 | ||
83 | PointType vector = point; | |
84 | subtract_point(vector, extreme); | |
85 | ||
86 | CoordinateType const diff = geometry::get<Dimension>(vector); | |
87 | ||
88 | // diff should never be zero | |
89 | // because of the way our triangle/trapezium is build. | |
90 | // We just return if it would be the case. | |
91 | if (geometry::math::equals(diff, 0)) | |
92 | { | |
93 | return; | |
94 | } | |
95 | ||
96 | CoordinateType const base_diff = base_value - geometry::get<Dimension>(extreme); | |
97 | ||
98 | multiply_value(vector, base_diff); | |
99 | divide_value(vector, diff); | |
100 | ||
101 | // The real move: | |
102 | point = extreme; | |
103 | add_point(point, vector); | |
104 | } | |
105 | ||
106 | ||
107 | template <std::size_t Dimension, typename Range, typename CoordinateType> | |
108 | inline void move_along_vector(Range& range, CoordinateType const& base_value) | |
109 | { | |
110 | if (range.size() >= 3) | |
111 | { | |
112 | move_along_vector<Dimension>(range.front(), *(range.begin() + 1), base_value); | |
113 | move_along_vector<Dimension>(range.back(), *(range.rbegin() + 1), base_value); | |
114 | } | |
115 | } | |
116 | ||
117 | ||
118 | template<typename Ring, std::size_t Dimension> | |
119 | struct extreme_points_on_ring | |
120 | { | |
121 | ||
122 | typedef typename geometry::coordinate_type<Ring>::type coordinate_type; | |
123 | typedef typename boost::range_iterator<Ring const>::type range_iterator; | |
124 | typedef typename geometry::point_type<Ring>::type point_type; | |
125 | ||
7c673cae FG |
126 | template <typename CirclingIterator, typename Points> |
127 | static inline bool extend(CirclingIterator& it, | |
128 | std::size_t n, | |
129 | coordinate_type max_coordinate_value, | |
130 | Points& points, int direction) | |
131 | { | |
132 | std::size_t safe_index = 0; | |
133 | do | |
134 | { | |
135 | it += direction; | |
136 | ||
137 | points.push_back(*it); | |
138 | ||
139 | if (safe_index++ >= n) | |
140 | { | |
141 | // E.g.: ring is completely horizontal or vertical (= invalid, but we don't want to have an infinite loop) | |
142 | return false; | |
143 | } | |
144 | } while (geometry::math::equals(geometry::get<Dimension>(*it), max_coordinate_value)); | |
145 | ||
146 | return true; | |
147 | } | |
148 | ||
149 | // Overload without adding to poinst | |
150 | template <typename CirclingIterator> | |
151 | static inline bool extend(CirclingIterator& it, | |
152 | std::size_t n, | |
153 | coordinate_type max_coordinate_value, | |
154 | int direction) | |
155 | { | |
156 | std::size_t safe_index = 0; | |
157 | do | |
158 | { | |
159 | it += direction; | |
160 | ||
161 | if (safe_index++ >= n) | |
162 | { | |
163 | // E.g.: ring is completely horizontal or vertical (= invalid, but we don't want to have an infinite loop) | |
164 | return false; | |
165 | } | |
166 | } while (geometry::math::equals(geometry::get<Dimension>(*it), max_coordinate_value)); | |
167 | ||
168 | return true; | |
169 | } | |
170 | ||
171 | template <typename CirclingIterator> | |
172 | static inline bool extent_both_sides(Ring const& ring, | |
173 | point_type extreme, | |
174 | CirclingIterator& left, | |
175 | CirclingIterator& right) | |
176 | { | |
177 | std::size_t const n = boost::size(ring); | |
178 | coordinate_type const max_coordinate_value = geometry::get<Dimension>(extreme); | |
179 | ||
180 | if (! extend(left, n, max_coordinate_value, -1)) | |
181 | { | |
182 | return false; | |
183 | } | |
184 | if (! extend(right, n, max_coordinate_value, +1)) | |
185 | { | |
186 | return false; | |
187 | } | |
188 | ||
189 | return true; | |
190 | } | |
191 | ||
192 | template <typename Collection, typename CirclingIterator> | |
193 | static inline bool collect(Ring const& ring, | |
194 | point_type extreme, | |
195 | Collection& points, | |
196 | CirclingIterator& left, | |
197 | CirclingIterator& right) | |
198 | { | |
199 | std::size_t const n = boost::size(ring); | |
200 | coordinate_type const max_coordinate_value = geometry::get<Dimension>(extreme); | |
201 | ||
202 | // Collects first left, which is reversed (if more than one point) then adds the top itself, then right | |
203 | if (! extend(left, n, max_coordinate_value, points, -1)) | |
204 | { | |
205 | return false; | |
206 | } | |
207 | std::reverse(points.begin(), points.end()); | |
208 | points.push_back(extreme); | |
209 | if (! extend(right, n, max_coordinate_value, points, +1)) | |
210 | { | |
211 | return false; | |
212 | } | |
213 | ||
214 | return true; | |
215 | } | |
216 | ||
b32b8144 | 217 | template <typename Extremes, typename Intruders, typename CirclingIterator, typename SideStrategy> |
7c673cae FG |
218 | static inline void get_intruders(Ring const& ring, CirclingIterator left, CirclingIterator right, |
219 | Extremes const& extremes, | |
b32b8144 FG |
220 | Intruders& intruders, |
221 | SideStrategy const& strategy) | |
7c673cae FG |
222 | { |
223 | if (boost::size(extremes) < 3) | |
224 | { | |
225 | return; | |
226 | } | |
227 | coordinate_type const min_value = geometry::get<Dimension>(*std::min_element(boost::begin(extremes), boost::end(extremes), compare<Dimension>())); | |
228 | ||
229 | // Also select left/right (if Dimension=1) | |
230 | coordinate_type const other_min = geometry::get<1 - Dimension>(*std::min_element(boost::begin(extremes), boost::end(extremes), compare<1 - Dimension>())); | |
231 | coordinate_type const other_max = geometry::get<1 - Dimension>(*std::max_element(boost::begin(extremes), boost::end(extremes), compare<1 - Dimension>())); | |
232 | ||
233 | std::size_t defensive_check_index = 0; // in case we skip over left/right check, collect modifies right too | |
234 | std::size_t const n = boost::size(ring); | |
235 | while (left != right && defensive_check_index < n) | |
236 | { | |
237 | coordinate_type const coordinate = geometry::get<Dimension>(*right); | |
238 | coordinate_type const other_coordinate = geometry::get<1 - Dimension>(*right); | |
239 | if (coordinate > min_value && other_coordinate > other_min && other_coordinate < other_max) | |
240 | { | |
241 | int const factor = geometry::point_order<Ring>::value == geometry::clockwise ? 1 : -1; | |
b32b8144 FG |
242 | int const first_side = strategy.apply(*right, extremes.front(), *(extremes.begin() + 1)) * factor; |
243 | int const last_side = strategy.apply(*right, *(extremes.rbegin() + 1), extremes.back()) * factor; | |
7c673cae FG |
244 | |
245 | // If not lying left from any of the extemes side | |
246 | if (first_side != 1 && last_side != 1) | |
247 | { | |
248 | //std::cout << "first " << first_side << " last " << last_side << std::endl; | |
249 | ||
250 | // we start at this intrusion until it is handled, and don't affect our initial left iterator | |
251 | CirclingIterator left_intrusion_it = right; | |
252 | typename boost::range_value<Intruders>::type intruder; | |
253 | collect(ring, *right, intruder, left_intrusion_it, right); | |
254 | ||
255 | // Also moves these to base-level, makes sorting possible which can be done in case of self-tangencies | |
256 | // (we might postpone this action, it is often not necessary. However it is not time-consuming) | |
257 | move_along_vector<Dimension>(intruder, min_value); | |
258 | intruders.push_back(intruder); | |
259 | --right; | |
260 | } | |
261 | } | |
262 | ++right; | |
263 | defensive_check_index++; | |
264 | } | |
265 | } | |
266 | ||
b32b8144 | 267 | template <typename Extremes, typename Intruders, typename SideStrategy> |
7c673cae FG |
268 | static inline void get_intruders(Ring const& ring, |
269 | Extremes const& extremes, | |
b32b8144 FG |
270 | Intruders& intruders, |
271 | SideStrategy const& strategy) | |
7c673cae FG |
272 | { |
273 | std::size_t const n = boost::size(ring); | |
274 | if (n >= 3) | |
275 | { | |
276 | geometry::ever_circling_range_iterator<Ring const> left(ring); | |
277 | geometry::ever_circling_range_iterator<Ring const> right(ring); | |
278 | ++right; | |
279 | ||
b32b8144 | 280 | get_intruders(ring, left, right, extremes, intruders, strategy); |
7c673cae FG |
281 | } |
282 | } | |
283 | ||
b32b8144 FG |
284 | template <typename Iterator, typename SideStrategy> |
285 | static inline bool right_turn(Ring const& ring, Iterator it, SideStrategy const& strategy) | |
7c673cae FG |
286 | { |
287 | typename std::iterator_traits<Iterator>::difference_type const index | |
288 | = std::distance(boost::begin(ring), it); | |
289 | geometry::ever_circling_range_iterator<Ring const> left(ring); | |
290 | geometry::ever_circling_range_iterator<Ring const> right(ring); | |
291 | left += index; | |
292 | right += index; | |
293 | ||
294 | if (! extent_both_sides(ring, *it, left, right)) | |
295 | { | |
296 | return false; | |
297 | } | |
298 | ||
299 | int const factor = geometry::point_order<Ring>::value == geometry::clockwise ? 1 : -1; | |
b32b8144 FG |
300 | int const first_side = strategy.apply(*(right - 1), *right, *left) * factor; |
301 | int const last_side = strategy.apply(*left, *(left + 1), *right) * factor; | |
7c673cae FG |
302 | |
303 | //std::cout << "Candidate at " << geometry::wkt(*it) << " first=" << first_side << " last=" << last_side << std::endl; | |
304 | ||
305 | // Turn should not be left (actually, it should be right because extent removes horizontal/collinear cases) | |
306 | return first_side != 1 && last_side != 1; | |
307 | } | |
308 | ||
309 | ||
310 | // Gets the extreme segments (top point plus neighbouring points), plus intruders, if any, on the same ring | |
b32b8144 FG |
311 | template <typename Extremes, typename Intruders, typename SideStrategy> |
312 | static inline bool apply(Ring const& ring, | |
313 | Extremes& extremes, | |
314 | Intruders& intruders, | |
315 | SideStrategy const& strategy) | |
7c673cae FG |
316 | { |
317 | std::size_t const n = boost::size(ring); | |
318 | if (n < 3) | |
319 | { | |
320 | return false; | |
321 | } | |
322 | ||
323 | // Get all maxima, usually one. In case of self-tangencies, or self-crossings, | |
324 | // the max might be is not valid. A valid max should make a right turn | |
325 | range_iterator max_it = boost::begin(ring); | |
326 | compare<Dimension> smaller; | |
327 | for (range_iterator it = max_it + 1; it != boost::end(ring); ++it) | |
328 | { | |
b32b8144 | 329 | if (smaller(*max_it, *it) && right_turn(ring, it, strategy)) |
7c673cae FG |
330 | { |
331 | max_it = it; | |
332 | } | |
333 | } | |
334 | ||
335 | if (max_it == boost::end(ring)) | |
336 | { | |
337 | return false; | |
338 | } | |
339 | ||
340 | typename std::iterator_traits<range_iterator>::difference_type const | |
341 | index = std::distance(boost::begin(ring), max_it); | |
342 | //std::cout << "Extreme point lies at " << index << " having " << geometry::wkt(*max_it) << std::endl; | |
343 | ||
344 | geometry::ever_circling_range_iterator<Ring const> left(ring); | |
345 | geometry::ever_circling_range_iterator<Ring const> right(ring); | |
346 | left += index; | |
347 | right += index; | |
348 | ||
349 | // Collect all points (often 3) in a temporary vector | |
350 | std::vector<point_type> points; | |
351 | points.reserve(3); | |
352 | if (! collect(ring, *max_it, points, left, right)) | |
353 | { | |
354 | return false; | |
355 | } | |
356 | ||
357 | //std::cout << "Built vector of " << points.size() << std::endl; | |
358 | ||
359 | coordinate_type const front_value = geometry::get<Dimension>(points.front()); | |
360 | coordinate_type const back_value = geometry::get<Dimension>(points.back()); | |
361 | coordinate_type const base_value = (std::max)(front_value, back_value); | |
362 | if (front_value < back_value) | |
363 | { | |
364 | move_along_vector<Dimension>(points.front(), *(points.begin() + 1), base_value); | |
365 | } | |
366 | else | |
367 | { | |
368 | move_along_vector<Dimension>(points.back(), *(points.rbegin() + 1), base_value); | |
369 | } | |
370 | ||
371 | std::copy(points.begin(), points.end(), std::back_inserter(extremes)); | |
372 | ||
b32b8144 | 373 | get_intruders(ring, left, right, extremes, intruders, strategy); |
7c673cae FG |
374 | |
375 | return true; | |
376 | } | |
377 | }; | |
378 | ||
379 | ||
380 | ||
381 | ||
382 | ||
383 | }} // namespace detail::extreme_points | |
384 | #endif // DOXYGEN_NO_DETAIL | |
385 | ||
386 | ||
387 | #ifndef DOXYGEN_NO_DISPATCH | |
388 | namespace dispatch | |
389 | { | |
390 | ||
391 | ||
392 | template | |
393 | < | |
394 | typename Geometry, | |
395 | std::size_t Dimension, | |
396 | typename GeometryTag = typename tag<Geometry>::type | |
397 | > | |
398 | struct extreme_points | |
399 | {}; | |
400 | ||
401 | ||
402 | template<typename Ring, std::size_t Dimension> | |
403 | struct extreme_points<Ring, Dimension, ring_tag> | |
404 | : detail::extreme_points::extreme_points_on_ring<Ring, Dimension> | |
405 | {}; | |
406 | ||
407 | ||
408 | template<typename Polygon, std::size_t Dimension> | |
409 | struct extreme_points<Polygon, Dimension, polygon_tag> | |
410 | { | |
b32b8144 FG |
411 | template <typename Extremes, typename Intruders, typename SideStrategy> |
412 | static inline bool apply(Polygon const& polygon, Extremes& extremes, Intruders& intruders, | |
413 | SideStrategy const& strategy) | |
7c673cae FG |
414 | { |
415 | typedef typename geometry::ring_type<Polygon>::type ring_type; | |
416 | typedef detail::extreme_points::extreme_points_on_ring | |
417 | < | |
418 | ring_type, Dimension | |
419 | > ring_implementation; | |
420 | ||
b32b8144 FG |
421 | if (! ring_implementation::apply(geometry::exterior_ring(polygon), |
422 | extremes, intruders, strategy)) | |
7c673cae FG |
423 | { |
424 | return false; | |
425 | } | |
426 | ||
427 | // For a polygon, its interior rings can contain intruders | |
428 | typename interior_return_type<Polygon const>::type | |
429 | rings = interior_rings(polygon); | |
430 | for (typename detail::interior_iterator<Polygon const>::type | |
431 | it = boost::begin(rings); it != boost::end(rings); ++it) | |
432 | { | |
b32b8144 | 433 | ring_implementation::get_intruders(*it, extremes, intruders, strategy); |
7c673cae FG |
434 | } |
435 | ||
436 | return true; | |
437 | } | |
438 | }; | |
439 | ||
440 | template<typename Box> | |
441 | struct extreme_points<Box, 1, box_tag> | |
442 | { | |
b32b8144 FG |
443 | template <typename Extremes, typename Intruders, typename SideStrategy> |
444 | static inline bool apply(Box const& box, Extremes& extremes, Intruders& , | |
445 | SideStrategy const& ) | |
7c673cae FG |
446 | { |
447 | extremes.resize(4); | |
448 | geometry::detail::assign_box_corners_oriented<false>(box, extremes); | |
449 | // ll,ul,ur,lr, contains too exactly the right info | |
450 | return true; | |
451 | } | |
452 | }; | |
453 | ||
454 | template<typename Box> | |
455 | struct extreme_points<Box, 0, box_tag> | |
456 | { | |
b32b8144 FG |
457 | template <typename Extremes, typename Intruders, typename SideStrategy> |
458 | static inline bool apply(Box const& box, Extremes& extremes, Intruders& , | |
459 | SideStrategy const& ) | |
7c673cae FG |
460 | { |
461 | extremes.resize(4); | |
462 | geometry::detail::assign_box_corners_oriented<false>(box, extremes); | |
463 | // ll,ul,ur,lr, rotate one to start with UL and end with LL | |
464 | std::rotate(extremes.begin(), extremes.begin() + 1, extremes.end()); | |
465 | return true; | |
466 | } | |
467 | }; | |
468 | ||
469 | template<typename MultiPolygon, std::size_t Dimension> | |
470 | struct extreme_points<MultiPolygon, Dimension, multi_polygon_tag> | |
471 | { | |
b32b8144 FG |
472 | template <typename Extremes, typename Intruders, typename SideStrategy> |
473 | static inline bool apply(MultiPolygon const& multi, Extremes& extremes, | |
474 | Intruders& intruders, SideStrategy const& strategy) | |
7c673cae FG |
475 | { |
476 | // Get one for the very first polygon, that is (for the moment) enough. | |
477 | // It is not guaranteed the "extreme" then, but for the current purpose | |
478 | // (point_on_surface) it can just be this point. | |
479 | if (boost::size(multi) >= 1) | |
480 | { | |
481 | return extreme_points | |
482 | < | |
483 | typename boost::range_value<MultiPolygon const>::type, | |
484 | Dimension, | |
485 | polygon_tag | |
b32b8144 | 486 | >::apply(*boost::begin(multi), extremes, intruders, strategy); |
7c673cae FG |
487 | } |
488 | ||
489 | return false; | |
490 | } | |
491 | }; | |
492 | ||
493 | } // namespace dispatch | |
494 | #endif // DOXYGEN_NO_DISPATCH | |
495 | ||
496 | ||
497 | /*! | |
498 | \brief Returns extreme points (for Edge=1 in dimension 1, so the top, | |
499 | for Edge=0 in dimension 0, the right side) | |
500 | \note We could specify a strategy (less/greater) to get bottom/left side too. However, until now we don't need that. | |
501 | */ | |
b32b8144 FG |
502 | template |
503 | < | |
504 | std::size_t Edge, | |
505 | typename Geometry, | |
506 | typename Extremes, | |
507 | typename Intruders, | |
508 | typename SideStrategy | |
509 | > | |
510 | inline bool extreme_points(Geometry const& geometry, | |
511 | Extremes& extremes, | |
512 | Intruders& intruders, | |
513 | SideStrategy const& strategy) | |
7c673cae FG |
514 | { |
515 | concepts::check<Geometry const>(); | |
516 | ||
517 | // Extremes is not required to follow a geometry concept (but it should support an output iterator), | |
518 | // but its elements should fulfil the point-concept | |
519 | concepts::check<typename boost::range_value<Extremes>::type>(); | |
520 | ||
521 | // Intruders should contain collections which value type is point-concept | |
522 | // Extremes might be anything (supporting an output iterator), but its elements should fulfil the point-concept | |
523 | concepts::check | |
524 | < | |
525 | typename boost::range_value | |
526 | < | |
527 | typename boost::range_value<Intruders>::type | |
528 | >::type | |
529 | const | |
530 | >(); | |
531 | ||
b32b8144 FG |
532 | return dispatch::extreme_points |
533 | < | |
534 | Geometry, | |
535 | Edge | |
536 | >::apply(geometry, extremes, intruders, strategy); | |
7c673cae FG |
537 | } |
538 | ||
539 | ||
11fdf7f2 TL |
540 | template |
541 | < | |
542 | std::size_t Edge, | |
543 | typename Geometry, | |
544 | typename Extremes, | |
545 | typename Intruders | |
546 | > | |
547 | inline bool extreme_points(Geometry const& geometry, | |
548 | Extremes& extremes, | |
549 | Intruders& intruders) | |
550 | { | |
551 | typedef typename strategy::side::services::default_strategy | |
552 | < | |
553 | typename cs_tag<Geometry>::type | |
554 | >::type strategy_type; | |
555 | ||
556 | return geometry::extreme_points<Edge>(geometry,extremes, intruders, strategy_type()); | |
557 | } | |
7c673cae FG |
558 | |
559 | }} // namespace boost::geometry | |
560 | ||
561 | ||
562 | #endif // BOOST_GEOMETRY_ALGORITHMS_DETAIL_EXTREME_POINTS_HPP |