[ceph.git] / ceph / src / boost / libs / geometry / include / boost / geometry / algorithms / detail / envelope / multipoint.hpp

// 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
Commit	Line	Data
7c673cae FG	1	// Boost.Geometry (aka GGL, Generic Geometry Library)
	2
	3	// Copyright (c) 2015, Oracle and/or its affiliates.
	4
	5	// Contributed and/or modified by Menelaos Karavelas, on behalf of Oracle
	6
	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)
	10
	11	#ifndef BOOST_GEOMETRY_ALGORITHMS_DETAIL_ENVELOPE_MULTIPOINT_HPP
	12	#define BOOST_GEOMETRY_ALGORITHMS_DETAIL_ENVELOPE_MULTIPOINT_HPP
	13
	14	#include <cstddef>
	15	#include <algorithm>
	16	#include <utility>
	17	#include <vector>
	18
	19	#include <boost/algorithm/minmax_element.hpp>
	20	#include <boost/range.hpp>
	21
	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>
	27
	28	#include <boost/geometry/util/math.hpp>
	29	#include <boost/geometry/util/range.hpp>
	30
	31	#include <boost/geometry/geometries/helper_geometry.hpp>
	32
	33	#include <boost/geometry/algorithms/detail/normalize.hpp>
	34
	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>
	39
	40	#include <boost/geometry/algorithms/dispatch/envelope.hpp>
	41
	42
	43	namespace boost { namespace geometry
	44	{
	45
	46	#ifndef DOXYGEN_NO_DETAIL
	47	namespace detail { namespace envelope
	48	{
	49
	50
	51	class envelope_multipoint_on_spheroid
	52	{
	53	private:
	54	template <std::size_t Dim>
	55	struct coordinate_less
	56	{
	57	template <typename Point>
	58	inline bool operator()(Point const& point1, Point const& point2) const
	59	{
	60	return math::smaller(geometry::get<Dim>(point1),
	61	geometry::get<Dim>(point2));
	62	}
	63	};
	64
65	template <typename Constants, typename MultiPoint, typename OutputIterator>
66	static inline void analyze_point_coordinates(MultiPoint const& multipoint,
67	bool& has_south_pole,
68	bool& has_north_pole,
69	OutputIterator oit)
70	{
71	typedef typename boost::range_value<MultiPoint>::type point_type;
72	typedef typename boost::range_iterator
73	<
74	MultiPoint const
75	>::type iterator_type;
76
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
81	//
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;
86
87	for (iterator_type it = boost::begin(multipoint);
88	it != boost::end(multipoint);
89	++it)
90	{
91	point_type point = detail::return_normalized<point_type>(*it);
92
93	if (math::equals(geometry::get<1>(point),
94	Constants::min_latitude()))
95	{
96	has_south_pole = true;
97	}
98	else if (math::equals(geometry::get<1>(point),
99	Constants::max_latitude()))
100	{
101	has_north_pole = true;
102	}
103	else
104	{
105	*oit++ = point;
106	}
107	}
108	}
109
110	template <typename SortedRange, typename Value>
111	static inline Value maximum_gap(SortedRange const& sorted_range,
112	Value& max_gap_left,
113	Value& max_gap_right)
114	{
115	typedef typename boost::range_iterator
116	<
117	SortedRange const
118	>::type iterator_type;
119
120	iterator_type it1 = boost::begin(sorted_range), it2 = it1;
121	++it2;
122	max_gap_left = geometry::get<0>(*it1);
123	max_gap_right = geometry::get<0>(*it2);
124
125	Value max_gap = max_gap_right - max_gap_left;
126	for (++it1, ++it2; it2 != boost::end(sorted_range); ++it1, ++it2)
127	{
128	Value gap = geometry::get<0>(it2) - geometry::get<0>(it1);
129	if (math::larger(gap, max_gap))
130	{
131	max_gap_left = geometry::get<0>(*it1);
132	max_gap_right = geometry::get<0>(*it2);
133	max_gap = gap;
134	}
135	}
136
137	return max_gap;
138	}
139
140	template
141	<
142	typename Constants,
143	typename PointRange,
144	typename LongitudeLess,
145	typename CoordinateType
146	>
147	static inline void get_min_max_longitudes(PointRange& range,
148	LongitudeLess const& lon_less,
149	CoordinateType& lon_min,
150	CoordinateType& lon_max)
151	{
152	typedef typename boost::range_iterator
153	<
154	PointRange const
155	>::type iterator_type;
156
157	// compute min and max longitude values
158	std::pair<iterator_type, iterator_type> min_max_longitudes
159	= boost::minmax_element(boost::begin(range),
160	boost::end(range),
161	lon_less);
162
163	lon_min = geometry::get<0>(*min_max_longitudes.first);
164	lon_max = geometry::get<0>(*min_max_longitudes.second);
165
166	// if the longitude span is "large" compute the true maximum gap
167	if (math::larger(lon_max - lon_min, Constants::half_period()))
168	{
169	std::sort(boost::begin(range), boost::end(range), lon_less);
170
171	CoordinateType max_gap_left = 0, max_gap_right = 0;
172	CoordinateType max_gap
173	= maximum_gap(range, max_gap_left, max_gap_right);
174
175	CoordinateType complement_gap
176	= Constants::period() + lon_min - lon_max;
177
178	if (math::larger(max_gap, complement_gap))
179	{
180	lon_min = max_gap_right;
181	lon_max = max_gap_left + Constants::period();
182	}
183	}
184	}
185
186	template
187	<
188	typename Constants,
189	typename Iterator,
190	typename LatitudeLess,
191	typename CoordinateType
192	>
193	static inline void get_min_max_latitudes(Iterator const first,
194	Iterator const last,
195	LatitudeLess const& lat_less,
196	bool has_south_pole,
197	bool has_north_pole,
198	CoordinateType& lat_min,
199	CoordinateType& lat_max)
200	{
201	if (has_south_pole && has_north_pole)
202	{
203	lat_min = Constants::min_latitude();
204	lat_max = Constants::max_latitude();
205	}
206	else if (has_south_pole)
207	{
208	lat_min = Constants::min_latitude();
209	lat_max
210	= geometry::get<1>(*std::max_element(first, last, lat_less));
211	}
212	else if (has_north_pole)
213	{
214	lat_min
215	= geometry::get<1>(*std::min_element(first, last, lat_less));
216	lat_max = Constants::max_latitude();
217	}
218	else
219	{
220	std::pair<Iterator, Iterator> min_max_latitudes
221	= boost::minmax_element(first, last, lat_less);
222
223	lat_min = geometry::get<1>(*min_max_latitudes.first);
224	lat_max = geometry::get<1>(*min_max_latitudes.second);
225	}
226	}
227
228	public:
229	template <typename MultiPoint, typename Box>
230	static inline void apply(MultiPoint const& multipoint, Box& mbr)
231	{
232	typedef typename point_type<MultiPoint>::type point_type;
233	typedef typename coordinate_type<MultiPoint>::type coordinate_type;
234	typedef typename boost::range_iterator
235	<
236	MultiPoint const
237	>::type iterator_type;
238
239	typedef math::detail::constants_on_spheroid
240	<
241	coordinate_type,
242	typename coordinate_system<MultiPoint>::type::units
243	> constants;
244
245	if (boost::empty(multipoint))
246	{
247	initialize<Box, 0, dimension<Box>::value>::apply(mbr);
248	return;
249	}
250
251	initialize<Box, 0, 2>::apply(mbr);
252
253	if (boost::size(multipoint) == 1)
254	{
255	return dispatch::envelope
256	<
257	typename boost::range_value<MultiPoint>::type
258	>::apply(range::front(multipoint), mbr);
259	}
260
261	// analyze the points and put the non-pole ones in the
262	// points vector
263	std::vector<point_type> points;
264	bool has_north_pole = false, has_south_pole = false;
265
266	analyze_point_coordinates<constants>(multipoint,
267	has_south_pole, has_north_pole,
268	std::back_inserter(points));
269
270	coordinate_type lon_min, lat_min, lon_max, lat_max;
271	if (points.size() == 1)
272	{
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();
282	}
283	else if (points.empty())
284	{
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();
295	}
296	else
297	{
298	get_min_max_longitudes<constants>(points,
299	coordinate_less<0>(),
300	lon_min,
301	lon_max);
302
303	get_min_max_latitudes<constants>(points.begin(),
304	points.end(),
305	coordinate_less<1>(),
306	has_south_pole,
307	has_north_pole,
308	lat_min,
309	lat_max);
310	}
311
312	typedef typename helper_geometry
313	<
314	Box,
315	coordinate_type,
316	typename coordinate_system<MultiPoint>::type::units
317	>::type helper_box_type;
318
319	helper_box_type helper_mbr;
320
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);
325
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);
329
330	// compute envelope for higher coordinates
331	iterator_type it = boost::begin(multipoint);
332	envelope_one_point<2, dimension<Box>::value>::apply(*it, mbr);
333
334	for (++it; it != boost::end(multipoint); ++it)
335	{
336	detail::expand::point_loop
337	<
338	strategy::compare::default_strategy,
339	strategy::compare::default_strategy,
340	2, dimension<Box>::value
341	>::apply(mbr, *it);
342	}
343	}
344	};
345
346
347	}} // namespace detail::envelope
348	#endif // DOXYGEN_NO_DETAIL
349
350
351
352	#ifndef DOXYGEN_NO_DISPATCH
353	namespace dispatch
354	{
355
356
357	template <typename MultiPoint, typename CSTag>
358	struct envelope<MultiPoint, multi_point_tag, CSTag>
359	: detail::envelope::envelope_range
360	{};
361
362	template <typename MultiPoint>
363	struct envelope<MultiPoint, multi_point_tag, spherical_equatorial_tag>
364	: detail::envelope::envelope_multipoint_on_spheroid
365	{};
366
367	template <typename MultiPoint>
368	struct envelope<MultiPoint, multi_point_tag, geographic_tag>
369	: detail::envelope::envelope_multipoint_on_spheroid
370	{};
371
372
373	} // namespace dispatch
374	#endif // DOXYGEN_NO_DISPATCH
375
376	}} // namespace boost::geometry
377
378	#endif // BOOST_GEOMETRY_ALGORITHMS_DETAIL_ENVELOPE_MULTIPOINT_HPP