1 // Boost.Geometry (aka GGL, Generic Geometry Library)
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.
6 // Copyright (c) 2013-2017 Adam Wulkiewicz, Lodz, Poland.
8 // This file was modified by Oracle on 2017, 2018.
9 // Modifications copyright (c) 2017-2018 Oracle and/or its affiliates.
11 // Contributed and/or modified by Adam Wulkiewicz, on behalf of Oracle
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)
17 #ifndef BOOST_GEOMETRY_ALGORITHMS_DETAIL_EXTREME_POINTS_HPP
18 #define BOOST_GEOMETRY_ALGORITHMS_DETAIL_EXTREME_POINTS_HPP
23 #include <boost/range.hpp>
25 #include <boost/geometry/algorithms/detail/interior_iterator.hpp>
27 #include <boost/geometry/core/cs.hpp>
28 #include <boost/geometry/core/point_order.hpp>
29 #include <boost/geometry/core/point_type.hpp>
30 #include <boost/geometry/core/ring_type.hpp>
31 #include <boost/geometry/core/tags.hpp>
33 #include <boost/geometry/geometries/concepts/check.hpp>
34 #include <boost/geometry/iterators/ever_circling_iterator.hpp>
36 #include <boost/geometry/algorithms/detail/assign_box_corners.hpp>
38 #include <boost/geometry/strategies/side.hpp>
40 #include <boost/geometry/util/math.hpp>
43 namespace boost { namespace geometry
47 #ifndef DOXYGEN_NO_DETAIL
48 namespace detail { namespace extreme_points
51 template <std::size_t Dimension>
54 template <typename Point>
55 inline bool operator()(Point const& lhs, Point const& rhs)
57 return geometry::get<Dimension>(lhs) < geometry::get<Dimension>(rhs);
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)
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)
69 // /base \ => / \ point .
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
76 CoordinateType const value = geometry::get<Dimension>(point);
77 //if (geometry::math::equals(value, base_value))
78 if (value >= base_value)
83 PointType vector = point;
84 subtract_point(vector, extreme);
86 CoordinateType const diff = geometry::get<Dimension>(vector);
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))
96 CoordinateType const base_diff = base_value - geometry::get<Dimension>(extreme);
98 multiply_value(vector, base_diff);
99 divide_value(vector, diff);
103 add_point(point, vector);
107 template <std::size_t Dimension, typename Range, typename CoordinateType>
108 inline void move_along_vector(Range& range, CoordinateType const& base_value)
110 if (range.size() >= 3)
112 move_along_vector<Dimension>(range.front(), *(range.begin() + 1), base_value);
113 move_along_vector<Dimension>(range.back(), *(range.rbegin() + 1), base_value);
118 template<typename Ring, std::size_t Dimension>
119 struct extreme_points_on_ring
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;
126 template <typename CirclingIterator, typename Points>
127 static inline bool extend(CirclingIterator& it,
129 coordinate_type max_coordinate_value,
130 Points& points, int direction)
132 std::size_t safe_index = 0;
137 points.push_back(*it);
139 if (safe_index++ >= n)
141 // E.g.: ring is completely horizontal or vertical (= invalid, but we don't want to have an infinite loop)
144 } while (geometry::math::equals(geometry::get<Dimension>(*it), max_coordinate_value));
149 // Overload without adding to poinst
150 template <typename CirclingIterator>
151 static inline bool extend(CirclingIterator& it,
153 coordinate_type max_coordinate_value,
156 std::size_t safe_index = 0;
161 if (safe_index++ >= n)
163 // E.g.: ring is completely horizontal or vertical (= invalid, but we don't want to have an infinite loop)
166 } while (geometry::math::equals(geometry::get<Dimension>(*it), max_coordinate_value));
171 template <typename CirclingIterator>
172 static inline bool extent_both_sides(Ring const& ring,
174 CirclingIterator& left,
175 CirclingIterator& right)
177 std::size_t const n = boost::size(ring);
178 coordinate_type const max_coordinate_value = geometry::get<Dimension>(extreme);
180 if (! extend(left, n, max_coordinate_value, -1))
184 if (! extend(right, n, max_coordinate_value, +1))
192 template <typename Collection, typename CirclingIterator>
193 static inline bool collect(Ring const& ring,
196 CirclingIterator& left,
197 CirclingIterator& right)
199 std::size_t const n = boost::size(ring);
200 coordinate_type const max_coordinate_value = geometry::get<Dimension>(extreme);
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))
207 std::reverse(points.begin(), points.end());
208 points.push_back(extreme);
209 if (! extend(right, n, max_coordinate_value, points, +1))
217 template <typename Extremes, typename Intruders, typename CirclingIterator, typename SideStrategy>
218 static inline void get_intruders(Ring const& ring, CirclingIterator left, CirclingIterator right,
219 Extremes const& extremes,
220 Intruders& intruders,
221 SideStrategy const& strategy)
223 if (boost::size(extremes) < 3)
227 coordinate_type const min_value = geometry::get<Dimension>(*std::min_element(boost::begin(extremes), boost::end(extremes), compare<Dimension>()));
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>()));
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)
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)
241 int const factor = geometry::point_order<Ring>::value == geometry::clockwise ? 1 : -1;
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;
245 // If not lying left from any of the extemes side
246 if (first_side != 1 && last_side != 1)
248 //std::cout << "first " << first_side << " last " << last_side << std::endl;
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);
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);
263 defensive_check_index++;
267 template <typename Extremes, typename Intruders, typename SideStrategy>
268 static inline void get_intruders(Ring const& ring,
269 Extremes const& extremes,
270 Intruders& intruders,
271 SideStrategy const& strategy)
273 std::size_t const n = boost::size(ring);
276 geometry::ever_circling_range_iterator<Ring const> left(ring);
277 geometry::ever_circling_range_iterator<Ring const> right(ring);
280 get_intruders(ring, left, right, extremes, intruders, strategy);
284 template <typename Iterator, typename SideStrategy>
285 static inline bool right_turn(Ring const& ring, Iterator it, SideStrategy const& strategy)
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);
294 if (! extent_both_sides(ring, *it, left, right))
299 int const factor = geometry::point_order<Ring>::value == geometry::clockwise ? 1 : -1;
300 int const first_side = strategy.apply(*(right - 1), *right, *left) * factor;
301 int const last_side = strategy.apply(*left, *(left + 1), *right) * factor;
303 //std::cout << "Candidate at " << geometry::wkt(*it) << " first=" << first_side << " last=" << last_side << std::endl;
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;
310 // Gets the extreme segments (top point plus neighbouring points), plus intruders, if any, on the same ring
311 template <typename Extremes, typename Intruders, typename SideStrategy>
312 static inline bool apply(Ring const& ring,
314 Intruders& intruders,
315 SideStrategy const& strategy)
317 std::size_t const n = boost::size(ring);
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)
329 if (smaller(*max_it, *it) && right_turn(ring, it, strategy))
335 if (max_it == boost::end(ring))
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;
344 geometry::ever_circling_range_iterator<Ring const> left(ring);
345 geometry::ever_circling_range_iterator<Ring const> right(ring);
349 // Collect all points (often 3) in a temporary vector
350 std::vector<point_type> points;
352 if (! collect(ring, *max_it, points, left, right))
357 //std::cout << "Built vector of " << points.size() << std::endl;
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)
364 move_along_vector<Dimension>(points.front(), *(points.begin() + 1), base_value);
368 move_along_vector<Dimension>(points.back(), *(points.rbegin() + 1), base_value);
371 std::copy(points.begin(), points.end(), std::back_inserter(extremes));
373 get_intruders(ring, left, right, extremes, intruders, strategy);
383 }} // namespace detail::extreme_points
384 #endif // DOXYGEN_NO_DETAIL
387 #ifndef DOXYGEN_NO_DISPATCH
395 std::size_t Dimension,
396 typename GeometryTag = typename tag<Geometry>::type
398 struct extreme_points
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>
408 template<typename Polygon, std::size_t Dimension>
409 struct extreme_points<Polygon, Dimension, polygon_tag>
411 template <typename Extremes, typename Intruders, typename SideStrategy>
412 static inline bool apply(Polygon const& polygon, Extremes& extremes, Intruders& intruders,
413 SideStrategy const& strategy)
415 typedef typename geometry::ring_type<Polygon>::type ring_type;
416 typedef detail::extreme_points::extreme_points_on_ring
419 > ring_implementation;
421 if (! ring_implementation::apply(geometry::exterior_ring(polygon),
422 extremes, intruders, strategy))
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)
433 ring_implementation::get_intruders(*it, extremes, intruders, strategy);
440 template<typename Box>
441 struct extreme_points<Box, 1, box_tag>
443 template <typename Extremes, typename Intruders, typename SideStrategy>
444 static inline bool apply(Box const& box, Extremes& extremes, Intruders& ,
445 SideStrategy const& )
448 geometry::detail::assign_box_corners_oriented<false>(box, extremes);
449 // ll,ul,ur,lr, contains too exactly the right info
454 template<typename Box>
455 struct extreme_points<Box, 0, box_tag>
457 template <typename Extremes, typename Intruders, typename SideStrategy>
458 static inline bool apply(Box const& box, Extremes& extremes, Intruders& ,
459 SideStrategy const& )
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());
469 template<typename MultiPolygon, std::size_t Dimension>
470 struct extreme_points<MultiPolygon, Dimension, multi_polygon_tag>
472 template <typename Extremes, typename Intruders, typename SideStrategy>
473 static inline bool apply(MultiPolygon const& multi, Extremes& extremes,
474 Intruders& intruders, SideStrategy const& strategy)
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)
481 return extreme_points
483 typename boost::range_value<MultiPolygon const>::type,
486 >::apply(*boost::begin(multi), extremes, intruders, strategy);
493 } // namespace dispatch
494 #endif // DOXYGEN_NO_DISPATCH
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.
508 typename SideStrategy
510 inline bool extreme_points(Geometry const& geometry,
512 Intruders& intruders,
513 SideStrategy const& strategy)
515 concepts::check<Geometry const>();
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>();
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
525 typename boost::range_value
527 typename boost::range_value<Intruders>::type
532 return dispatch::extreme_points
536 >::apply(geometry, extremes, intruders, strategy);
547 inline bool extreme_points(Geometry const& geometry,
549 Intruders& intruders)
551 typedef typename strategy::side::services::default_strategy
553 typename cs_tag<Geometry>::type
554 >::type strategy_type;
556 return geometry::extreme_points<Edge>(geometry,extremes, intruders, strategy_type());
559 }} // namespace boost::geometry
562 #endif // BOOST_GEOMETRY_ALGORITHMS_DETAIL_EXTREME_POINTS_HPP