1 // Boost.Geometry (aka GGL, Generic Geometry Library)
3 // Copyright (c) 2015, Oracle and/or its affiliates.
5 // Contributed and/or modified by Menelaos Karavelas, on behalf of Oracle
7 // Distributed under the Boost Software License, Version 1.0.
8 // (See accompanying file LICENSE_1_0.txt or copy at
9 // http://www.boost.org/LICENSE_1_0.txt)
11 #ifndef BOOST_GEOMETRY_ALGORITHMS_DETAIL_ENVELOPE_MULTIPOINT_HPP
12 #define BOOST_GEOMETRY_ALGORITHMS_DETAIL_ENVELOPE_MULTIPOINT_HPP
19 #include <boost/algorithm/minmax_element.hpp>
20 #include <boost/range.hpp>
22 #include <boost/geometry/core/access.hpp>
23 #include <boost/geometry/core/assert.hpp>
24 #include <boost/geometry/core/coordinate_system.hpp>
25 #include <boost/geometry/core/coordinate_type.hpp>
26 #include <boost/geometry/core/tags.hpp>
28 #include <boost/geometry/util/math.hpp>
29 #include <boost/geometry/util/range.hpp>
31 #include <boost/geometry/geometries/helper_geometry.hpp>
33 #include <boost/geometry/algorithms/detail/normalize.hpp>
35 #include <boost/geometry/algorithms/detail/envelope/box.hpp>
36 #include <boost/geometry/algorithms/detail/envelope/initialize.hpp>
37 #include <boost/geometry/algorithms/detail/envelope/range.hpp>
38 #include <boost/geometry/algorithms/detail/expand/point.hpp>
40 #include <boost/geometry/algorithms/dispatch/envelope.hpp>
43 namespace boost { namespace geometry
46 #ifndef DOXYGEN_NO_DETAIL
47 namespace detail { namespace envelope
51 class envelope_multipoint_on_spheroid
54 template <std::size_t Dim>
55 struct coordinate_less
57 template <typename Point>
58 inline bool operator()(Point const& point1, Point const& point2) const
60 return math::smaller(geometry::get<Dim>(point1),
61 geometry::get<Dim>(point2));
65 template <typename Constants, typename MultiPoint, typename OutputIterator>
66 static inline void analyze_point_coordinates(MultiPoint const& multipoint,
71 typedef typename boost::range_value<MultiPoint>::type point_type;
72 typedef typename boost::range_iterator
75 >::type iterator_type;
77 // analyze point coordinates:
78 // (1) normalize point coordinates
79 // (2) check if any point is the north or the south pole
80 // (3) put all non-pole points in a container
82 // notice that at this point in the algorithm, we have at
83 // least two points on the spheroid
84 has_south_pole = false;
85 has_north_pole = false;
87 for (iterator_type it = boost::begin(multipoint);
88 it != boost::end(multipoint);
91 point_type point = detail::return_normalized<point_type>(*it);
93 if (math::equals(geometry::get<1>(point),
94 Constants::min_latitude()))
96 has_south_pole = true;
98 else if (math::equals(geometry::get<1>(point),
99 Constants::max_latitude()))
101 has_north_pole = true;
110 template <typename SortedRange, typename Value>
111 static inline Value maximum_gap(SortedRange const& sorted_range,
113 Value& max_gap_right)
115 typedef typename boost::range_iterator
118 >::type iterator_type;
120 iterator_type it1 = boost::begin(sorted_range), it2 = it1;
122 max_gap_left = geometry::get<0>(*it1);
123 max_gap_right = geometry::get<0>(*it2);
125 Value max_gap = max_gap_right - max_gap_left;
126 for (++it1, ++it2; it2 != boost::end(sorted_range); ++it1, ++it2)
128 Value gap = geometry::get<0>(*it2) - geometry::get<0>(*it1);
129 if (math::larger(gap, max_gap))
131 max_gap_left = geometry::get<0>(*it1);
132 max_gap_right = geometry::get<0>(*it2);
144 typename LongitudeLess,
145 typename CoordinateType
147 static inline void get_min_max_longitudes(PointRange& range,
148 LongitudeLess const& lon_less,
149 CoordinateType& lon_min,
150 CoordinateType& lon_max)
152 typedef typename boost::range_iterator
155 >::type iterator_type;
157 // compute min and max longitude values
158 std::pair<iterator_type, iterator_type> min_max_longitudes
159 = boost::minmax_element(boost::begin(range),
163 lon_min = geometry::get<0>(*min_max_longitudes.first);
164 lon_max = geometry::get<0>(*min_max_longitudes.second);
166 // if the longitude span is "large" compute the true maximum gap
167 if (math::larger(lon_max - lon_min, Constants::half_period()))
169 std::sort(boost::begin(range), boost::end(range), lon_less);
171 CoordinateType max_gap_left = 0, max_gap_right = 0;
172 CoordinateType max_gap
173 = maximum_gap(range, max_gap_left, max_gap_right);
175 CoordinateType complement_gap
176 = Constants::period() + lon_min - lon_max;
178 if (math::larger(max_gap, complement_gap))
180 lon_min = max_gap_right;
181 lon_max = max_gap_left + Constants::period();
190 typename LatitudeLess,
191 typename CoordinateType
193 static inline void get_min_max_latitudes(Iterator const first,
195 LatitudeLess const& lat_less,
198 CoordinateType& lat_min,
199 CoordinateType& lat_max)
201 if (has_south_pole && has_north_pole)
203 lat_min = Constants::min_latitude();
204 lat_max = Constants::max_latitude();
206 else if (has_south_pole)
208 lat_min = Constants::min_latitude();
210 = geometry::get<1>(*std::max_element(first, last, lat_less));
212 else if (has_north_pole)
215 = geometry::get<1>(*std::min_element(first, last, lat_less));
216 lat_max = Constants::max_latitude();
220 std::pair<Iterator, Iterator> min_max_latitudes
221 = boost::minmax_element(first, last, lat_less);
223 lat_min = geometry::get<1>(*min_max_latitudes.first);
224 lat_max = geometry::get<1>(*min_max_latitudes.second);
229 template <typename MultiPoint, typename Box>
230 static inline void apply(MultiPoint const& multipoint, Box& mbr)
232 typedef typename point_type<MultiPoint>::type point_type;
233 typedef typename coordinate_type<MultiPoint>::type coordinate_type;
234 typedef typename boost::range_iterator
237 >::type iterator_type;
239 typedef math::detail::constants_on_spheroid
242 typename coordinate_system<MultiPoint>::type::units
245 if (boost::empty(multipoint))
247 initialize<Box, 0, dimension<Box>::value>::apply(mbr);
251 initialize<Box, 0, 2>::apply(mbr);
253 if (boost::size(multipoint) == 1)
255 return dispatch::envelope
257 typename boost::range_value<MultiPoint>::type
258 >::apply(range::front(multipoint), mbr);
261 // analyze the points and put the non-pole ones in the
263 std::vector<point_type> points;
264 bool has_north_pole = false, has_south_pole = false;
266 analyze_point_coordinates<constants>(multipoint,
267 has_south_pole, has_north_pole,
268 std::back_inserter(points));
270 coordinate_type lon_min, lat_min, lon_max, lat_max;
271 if (points.size() == 1)
273 // we have one non-pole point and at least one pole point
274 lon_min = geometry::get<0>(range::front(points));
275 lon_max = geometry::get<0>(range::front(points));
276 lat_min = has_south_pole
277 ? constants::min_latitude()
278 : constants::max_latitude();
279 lat_max = has_north_pole
280 ? constants::max_latitude()
281 : constants::min_latitude();
283 else if (points.empty())
285 // all points are pole points
286 BOOST_GEOMETRY_ASSERT(has_south_pole || has_north_pole);
287 lon_min = coordinate_type(0);
288 lon_max = coordinate_type(0);
289 lat_min = has_south_pole
290 ? constants::min_latitude()
291 : constants::max_latitude();
292 lat_max = (has_north_pole)
293 ? constants::max_latitude()
294 : constants::min_latitude();
298 get_min_max_longitudes<constants>(points,
299 coordinate_less<0>(),
303 get_min_max_latitudes<constants>(points.begin(),
305 coordinate_less<1>(),
312 typedef typename helper_geometry
316 typename coordinate_system<MultiPoint>::type::units
317 >::type helper_box_type;
319 helper_box_type helper_mbr;
321 geometry::set<min_corner, 0>(helper_mbr, lon_min);
322 geometry::set<min_corner, 1>(helper_mbr, lat_min);
323 geometry::set<max_corner, 0>(helper_mbr, lon_max);
324 geometry::set<max_corner, 1>(helper_mbr, lat_max);
326 // now transform to output MBR (per index)
327 envelope_indexed_box_on_spheroid<min_corner, 2>::apply(helper_mbr, mbr);
328 envelope_indexed_box_on_spheroid<max_corner, 2>::apply(helper_mbr, mbr);
330 // compute envelope for higher coordinates
331 iterator_type it = boost::begin(multipoint);
332 envelope_one_point<2, dimension<Box>::value>::apply(*it, mbr);
334 for (++it; it != boost::end(multipoint); ++it)
336 detail::expand::point_loop
338 strategy::compare::default_strategy,
339 strategy::compare::default_strategy,
340 2, dimension<Box>::value
347 }} // namespace detail::envelope
348 #endif // DOXYGEN_NO_DETAIL
352 #ifndef DOXYGEN_NO_DISPATCH
357 template <typename MultiPoint, typename CSTag>
358 struct envelope<MultiPoint, multi_point_tag, CSTag>
359 : detail::envelope::envelope_range
362 template <typename MultiPoint>
363 struct envelope<MultiPoint, multi_point_tag, spherical_equatorial_tag>
364 : detail::envelope::envelope_multipoint_on_spheroid
367 template <typename MultiPoint>
368 struct envelope<MultiPoint, multi_point_tag, geographic_tag>
369 : detail::envelope::envelope_multipoint_on_spheroid
373 } // namespace dispatch
374 #endif // DOXYGEN_NO_DISPATCH
376 }} // namespace boost::geometry
378 #endif // BOOST_GEOMETRY_ALGORITHMS_DETAIL_ENVELOPE_MULTIPOINT_HPP