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