summaryrefslogtreecommitdiff
path: root/boost/geometry/algorithms/detail/envelope/multipoint.hpp
diff options
context:
space:
mode:
Diffstat (limited to 'boost/geometry/algorithms/detail/envelope/multipoint.hpp')
-rw-r--r--boost/geometry/algorithms/detail/envelope/multipoint.hpp378
1 files changed, 378 insertions, 0 deletions
diff --git a/boost/geometry/algorithms/detail/envelope/multipoint.hpp b/boost/geometry/algorithms/detail/envelope/multipoint.hpp
new file mode 100644
index 0000000000..210debfdba
--- /dev/null
+++ b/boost/geometry/algorithms/detail/envelope/multipoint.hpp
@@ -0,0 +1,378 @@
+// Boost.Geometry (aka GGL, Generic Geometry Library)
+
+// Copyright (c) 2015, Oracle and/or its affiliates.
+
+// Contributed and/or modified by Menelaos Karavelas, on behalf of Oracle
+
+// Distributed under the Boost Software License, Version 1.0.
+// (See accompanying file LICENSE_1_0.txt or copy at
+// http://www.boost.org/LICENSE_1_0.txt)
+
+#ifndef BOOST_GEOMETRY_ALGORITHMS_DETAIL_ENVELOPE_MULTIPOINT_HPP
+#define BOOST_GEOMETRY_ALGORITHMS_DETAIL_ENVELOPE_MULTIPOINT_HPP
+
+#include <cstddef>
+#include <algorithm>
+#include <utility>
+#include <vector>
+
+#include <boost/algorithm/minmax_element.hpp>
+#include <boost/range.hpp>
+
+#include <boost/geometry/core/access.hpp>
+#include <boost/geometry/core/assert.hpp>
+#include <boost/geometry/core/coordinate_system.hpp>
+#include <boost/geometry/core/coordinate_type.hpp>
+#include <boost/geometry/core/tags.hpp>
+
+#include <boost/geometry/util/math.hpp>
+#include <boost/geometry/util/range.hpp>
+
+#include <boost/geometry/geometries/helper_geometry.hpp>
+
+#include <boost/geometry/algorithms/detail/normalize.hpp>
+
+#include <boost/geometry/algorithms/detail/envelope/box.hpp>
+#include <boost/geometry/algorithms/detail/envelope/initialize.hpp>
+#include <boost/geometry/algorithms/detail/envelope/range.hpp>
+#include <boost/geometry/algorithms/detail/expand/point.hpp>
+
+#include <boost/geometry/algorithms/dispatch/envelope.hpp>
+
+
+namespace boost { namespace geometry
+{
+
+#ifndef DOXYGEN_NO_DETAIL
+namespace detail { namespace envelope
+{
+
+
+class envelope_multipoint_on_spheroid
+{
+private:
+ template <std::size_t Dim>
+ struct coordinate_less
+ {
+ template <typename Point>
+ inline bool operator()(Point const& point1, Point const& point2) const
+ {
+ return math::smaller(geometry::get<Dim>(point1),
+ geometry::get<Dim>(point2));
+ }
+ };
+
+ template <typename Constants, typename MultiPoint, typename OutputIterator>
+ static inline void analyze_point_coordinates(MultiPoint const& multipoint,
+ bool& has_south_pole,
+ bool& has_north_pole,
+ OutputIterator oit)
+ {
+ typedef typename boost::range_value<MultiPoint>::type point_type;
+ typedef typename boost::range_iterator
+ <
+ MultiPoint const
+ >::type iterator_type;
+
+ // analyze point coordinates:
+ // (1) normalize point coordinates
+ // (2) check if any point is the north or the south pole
+ // (3) put all non-pole points in a container
+ //
+ // notice that at this point in the algorithm, we have at
+ // least two points on the spheroid
+ has_south_pole = false;
+ has_north_pole = false;
+
+ for (iterator_type it = boost::begin(multipoint);
+ it != boost::end(multipoint);
+ ++it)
+ {
+ point_type point = detail::return_normalized<point_type>(*it);
+
+ if (math::equals(geometry::get<1>(point),
+ Constants::min_latitude()))
+ {
+ has_south_pole = true;
+ }
+ else if (math::equals(geometry::get<1>(point),
+ Constants::max_latitude()))
+ {
+ has_north_pole = true;
+ }
+ else
+ {
+ *oit++ = point;
+ }
+ }
+ }
+
+ template <typename SortedRange, typename Value>
+ static inline Value maximum_gap(SortedRange const& sorted_range,
+ Value& max_gap_left,
+ Value& max_gap_right)
+ {
+ typedef typename boost::range_iterator
+ <
+ SortedRange const
+ >::type iterator_type;
+
+ iterator_type it1 = boost::begin(sorted_range), it2 = it1;
+ ++it2;
+ max_gap_left = geometry::get<0>(*it1);
+ max_gap_right = geometry::get<0>(*it2);
+
+ Value max_gap = max_gap_right - max_gap_left;
+ for (++it1, ++it2; it2 != boost::end(sorted_range); ++it1, ++it2)
+ {
+ Value gap = geometry::get<0>(*it2) - geometry::get<0>(*it1);
+ if (math::larger(gap, max_gap))
+ {
+ max_gap_left = geometry::get<0>(*it1);
+ max_gap_right = geometry::get<0>(*it2);
+ max_gap = gap;
+ }
+ }
+
+ return max_gap;
+ }
+
+ template
+ <
+ typename Constants,
+ typename PointRange,
+ typename LongitudeLess,
+ typename CoordinateType
+ >
+ static inline void get_min_max_longitudes(PointRange& range,
+ LongitudeLess const& lon_less,
+ CoordinateType& lon_min,
+ CoordinateType& lon_max)
+ {
+ typedef typename boost::range_iterator
+ <
+ PointRange const
+ >::type iterator_type;
+
+ // compute min and max longitude values
+ std::pair<iterator_type, iterator_type> min_max_longitudes
+ = boost::minmax_element(boost::begin(range),
+ boost::end(range),
+ lon_less);
+
+ lon_min = geometry::get<0>(*min_max_longitudes.first);
+ lon_max = geometry::get<0>(*min_max_longitudes.second);
+
+ // if the longitude span is "large" compute the true maximum gap
+ if (math::larger(lon_max - lon_min, Constants::half_period()))
+ {
+ std::sort(boost::begin(range), boost::end(range), lon_less);
+
+ CoordinateType max_gap_left = 0, max_gap_right = 0;
+ CoordinateType max_gap
+ = maximum_gap(range, max_gap_left, max_gap_right);
+
+ CoordinateType complement_gap
+ = Constants::period() + lon_min - lon_max;
+
+ if (math::larger(max_gap, complement_gap))
+ {
+ lon_min = max_gap_right;
+ lon_max = max_gap_left + Constants::period();
+ }
+ }
+ }
+
+ template
+ <
+ typename Constants,
+ typename Iterator,
+ typename LatitudeLess,
+ typename CoordinateType
+ >
+ static inline void get_min_max_latitudes(Iterator const first,
+ Iterator const last,
+ LatitudeLess const& lat_less,
+ bool has_south_pole,
+ bool has_north_pole,
+ CoordinateType& lat_min,
+ CoordinateType& lat_max)
+ {
+ if (has_south_pole && has_north_pole)
+ {
+ lat_min = Constants::min_latitude();
+ lat_max = Constants::max_latitude();
+ }
+ else if (has_south_pole)
+ {
+ lat_min = Constants::min_latitude();
+ lat_max
+ = geometry::get<1>(*std::max_element(first, last, lat_less));
+ }
+ else if (has_north_pole)
+ {
+ lat_min
+ = geometry::get<1>(*std::min_element(first, last, lat_less));
+ lat_max = Constants::max_latitude();
+ }
+ else
+ {
+ std::pair<Iterator, Iterator> min_max_latitudes
+ = boost::minmax_element(first, last, lat_less);
+
+ lat_min = geometry::get<1>(*min_max_latitudes.first);
+ lat_max = geometry::get<1>(*min_max_latitudes.second);
+ }
+ }
+
+public:
+ template <typename MultiPoint, typename Box>
+ static inline void apply(MultiPoint const& multipoint, Box& mbr)
+ {
+ typedef typename point_type<MultiPoint>::type point_type;
+ typedef typename coordinate_type<MultiPoint>::type coordinate_type;
+ typedef typename boost::range_iterator
+ <
+ MultiPoint const
+ >::type iterator_type;
+
+ typedef math::detail::constants_on_spheroid
+ <
+ coordinate_type,
+ typename coordinate_system<MultiPoint>::type::units
+ > constants;
+
+ if (boost::empty(multipoint))
+ {
+ initialize<Box, 0, dimension<Box>::value>::apply(mbr);
+ return;
+ }
+
+ initialize<Box, 0, 2>::apply(mbr);
+
+ if (boost::size(multipoint) == 1)
+ {
+ return dispatch::envelope
+ <
+ typename boost::range_value<MultiPoint>::type
+ >::apply(range::front(multipoint), mbr);
+ }
+
+ // analyze the points and put the non-pole ones in the
+ // points vector
+ std::vector<point_type> points;
+ bool has_north_pole = false, has_south_pole = false;
+
+ analyze_point_coordinates<constants>(multipoint,
+ has_south_pole, has_north_pole,
+ std::back_inserter(points));
+
+ coordinate_type lon_min, lat_min, lon_max, lat_max;
+ if (points.size() == 1)
+ {
+ // we have one non-pole point and at least one pole point
+ lon_min = geometry::get<0>(range::front(points));
+ lon_max = geometry::get<0>(range::front(points));
+ lat_min = has_south_pole
+ ? constants::min_latitude()
+ : constants::max_latitude();
+ lat_max = has_north_pole
+ ? constants::max_latitude()
+ : constants::min_latitude();
+ }
+ else if (points.empty())
+ {
+ // all points are pole points
+ BOOST_GEOMETRY_ASSERT(has_south_pole || has_north_pole);
+ lon_min = coordinate_type(0);
+ lon_max = coordinate_type(0);
+ lat_min = has_south_pole
+ ? constants::min_latitude()
+ : constants::max_latitude();
+ lat_max = (has_north_pole)
+ ? constants::max_latitude()
+ : constants::min_latitude();
+ }
+ else
+ {
+ get_min_max_longitudes<constants>(points,
+ coordinate_less<0>(),
+ lon_min,
+ lon_max);
+
+ get_min_max_latitudes<constants>(points.begin(),
+ points.end(),
+ coordinate_less<1>(),
+ has_south_pole,
+ has_north_pole,
+ lat_min,
+ lat_max);
+ }
+
+ typedef typename helper_geometry
+ <
+ Box,
+ coordinate_type,
+ typename coordinate_system<MultiPoint>::type::units
+ >::type helper_box_type;
+
+ helper_box_type helper_mbr;
+
+ geometry::set<min_corner, 0>(helper_mbr, lon_min);
+ geometry::set<min_corner, 1>(helper_mbr, lat_min);
+ geometry::set<max_corner, 0>(helper_mbr, lon_max);
+ geometry::set<max_corner, 1>(helper_mbr, lat_max);
+
+ // now transform to output MBR (per index)
+ envelope_indexed_box_on_spheroid<min_corner, 2>::apply(helper_mbr, mbr);
+ envelope_indexed_box_on_spheroid<max_corner, 2>::apply(helper_mbr, mbr);
+
+ // compute envelope for higher coordinates
+ iterator_type it = boost::begin(multipoint);
+ envelope_one_point<2, dimension<Box>::value>::apply(*it, mbr);
+
+ for (++it; it != boost::end(multipoint); ++it)
+ {
+ detail::expand::point_loop
+ <
+ strategy::compare::default_strategy,
+ strategy::compare::default_strategy,
+ 2, dimension<Box>::value
+ >::apply(mbr, *it);
+ }
+ }
+};
+
+
+}} // namespace detail::envelope
+#endif // DOXYGEN_NO_DETAIL
+
+
+
+#ifndef DOXYGEN_NO_DISPATCH
+namespace dispatch
+{
+
+
+template <typename MultiPoint, typename CSTag>
+struct envelope<MultiPoint, multi_point_tag, CSTag>
+ : detail::envelope::envelope_range
+{};
+
+template <typename MultiPoint>
+struct envelope<MultiPoint, multi_point_tag, spherical_equatorial_tag>
+ : detail::envelope::envelope_multipoint_on_spheroid
+{};
+
+template <typename MultiPoint>
+struct envelope<MultiPoint, multi_point_tag, geographic_tag>
+ : detail::envelope::envelope_multipoint_on_spheroid
+{};
+
+
+} // namespace dispatch
+#endif // DOXYGEN_NO_DISPATCH
+
+}} // namespace boost::geometry
+
+#endif // BOOST_GEOMETRY_ALGORITHMS_DETAIL_ENVELOPE_MULTIPOINT_HPP