1 // Boost.Geometry (aka GGL, Generic Geometry Library)
3 // Copyright (c) 2015-2018, Oracle and/or its affiliates.
5 // Contributed and/or modified by Vissarion Fysikopoulos, on behalf of Oracle
6 // Contributed and/or modified by Menelaos Karavelas, on behalf of Oracle
7 // Contributed and/or modified by Adam Wulkiewicz, on behalf of Oracle
9 // Distributed under the Boost Software License, Version 1.0.
10 // (See accompanying file LICENSE_1_0.txt or copy at
11 // http://www.boost.org/LICENSE_1_0.txt)
13 #ifndef BOOST_GEOMETRY_STRATEGIES_SPHERICAL_ENVELOPE_MULTIPOINT_HPP
14 #define BOOST_GEOMETRY_STRATEGIES_SPHERICAL_ENVELOPE_MULTIPOINT_HPP
21 #include <boost/algorithm/minmax_element.hpp>
22 #include <boost/range.hpp>
24 #include <boost/geometry/core/access.hpp>
25 #include <boost/geometry/core/assert.hpp>
26 #include <boost/geometry/core/coordinate_system.hpp>
27 #include <boost/geometry/core/coordinate_type.hpp>
28 #include <boost/geometry/core/tags.hpp>
30 #include <boost/geometry/util/math.hpp>
31 #include <boost/geometry/util/range.hpp>
33 #include <boost/geometry/geometries/helper_geometry.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/strategies/cartesian/envelope_point.hpp>
41 #include <boost/geometry/strategies/normalize.hpp>
42 #include <boost/geometry/strategies/spherical/envelope_box.hpp>
43 #include <boost/geometry/strategies/spherical/envelope_point.hpp>
46 namespace boost { namespace geometry
49 namespace strategy { namespace envelope
52 class spherical_multipoint
55 template <std::size_t Dim>
56 struct coordinate_less
58 template <typename Point>
59 inline bool operator()(Point const& point1, Point const& point2) const
61 return math::smaller(geometry::get<Dim>(point1),
62 geometry::get<Dim>(point2));
66 template <typename Constants, typename MultiPoint, typename OutputIterator>
67 static inline void analyze_point_coordinates(MultiPoint const& multipoint,
72 typedef typename boost::range_value<MultiPoint>::type point_type;
73 typedef typename boost::range_iterator
76 >::type iterator_type;
78 // analyze point coordinates:
79 // (1) normalize point coordinates
80 // (2) check if any point is the north or the south pole
81 // (3) put all non-pole points in a container
83 // notice that at this point in the algorithm, we have at
84 // least two points on the spheroid
85 has_south_pole = false;
86 has_north_pole = false;
88 for (iterator_type it = boost::begin(multipoint);
89 it != boost::end(multipoint);
93 normalize::spherical_point::apply(*it, point);
95 if (math::equals(geometry::get<1>(point),
96 Constants::min_latitude()))
98 has_south_pole = true;
100 else if (math::equals(geometry::get<1>(point),
101 Constants::max_latitude()))
103 has_north_pole = true;
112 template <typename SortedRange, typename Value>
113 static inline Value maximum_gap(SortedRange const& sorted_range,
115 Value& max_gap_right)
117 typedef typename boost::range_iterator
120 >::type iterator_type;
122 iterator_type it1 = boost::begin(sorted_range), it2 = it1;
124 max_gap_left = geometry::get<0>(*it1);
125 max_gap_right = geometry::get<0>(*it2);
127 Value max_gap = max_gap_right - max_gap_left;
128 for (++it1, ++it2; it2 != boost::end(sorted_range); ++it1, ++it2)
130 Value gap = geometry::get<0>(*it2) - geometry::get<0>(*it1);
131 if (math::larger(gap, max_gap))
133 max_gap_left = geometry::get<0>(*it1);
134 max_gap_right = geometry::get<0>(*it2);
146 typename LongitudeLess,
147 typename CoordinateType
149 static inline void get_min_max_longitudes(PointRange& range,
150 LongitudeLess const& lon_less,
151 CoordinateType& lon_min,
152 CoordinateType& lon_max)
154 typedef typename boost::range_iterator
157 >::type iterator_type;
159 // compute min and max longitude values
160 std::pair<iterator_type, iterator_type> min_max_longitudes
161 = boost::minmax_element(boost::begin(range),
165 lon_min = geometry::get<0>(*min_max_longitudes.first);
166 lon_max = geometry::get<0>(*min_max_longitudes.second);
168 // if the longitude span is "large" compute the true maximum gap
169 if (math::larger(lon_max - lon_min, Constants::half_period()))
171 std::sort(boost::begin(range), boost::end(range), lon_less);
173 CoordinateType max_gap_left = 0, max_gap_right = 0;
174 CoordinateType max_gap
175 = maximum_gap(range, max_gap_left, max_gap_right);
177 CoordinateType complement_gap
178 = Constants::period() + lon_min - lon_max;
180 if (math::larger(max_gap, complement_gap))
182 lon_min = max_gap_right;
183 lon_max = max_gap_left + Constants::period();
192 typename LatitudeLess,
193 typename CoordinateType
195 static inline void get_min_max_latitudes(Iterator const first,
197 LatitudeLess const& lat_less,
200 CoordinateType& lat_min,
201 CoordinateType& lat_max)
203 if (has_south_pole && has_north_pole)
205 lat_min = Constants::min_latitude();
206 lat_max = Constants::max_latitude();
208 else if (has_south_pole)
210 lat_min = Constants::min_latitude();
212 = geometry::get<1>(*std::max_element(first, last, lat_less));
214 else if (has_north_pole)
217 = geometry::get<1>(*std::min_element(first, last, lat_less));
218 lat_max = Constants::max_latitude();
222 std::pair<Iterator, Iterator> min_max_latitudes
223 = boost::minmax_element(first, last, lat_less);
225 lat_min = geometry::get<1>(*min_max_latitudes.first);
226 lat_max = geometry::get<1>(*min_max_latitudes.second);
231 template <typename MultiPoint, typename Box>
232 static inline void apply(MultiPoint const& multipoint, Box& mbr)
234 typedef typename point_type<MultiPoint>::type point_type;
235 typedef typename coordinate_type<MultiPoint>::type coordinate_type;
236 typedef typename boost::range_iterator
239 >::type iterator_type;
241 typedef math::detail::constants_on_spheroid
244 typename geometry::detail::cs_angular_units<MultiPoint>::type
247 if (boost::empty(multipoint))
249 geometry::detail::envelope::initialize<Box, 0, dimension<Box>::value>::apply(mbr);
253 geometry::detail::envelope::initialize<Box, 0, 2>::apply(mbr);
255 if (boost::size(multipoint) == 1)
257 return dispatch::envelope
259 typename boost::range_value<MultiPoint>::type
260 >::apply(range::front(multipoint), mbr, strategy::envelope::spherical_point());
263 // analyze the points and put the non-pole ones in the
265 std::vector<point_type> points;
266 bool has_north_pole = false, has_south_pole = false;
268 analyze_point_coordinates<constants>(multipoint,
269 has_south_pole, has_north_pole,
270 std::back_inserter(points));
272 coordinate_type lon_min, lat_min, lon_max, lat_max;
273 if (points.size() == 1)
275 // we have one non-pole point and at least one pole point
276 lon_min = geometry::get<0>(range::front(points));
277 lon_max = geometry::get<0>(range::front(points));
278 lat_min = has_south_pole
279 ? constants::min_latitude()
280 : constants::max_latitude();
281 lat_max = has_north_pole
282 ? constants::max_latitude()
283 : constants::min_latitude();
285 else if (points.empty())
287 // all points are pole points
288 BOOST_GEOMETRY_ASSERT(has_south_pole || has_north_pole);
289 lon_min = coordinate_type(0);
290 lon_max = coordinate_type(0);
291 lat_min = has_south_pole
292 ? constants::min_latitude()
293 : constants::max_latitude();
294 lat_max = (has_north_pole)
295 ? constants::max_latitude()
296 : constants::min_latitude();
300 get_min_max_longitudes<constants>(points,
301 coordinate_less<0>(),
305 get_min_max_latitudes<constants>(points.begin(),
307 coordinate_less<1>(),
314 typedef typename helper_geometry
318 typename geometry::detail::cs_angular_units<MultiPoint>::type
319 >::type helper_box_type;
321 helper_box_type helper_mbr;
323 geometry::set<min_corner, 0>(helper_mbr, lon_min);
324 geometry::set<min_corner, 1>(helper_mbr, lat_min);
325 geometry::set<max_corner, 0>(helper_mbr, lon_max);
326 geometry::set<max_corner, 1>(helper_mbr, lat_max);
328 // now transform to output MBR (per index)
329 geometry::detail::envelope::envelope_indexed_box_on_spheroid<min_corner, 2>::apply(helper_mbr, mbr);
330 geometry::detail::envelope::envelope_indexed_box_on_spheroid<max_corner, 2>::apply(helper_mbr, mbr);
332 // compute envelope for higher coordinates
333 iterator_type it = boost::begin(multipoint);
334 geometry::detail::envelope::envelope_one_point<2, dimension<Box>::value>::apply(*it, mbr);
336 for (++it; it != boost::end(multipoint); ++it)
338 strategy::expand::detail::point_loop
340 2, dimension<Box>::value
347 #ifndef DOXYGEN_NO_STRATEGY_SPECIALIZATIONS
352 template <typename CalculationType>
353 struct default_strategy<multi_point_tag, spherical_equatorial_tag, CalculationType>
355 typedef strategy::envelope::spherical_multipoint type;
358 template <typename CalculationType>
359 struct default_strategy<multi_point_tag, spherical_polar_tag, CalculationType>
361 typedef strategy::envelope::spherical_multipoint type;
364 template <typename CalculationType>
365 struct default_strategy<multi_point_tag, geographic_tag, CalculationType>
367 typedef strategy::envelope::spherical_multipoint type;
370 } // namespace services
372 #endif // DOXYGEN_NO_STRATEGY_SPECIALIZATIONS
375 }} // namespace strategy::envelope
377 }} // namespace boost::geometry
379 #endif // BOOST_GEOMETRY_STRATEGIES_SPHERICAL_ENVELOPE_MULTIPOINT_HPP