diff options
Diffstat (limited to 'boost/geometry/algorithms/detail/envelope')
12 files changed, 2158 insertions, 0 deletions
diff --git a/boost/geometry/algorithms/detail/envelope/box.hpp b/boost/geometry/algorithms/detail/envelope/box.hpp new file mode 100644 index 0000000000..3790262948 --- /dev/null +++ b/boost/geometry/algorithms/detail/envelope/box.hpp @@ -0,0 +1,167 @@ +// Boost.Geometry (aka GGL, Generic Geometry Library) + +// Copyright (c) 2007-2015 Barend Gehrels, Amsterdam, the Netherlands. +// Copyright (c) 2008-2015 Bruno Lalande, Paris, France. +// Copyright (c) 2009-2015 Mateusz Loskot, London, UK. + +// This file was modified by Oracle on 2015. +// Modifications 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_BOX_HPP +#define BOOST_GEOMETRY_ALGORITHMS_DETAIL_ENVELOPE_BOX_HPP + +#include <cstddef> + +#include <boost/geometry/core/cs.hpp> +#include <boost/geometry/core/coordinate_dimension.hpp> +#include <boost/geometry/core/coordinate_system.hpp> +#include <boost/geometry/core/tags.hpp> + +#include <boost/geometry/views/detail/indexed_point_view.hpp> + +#include <boost/geometry/algorithms/detail/convert_point_to_point.hpp> +#include <boost/geometry/algorithms/detail/normalize.hpp> +#include <boost/geometry/algorithms/detail/envelope/transform_units.hpp> + +#include <boost/geometry/algorithms/dispatch/envelope.hpp> + + +namespace boost { namespace geometry +{ + +#ifndef DOXYGEN_NO_DETAIL +namespace detail { namespace envelope +{ + + +template +< + std::size_t Index, + std::size_t Dimension, + std::size_t DimensionCount +> +struct envelope_indexed_box +{ + template <typename BoxIn, typename BoxOut> + static inline void apply(BoxIn const& box_in, BoxOut& mbr) + { + detail::indexed_point_view<BoxIn const, Index> box_in_corner(box_in); + detail::indexed_point_view<BoxOut, Index> mbr_corner(mbr); + + detail::conversion::point_to_point + < + detail::indexed_point_view<BoxIn const, Index>, + detail::indexed_point_view<BoxOut, Index>, + Dimension, + DimensionCount + >::apply(box_in_corner, mbr_corner); + } +}; + +template +< + std::size_t Index, + std::size_t DimensionCount +> +struct envelope_indexed_box_on_spheroid +{ + template <typename BoxIn, typename BoxOut> + static inline void apply(BoxIn const& box_in, BoxOut& mbr) + { + // transform() does not work with boxes of dimension higher + // than 2; to account for such boxes we transform the min/max + // points of the boxes using the indexed_point_view + detail::indexed_point_view<BoxIn const, Index> box_in_corner(box_in); + detail::indexed_point_view<BoxOut, Index> mbr_corner(mbr); + + // first transform the units + transform_units(box_in_corner, mbr_corner); + + // now transform the remaining coordinates + detail::conversion::point_to_point + < + detail::indexed_point_view<BoxIn const, Index>, + detail::indexed_point_view<BoxOut, Index>, + 2, + DimensionCount + >::apply(box_in_corner, mbr_corner); + } +}; + + +struct envelope_box +{ + template<typename BoxIn, typename BoxOut> + static inline void apply(BoxIn const& box_in, BoxOut& mbr) + { + envelope_indexed_box + < + min_corner, 0, dimension<BoxIn>::value + >::apply(box_in, mbr); + + envelope_indexed_box + < + max_corner, 0, dimension<BoxIn>::value + >::apply(box_in, mbr); + } +}; + + +struct envelope_box_on_spheroid +{ + template <typename BoxIn, typename BoxOut> + static inline void apply(BoxIn const& box_in, BoxOut& mbr) + { + BoxIn box_in_normalized = detail::return_normalized<BoxIn>(box_in); + + envelope_indexed_box_on_spheroid + < + min_corner, dimension<BoxIn>::value + >::apply(box_in_normalized, mbr); + + envelope_indexed_box_on_spheroid + < + max_corner, dimension<BoxIn>::value + >::apply(box_in_normalized, mbr); + } +}; + + +}} // namespace detail::envelope +#endif // DOXYGEN_NO_DETAIL + +#ifndef DOXYGEN_NO_DISPATCH +namespace dispatch +{ + + +template <typename Box, typename CS_Tag> +struct envelope<Box, box_tag, CS_Tag> + : detail::envelope::envelope_box +{}; + + +template <typename Box> +struct envelope<Box, box_tag, spherical_equatorial_tag> + : detail::envelope::envelope_box_on_spheroid +{}; + + +template <typename Box> +struct envelope<Box, box_tag, geographic_tag> + : detail::envelope::envelope_box_on_spheroid +{}; + + +} // namespace dispatch +#endif // DOXYGEN_NO_DISPATCH + +}} // namespace boost::geometry + +#endif // BOOST_GEOMETRY_ALGORITHMS_DETAIL_ENVELOPE_BOX_HPP diff --git a/boost/geometry/algorithms/detail/envelope/implementation.hpp b/boost/geometry/algorithms/detail/envelope/implementation.hpp new file mode 100644 index 0000000000..c1dbf8e589 --- /dev/null +++ b/boost/geometry/algorithms/detail/envelope/implementation.hpp @@ -0,0 +1,106 @@ +// Boost.Geometry (aka GGL, Generic Geometry Library) + +// Copyright (c) 2007-2015 Barend Gehrels, Amsterdam, the Netherlands. +// Copyright (c) 2008-2015 Bruno Lalande, Paris, France. +// Copyright (c) 2009-2015 Mateusz Loskot, London, UK. + +// This file was modified by Oracle on 2015. +// Modifications copyright (c) 2015, Oracle and/or its affiliates. + +// Contributed and/or modified by Menelaos Karavelas, on behalf of Oracle + +// Parts of Boost.Geometry are redesigned from Geodan's Geographic Library +// (geolib/GGL), copyright (c) 1995-2010 Geodan, Amsterdam, the Netherlands. + +// 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_IMPLEMENTATION_HPP +#define BOOST_GEOMETRY_ALGORITHMS_DETAIL_ENVELOPE_IMPLEMENTATION_HPP + +#include <boost/geometry/core/exterior_ring.hpp> +#include <boost/geometry/core/interior_rings.hpp> +#include <boost/geometry/core/tags.hpp> + +#include <boost/geometry/algorithms/is_empty.hpp> + +#include <boost/geometry/algorithms/detail/envelope/box.hpp> +#include <boost/geometry/algorithms/detail/envelope/linear.hpp> +#include <boost/geometry/algorithms/detail/envelope/multipoint.hpp> +#include <boost/geometry/algorithms/detail/envelope/point.hpp> +#include <boost/geometry/algorithms/detail/envelope/range.hpp> +#include <boost/geometry/algorithms/detail/envelope/segment.hpp> + +#include <boost/geometry/algorithms/dispatch/envelope.hpp> + + +namespace boost { namespace geometry +{ + +#ifndef DOXYGEN_NO_DETAIL +namespace detail { namespace envelope +{ + + +struct envelope_polygon +{ + template <typename Polygon, typename Box> + static inline void apply(Polygon const& polygon, Box& mbr) + { + typename ring_return_type<Polygon const>::type ext_ring + = exterior_ring(polygon); + + if (geometry::is_empty(ext_ring)) + { + // if the exterior ring is empty, consider the interior rings + envelope_multi_range + < + envelope_range + >::apply(interior_rings(polygon), mbr); + } + else + { + // otherwise, consider only the exterior ring + envelope_range::apply(ext_ring, mbr); + } + } +}; + + +}} // namespace detail::envelope +#endif // DOXYGEN_NO_DETAIL + +#ifndef DOXYGEN_NO_DISPATCH +namespace dispatch +{ + + +template <typename Ring> +struct envelope<Ring, ring_tag> + : detail::envelope::envelope_range +{}; + + +template <typename Polygon> +struct envelope<Polygon, polygon_tag> + : detail::envelope::envelope_polygon +{}; + + +template <typename MultiPolygon> +struct envelope<MultiPolygon, multi_polygon_tag> + : detail::envelope::envelope_multi_range + < + detail::envelope::envelope_polygon + > +{}; + + +} // namespace dispatch +#endif // DOXYGEN_NO_DISPATCH + + +}} // namespace boost::geometry + +#endif // BOOST_GEOMETRY_ALGORITHMS_DETAIL_ENVELOPE_IMPLEMENTATION_HPP diff --git a/boost/geometry/algorithms/detail/envelope/initialize.hpp b/boost/geometry/algorithms/detail/envelope/initialize.hpp new file mode 100644 index 0000000000..d8e252b53a --- /dev/null +++ b/boost/geometry/algorithms/detail/envelope/initialize.hpp @@ -0,0 +1,86 @@ +// 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_INITIALIZE_HPP +#define BOOST_GEOMETRY_ALGORITHMS_DETAIL_ENVELOPE_INITIALIZE_HPP + +#include <cstddef> + +#include <boost/numeric/conversion/bounds.hpp> + +#include <boost/geometry/core/access.hpp> +#include <boost/geometry/core/coordinate_dimension.hpp> +#include <boost/geometry/core/coordinate_type.hpp> + + +namespace boost { namespace geometry +{ + +#ifndef DOXYGEN_NO_DETAIL +namespace detail { namespace envelope +{ + +template <std::size_t Dimension, std::size_t DimensionCount> +struct initialize_loop +{ + template <typename Box, typename CoordinateType> + static inline void apply(Box& box, + CoordinateType min_value, + CoordinateType max_value) + { + geometry::set<min_corner, Dimension>(box, min_value); + geometry::set<max_corner, Dimension>(box, max_value); + + initialize_loop + < + Dimension + 1, DimensionCount + >::apply(box, min_value, max_value); + } +}; + +template <std::size_t DimensionCount> +struct initialize_loop<DimensionCount, DimensionCount> +{ + template <typename Box, typename CoordinateType> + static inline void apply(Box&, CoordinateType, CoordinateType) + { + } +}; + + +template +< + typename Box, + std::size_t Dimension = 0, + std::size_t DimensionCount = dimension<Box>::value +> +struct initialize +{ + typedef typename coordinate_type<Box>::type coordinate_type; + + static inline void apply(Box& box, + coordinate_type min_value + = boost::numeric::bounds<coordinate_type>::highest(), + coordinate_type max_value + = boost::numeric::bounds<coordinate_type>::lowest()) + { + initialize_loop + < + Dimension, DimensionCount + >::apply(box, min_value, max_value); + } +}; + +}} // namespace detail::envelope +#endif // DOXYGEN_NO_DETAIL + +}} // namespace boost::geometry + +#endif // BOOST_GEOMETRY_ALGORITHMS_DETAIL_ENVELOPE_INITIALIZE_HPP diff --git a/boost/geometry/algorithms/detail/envelope/interface.hpp b/boost/geometry/algorithms/detail/envelope/interface.hpp new file mode 100644 index 0000000000..997ac1b23e --- /dev/null +++ b/boost/geometry/algorithms/detail/envelope/interface.hpp @@ -0,0 +1,126 @@ +// Boost.Geometry (aka GGL, Generic Geometry Library) + +// Copyright (c) 2007-2015 Barend Gehrels, Amsterdam, the Netherlands. +// Copyright (c) 2008-2015 Bruno Lalande, Paris, France. +// Copyright (c) 2009-2015 Mateusz Loskot, London, UK. + +// This file was modified by Oracle on 2015. +// Modifications copyright (c) 2015, Oracle and/or its affiliates. + +// Contributed and/or modified by Menelaos Karavelas, on behalf of Oracle + +// Parts of Boost.Geometry are redesigned from Geodan's Geographic Library +// (geolib/GGL), copyright (c) 1995-2010 Geodan, Amsterdam, the Netherlands. + +// 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_INTERFACE_HPP +#define BOOST_GEOMETRY_ALGORITHMS_DETAIL_ENVELOPE_INTERFACE_HPP + +#include <boost/variant/apply_visitor.hpp> +#include <boost/variant/static_visitor.hpp> +#include <boost/variant/variant_fwd.hpp> + +#include <boost/geometry/geometries/concepts/check.hpp> + +#include <boost/geometry/algorithms/dispatch/envelope.hpp> + + +namespace boost { namespace geometry +{ + +namespace resolve_variant +{ + +template <typename Geometry> +struct envelope +{ + template <typename Box> + static inline void apply(Geometry const& geometry, Box& box) + { + concept::check<Geometry const>(); + concept::check<Box>(); + + dispatch::envelope<Geometry>::apply(geometry, box); + } +}; + +template <BOOST_VARIANT_ENUM_PARAMS(typename T)> +struct envelope<boost::variant<BOOST_VARIANT_ENUM_PARAMS(T)> > +{ + template <typename Box> + struct visitor: boost::static_visitor<void> + { + Box& m_box; + + visitor(Box& box): m_box(box) {} + + template <typename Geometry> + void operator()(Geometry const& geometry) const + { + envelope<Geometry>::apply(geometry, m_box); + } + }; + + template <typename Box> + static inline void + apply(boost::variant<BOOST_VARIANT_ENUM_PARAMS(T)> const& geometry, + Box& box) + { + boost::apply_visitor(visitor<Box>(box), geometry); + } +}; + +} // namespace resolve_variant + + +/*! +\brief \brief_calc{envelope} +\ingroup envelope +\details \details_calc{envelope,\det_envelope}. +\tparam Geometry \tparam_geometry +\tparam Box \tparam_box +\param geometry \param_geometry +\param mbr \param_box \param_set{envelope} + +\qbk{[include reference/algorithms/envelope.qbk]} +\qbk{ +[heading Example] +[envelope] [envelope_output] +} +*/ +template<typename Geometry, typename Box> +inline void envelope(Geometry const& geometry, Box& mbr) +{ + resolve_variant::envelope<Geometry>::apply(geometry, mbr); +} + + +/*! +\brief \brief_calc{envelope} +\ingroup envelope +\details \details_calc{return_envelope,\det_envelope}. \details_return{envelope} +\tparam Box \tparam_box +\tparam Geometry \tparam_geometry +\param geometry \param_geometry +\return \return_calc{envelope} + +\qbk{[include reference/algorithms/envelope.qbk]} +\qbk{ +[heading Example] +[return_envelope] [return_envelope_output] +} +*/ +template<typename Box, typename Geometry> +inline Box return_envelope(Geometry const& geometry) +{ + Box mbr; + resolve_variant::envelope<Geometry>::apply(geometry, mbr); + return mbr; +} + +}} // namespace boost::geometry + +#endif // BOOST_GEOMETRY_ALGORITHMS_DETAIL_ENVELOPE_INTERFACE_HPP diff --git a/boost/geometry/algorithms/detail/envelope/intersects_antimeridian.hpp b/boost/geometry/algorithms/detail/envelope/intersects_antimeridian.hpp new file mode 100644 index 0000000000..47937bf740 --- /dev/null +++ b/boost/geometry/algorithms/detail/envelope/intersects_antimeridian.hpp @@ -0,0 +1,78 @@ +// 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_INTERSECTS_ANTIMERIDIAN_HPP +#define BOOST_GEOMETRY_ALGORITHMS_DETAIL_ENVELOPE_INTERSECTS_ANTIMERIDIAN_HPP + +#include <boost/geometry/core/access.hpp> +#include <boost/geometry/core/coordinate_system.hpp> + +#include <boost/geometry/util/math.hpp> + +#include <boost/geometry/algorithms/detail/normalize.hpp> + + +namespace boost { namespace geometry +{ + +namespace detail { namespace envelope +{ + + +struct intersects_antimeridian +{ + template <typename Units, typename CoordinateType> + static inline bool apply(CoordinateType const& lon1, + CoordinateType const& lat1, + CoordinateType const& lon2, + CoordinateType const& lat2) + { + typedef math::detail::constants_on_spheroid + < + CoordinateType, Units + > constants; + + return + math::equals(math::abs(lat1), constants::max_latitude()) + || + math::equals(math::abs(lat2), constants::max_latitude()) + || + math::larger(math::abs(lon1 - lon2), constants::half_period()); + } + + template <typename Segment> + static inline bool apply(Segment const& segment) + { + return apply(detail::indexed_point_view<Segment, 0>(segment), + detail::indexed_point_view<Segment, 1>(segment)); + } + + template <typename Point> + static inline bool apply(Point const& p1, Point const& p2) + { + Point p1_normalized = detail::return_normalized<Point>(p1); + Point p2_normalized = detail::return_normalized<Point>(p2); + + return apply + < + typename coordinate_system<Point>::type::units + >(geometry::get<0>(p1_normalized), + geometry::get<1>(p1_normalized), + geometry::get<0>(p2_normalized), + geometry::get<1>(p2_normalized)); + } +}; + + +}} // namespace detail::envelope + +}} // namespace boost::geometry + +#endif // BOOST_GEOMETRY_ALGORITHMS_DETAIL_ENVELOPE_INTERSECTS_ANTIMERIDIAN_HPP diff --git a/boost/geometry/algorithms/detail/envelope/linear.hpp b/boost/geometry/algorithms/detail/envelope/linear.hpp new file mode 100644 index 0000000000..49c3cf3135 --- /dev/null +++ b/boost/geometry/algorithms/detail/envelope/linear.hpp @@ -0,0 +1,96 @@ +// Boost.Geometry (aka GGL, Generic Geometry Library) + +// Copyright (c) 2007-2015 Barend Gehrels, Amsterdam, the Netherlands. +// Copyright (c) 2008-2015 Bruno Lalande, Paris, France. +// Copyright (c) 2009-2015 Mateusz Loskot, London, UK. + +// This file was modified by Oracle on 2015. +// Modifications 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_LINEAR_HPP +#define BOOST_GEOMETRY_ALGORITHMS_DETAIL_ENVELOPE_LINEAR_HPP + +#include <boost/geometry/core/cs.hpp> +#include <boost/geometry/core/tags.hpp> + +#include <boost/geometry/iterators/segment_iterator.hpp> + +#include <boost/geometry/algorithms/detail/envelope/range.hpp> + +#include <boost/geometry/algorithms/dispatch/envelope.hpp> + + +namespace boost { namespace geometry +{ + +#ifndef DOXYGEN_NO_DETAIL +namespace detail { namespace envelope +{ + + +struct envelope_linestring_on_spheroid +{ + template <typename Linestring, typename Box> + static inline void apply(Linestring const& linestring, Box& mbr) + { + envelope_range::apply(geometry::segments_begin(linestring), + geometry::segments_end(linestring), + mbr); + } +}; + + +}} // namespace detail::envelope +#endif // DOXYGEN_NO_DETAIL + + +#ifndef DOXYGEN_NO_DISPATCH +namespace dispatch +{ + + +template <typename Linestring, typename CS_Tag> +struct envelope<Linestring, linestring_tag, CS_Tag> + : detail::envelope::envelope_range +{}; + +template <typename Linestring> +struct envelope<Linestring, linestring_tag, spherical_equatorial_tag> + : detail::envelope::envelope_linestring_on_spheroid +{}; + + +template <typename MultiLinestring, typename CS_Tag> +struct envelope + < + MultiLinestring, multi_linestring_tag, CS_Tag + > : detail::envelope::envelope_multi_range + < + detail::envelope::envelope_range + > +{}; + +template <typename MultiLinestring> +struct envelope + < + MultiLinestring, multi_linestring_tag, spherical_equatorial_tag + > : detail::envelope::envelope_multi_range_on_spheroid + < + detail::envelope::envelope_linestring_on_spheroid + > +{}; + + +} // namespace dispatch +#endif // DOXYGEN_NO_DISPATCH + + +}} // namespace boost::geometry + +#endif // BOOST_GEOMETRY_ALGORITHMS_DETAIL_ENVELOPE_LINEAR_HPP 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 diff --git a/boost/geometry/algorithms/detail/envelope/point.hpp b/boost/geometry/algorithms/detail/envelope/point.hpp new file mode 100644 index 0000000000..e914e7e8a0 --- /dev/null +++ b/boost/geometry/algorithms/detail/envelope/point.hpp @@ -0,0 +1,127 @@ +// Boost.Geometry (aka GGL, Generic Geometry Library) + +// Copyright (c) 2007-2015 Barend Gehrels, Amsterdam, the Netherlands. +// Copyright (c) 2008-2015 Bruno Lalande, Paris, France. +// Copyright (c) 2009-2015 Mateusz Loskot, London, UK. + +// This file was modified by Oracle on 2015. +// Modifications 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_POINT_HPP +#define BOOST_GEOMETRY_ALGORITHMS_DETAIL_ENVELOPE_POINT_HPP + +#include <cstddef> + +#include <boost/geometry/core/access.hpp> +#include <boost/geometry/core/cs.hpp> +#include <boost/geometry/core/coordinate_dimension.hpp> +#include <boost/geometry/core/coordinate_system.hpp> +#include <boost/geometry/core/tags.hpp> + +#include <boost/geometry/views/detail/indexed_point_view.hpp> + +#include <boost/geometry/algorithms/detail/convert_point_to_point.hpp> +#include <boost/geometry/algorithms/detail/normalize.hpp> + +#include <boost/geometry/algorithms/detail/envelope/transform_units.hpp> + +#include <boost/geometry/algorithms/dispatch/envelope.hpp> + + +namespace boost { namespace geometry +{ + +#ifndef DOXYGEN_NO_DETAIL +namespace detail { namespace envelope +{ + + +template <std::size_t Dimension, std::size_t DimensionCount> +struct envelope_one_point +{ + template <std::size_t Index, typename Point, typename Box> + static inline void apply(Point const& point, Box& mbr) + { + detail::indexed_point_view<Box, Index> box_corner(mbr); + detail::conversion::point_to_point + < + Point, + detail::indexed_point_view<Box, Index>, + Dimension, + DimensionCount + >::apply(point, box_corner); + } + + template <typename Point, typename Box> + static inline void apply(Point const& point, Box& mbr) + { + apply<min_corner>(point, mbr); + apply<max_corner>(point, mbr); + } +}; + + +struct envelope_point_on_spheroid +{ + template<typename Point, typename Box> + static inline void apply(Point const& point, Box& mbr) + { + Point normalized_point = detail::return_normalized<Point>(point); + + typename point_type<Box>::type box_point; + + // transform units of input point to units of a box point + transform_units(normalized_point, box_point); + + geometry::set<min_corner, 0>(mbr, geometry::get<0>(box_point)); + geometry::set<min_corner, 1>(mbr, geometry::get<1>(box_point)); + + geometry::set<max_corner, 0>(mbr, geometry::get<0>(box_point)); + geometry::set<max_corner, 1>(mbr, geometry::get<1>(box_point)); + + envelope_one_point + < + 2, dimension<Point>::value + >::apply(normalized_point, mbr); + } +}; + + +}} // namespace detail::envelope +#endif // DOXYGEN_NO_DETAIL + +#ifndef DOXYGEN_NO_DISPATCH +namespace dispatch +{ + + +template <typename Point, typename CS_Tag> +struct envelope<Point, point_tag, CS_Tag> + : detail::envelope::envelope_one_point<0, dimension<Point>::value> +{}; + + +template <typename Point> +struct envelope<Point, point_tag, spherical_equatorial_tag> + : detail::envelope::envelope_point_on_spheroid +{}; + + +template <typename Point> +struct envelope<Point, point_tag, geographic_tag> + : detail::envelope::envelope_point_on_spheroid +{}; + + +} // namespace dispatch +#endif // DOXYGEN_NO_DISPATCH + +}} // namespace boost::geometry + +#endif // BOOST_GEOMETRY_ALGORITHMS_DETAIL_ENVELOPE_POINT_HPP diff --git a/boost/geometry/algorithms/detail/envelope/range.hpp b/boost/geometry/algorithms/detail/envelope/range.hpp new file mode 100644 index 0000000000..63b518114b --- /dev/null +++ b/boost/geometry/algorithms/detail/envelope/range.hpp @@ -0,0 +1,179 @@ +// Boost.Geometry (aka GGL, Generic Geometry Library) + +// Copyright (c) 2007-2015 Barend Gehrels, Amsterdam, the Netherlands. +// Copyright (c) 2008-2015 Bruno Lalande, Paris, France. +// Copyright (c) 2009-2015 Mateusz Loskot, London, UK. + +// This file was modified by Oracle on 2015. +// Modifications copyright (c) 2015, Oracle and/or its affiliates. + +// Contributed and/or modified by Menelaos Karavelas, on behalf of Oracle + +// Parts of Boost.Geometry are redesigned from Geodan's Geographic Library +// (geolib/GGL), copyright (c) 1995-2010 Geodan, Amsterdam, the Netherlands. + +// 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_RANGE_HPP +#define BOOST_GEOMETRY_ALGORITHMS_DETAIL_ENVELOPE_RANGE_HPP + +#include <iterator> +#include <vector> + +#include <boost/range.hpp> + +#include <boost/geometry/core/coordinate_dimension.hpp> + +#include <boost/geometry/util/range.hpp> + +#include <boost/geometry/algorithms/is_empty.hpp> + +#include <boost/geometry/algorithms/detail/envelope/initialize.hpp> +#include <boost/geometry/algorithms/detail/envelope/range_of_boxes.hpp> + +#include <boost/geometry/algorithms/detail/expand/box.hpp> +#include <boost/geometry/algorithms/detail/expand/point.hpp> +#include <boost/geometry/algorithms/detail/expand/segment.hpp> + +#include <boost/geometry/algorithms/dispatch/envelope.hpp> + + +namespace boost { namespace geometry +{ + +#ifndef DOXYGEN_NO_DETAIL +namespace detail { namespace envelope +{ + + +// implementation for simple ranges +struct envelope_range +{ + template <typename Iterator, typename Box> + static inline void apply(Iterator first, Iterator last, Box& mbr) + { + typedef typename std::iterator_traits<Iterator>::value_type value_type; + + // initialize MBR + initialize<Box, 0, dimension<Box>::value>::apply(mbr); + + Iterator it = first; + if (it != last) + { + // initialize box with first element in range + dispatch::envelope<value_type>::apply(*it, mbr); + + // consider now the remaining elements in the range (if any) + for (++it; it != last; ++it) + { + dispatch::expand<Box, value_type>::apply(mbr, *it); + } + } + } + + template <typename Range, typename Box> + static inline void apply(Range const& range, Box& mbr) + { + return apply(boost::begin(range), boost::end(range), mbr); + } +}; + + +// implementation for multi-ranges +template <typename EnvelopePolicy> +struct envelope_multi_range +{ + template <typename MultiRange, typename Box> + static inline void apply(MultiRange const& multirange, Box& mbr) + { + typedef typename boost::range_iterator + < + MultiRange const + >::type iterator_type; + + bool initialized = false; + for (iterator_type it = boost::begin(multirange); + it != boost::end(multirange); + ++it) + { + if (! geometry::is_empty(*it)) + { + if (initialized) + { + Box helper_mbr; + EnvelopePolicy::apply(*it, helper_mbr); + + dispatch::expand<Box, Box>::apply(mbr, helper_mbr); + } + else + { + // compute the initial envelope + EnvelopePolicy::apply(*it, mbr); + initialized = true; + } + } + } + + if (! initialized) + { + // if not already initialized, initialize MBR + initialize<Box, 0, dimension<Box>::value>::apply(mbr); + } + } +}; + + +// implementation for multi-range on a spheroid (longitude is periodic) +template <typename EnvelopePolicy> +struct envelope_multi_range_on_spheroid +{ + template <typename MultiRange, typename Box> + static inline void apply(MultiRange const& multirange, Box& mbr) + { + typedef typename boost::range_iterator + < + MultiRange const + >::type iterator_type; + + // due to the periodicity of longitudes we need to compute the boxes + // of all the single geometries and keep them in a container + std::vector<Box> boxes; + for (iterator_type it = boost::begin(multirange); + it != boost::end(multirange); + ++it) + { + if (! geometry::is_empty(*it)) + { + Box helper_box; + EnvelopePolicy::apply(*it, helper_box); + boxes.push_back(helper_box); + } + } + + // now we need to compute the envelope of the range of boxes + // (cannot be done in an incremental fashion as in the + // Cartesian coordinate system) + // if all single geometries are empty no boxes have been found + // and the MBR is simply initialized + if (! boxes.empty()) + { + envelope_range_of_boxes::apply(boxes, mbr); + } + else + { + initialize<Box, 0, dimension<Box>::value>::apply(mbr); + } + + } +}; + + +}} // namespace detail::envelope +#endif // DOXYGEN_NO_DETAIL + + +}} // namespace boost::geometry + +#endif // BOOST_GEOMETRY_ALGORITHMS_DETAIL_ENVELOPE_RANGE_HPP diff --git a/boost/geometry/algorithms/detail/envelope/range_of_boxes.hpp b/boost/geometry/algorithms/detail/envelope/range_of_boxes.hpp new file mode 100644 index 0000000000..64bdb9b9cb --- /dev/null +++ b/boost/geometry/algorithms/detail/envelope/range_of_boxes.hpp @@ -0,0 +1,326 @@ +// 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_RANGE_OF_BOXES_HPP +#define BOOST_GEOMETRY_ALGORITHMS_DETAIL_ENVELOPE_RANGE_OF_BOXES_HPP + +#include <cstddef> + +#include <algorithm> +#include <vector> + +#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/util/math.hpp> +#include <boost/geometry/util/range.hpp> + +#include <boost/geometry/algorithms/detail/convert_point_to_point.hpp> +#include <boost/geometry/algorithms/detail/max_interval_gap.hpp> +#include <boost/geometry/algorithms/detail/expand/indexed.hpp> + + +namespace boost { namespace geometry +{ + +#ifndef DOXYGEN_NO_DETAIL +namespace detail { namespace envelope +{ + + +template <typename T> +class longitude_interval +{ + typedef T const& reference_type; + +public: + typedef T value_type; + typedef T difference_type; + + longitude_interval(T const& left, T const& right) + { + m_end[0] = left; + m_end[1] = right; + } + + template <std::size_t Index> + reference_type get() const + { + return m_end[Index]; + } + + difference_type length() const + { + return get<1>() - get<0>(); + } + +private: + T m_end[2]; +}; + + +template <typename Units> +struct envelope_range_of_longitudes +{ + template <std::size_t Index> + struct longitude_less + { + template <typename Interval> + inline bool operator()(Interval const& i1, Interval const& i2) const + { + return math::smaller(i1.template get<Index>(), + i2.template get<Index>()); + } + }; + + template <typename RangeOfLongitudeIntervals, typename Longitude> + static inline void apply(RangeOfLongitudeIntervals const& range, + Longitude& lon_min, Longitude& lon_max) + { + typedef typename math::detail::constants_on_spheroid + < + Longitude, Units + > constants; + + Longitude const zero = 0; + Longitude const period = constants::period(); + + lon_min = lon_max = zero; + + // the range of longitude intervals can be empty if all input boxes + // degenerate to the north or south pole (or combination of the two) + // in this case the initialization values for lon_min and + // lon_max are valid choices + if (! boost::empty(range)) + { + lon_min = std::min_element(boost::begin(range), + boost::end(range), + longitude_less<0>())->template get<0>(); + lon_max = std::max_element(boost::begin(range), + boost::end(range), + longitude_less<1>())->template get<1>(); + + if (math::larger(lon_max - lon_min, constants::half_period())) + { + Longitude max_gap_left, max_gap_right; + Longitude max_gap = geometry::maximum_gap(range, + max_gap_left, + max_gap_right); + + BOOST_GEOMETRY_ASSERT(! math::larger(lon_min, lon_max)); + BOOST_GEOMETRY_ASSERT + (! math::larger(lon_max, constants::max_longitude())); + BOOST_GEOMETRY_ASSERT + (! math::smaller(lon_min, constants::min_longitude())); + + BOOST_GEOMETRY_ASSERT + (! math::larger(max_gap_left, max_gap_right)); + BOOST_GEOMETRY_ASSERT + (! math::larger(max_gap_right, constants::max_longitude())); + BOOST_GEOMETRY_ASSERT + (! math::smaller(max_gap_left, constants::min_longitude())); + + if (math::larger(max_gap, zero)) + { + Longitude wrapped_gap = period + lon_min - lon_max; + if (math::larger(max_gap, wrapped_gap)) + { + lon_min = max_gap_right; + lon_max = max_gap_left + period; + } + } + } + } + } +}; + + +template <std::size_t Dimension, std::size_t DimensionCount> +struct envelope_range_of_boxes_by_expansion +{ + template <typename RangeOfBoxes, typename Box> + static inline void apply(RangeOfBoxes const& range_of_boxes, Box& mbr) + { + typedef typename boost::range_value<RangeOfBoxes>::type box_type; + + typedef typename boost::range_iterator + < + RangeOfBoxes const + >::type iterator_type; + + // first initialize MBR + detail::indexed_point_view<Box, min_corner> mbr_min(mbr); + detail::indexed_point_view<Box, max_corner> mbr_max(mbr); + + detail::indexed_point_view<box_type const, min_corner> + first_box_min(range::front(range_of_boxes)); + + detail::indexed_point_view<box_type const, max_corner> + first_box_max(range::front(range_of_boxes)); + + detail::conversion::point_to_point + < + detail::indexed_point_view<box_type const, min_corner>, + detail::indexed_point_view<Box, min_corner>, + Dimension, + DimensionCount + >::apply(first_box_min, mbr_min); + + detail::conversion::point_to_point + < + detail::indexed_point_view<box_type const, max_corner>, + detail::indexed_point_view<Box, max_corner>, + Dimension, + DimensionCount + >::apply(first_box_max, mbr_max); + + // now expand using the remaining boxes + iterator_type it = boost::begin(range_of_boxes); + for (++it; it != boost::end(range_of_boxes); ++it) + { + detail::expand::indexed_loop + < + strategy::compare::default_strategy, + strategy::compare::default_strategy, + min_corner, + Dimension, + DimensionCount + >::apply(mbr, *it); + + detail::expand::indexed_loop + < + strategy::compare::default_strategy, + strategy::compare::default_strategy, + max_corner, + Dimension, + DimensionCount + >::apply(mbr, *it); + } + } + +}; + + +struct envelope_range_of_boxes +{ + template <std::size_t Index> + struct latitude_less + { + template <typename Box> + inline bool operator()(Box const& box1, Box const& box2) const + { + return math::smaller(geometry::get<Index, 1>(box1), + geometry::get<Index, 1>(box2)); + } + }; + + template <typename RangeOfBoxes, typename Box> + static inline void apply(RangeOfBoxes const& range_of_boxes, Box& mbr) + { + // boxes in the range are assumed to be normalized already + + typedef typename boost::range_value<RangeOfBoxes>::type box_type; + typedef typename coordinate_type<box_type>::type coordinate_type; + typedef typename coordinate_system<box_type>::type::units units_type; + typedef typename boost::range_iterator + < + RangeOfBoxes const + >::type iterator_type; + + typedef math::detail::constants_on_spheroid + < + coordinate_type, units_type + > constants; + + typedef longitude_interval<coordinate_type> interval_type; + typedef std::vector<interval_type> interval_range_type; + + BOOST_GEOMETRY_ASSERT(! boost::empty(range_of_boxes)); + + iterator_type it_min = std::min_element(boost::begin(range_of_boxes), + boost::end(range_of_boxes), + latitude_less<min_corner>()); + iterator_type it_max = std::max_element(boost::begin(range_of_boxes), + boost::end(range_of_boxes), + latitude_less<max_corner>()); + + coordinate_type const min_longitude = constants::min_longitude(); + coordinate_type const max_longitude = constants::max_longitude(); + coordinate_type const period = constants::period(); + + interval_range_type intervals; + for (iterator_type it = boost::begin(range_of_boxes); + it != boost::end(range_of_boxes); + ++it) + { + coordinate_type lat_min = geometry::get<min_corner, 1>(*it); + coordinate_type lat_max = geometry::get<max_corner, 1>(*it); + if (math::equals(lat_min, constants::max_latitude()) + || math::equals(lat_max, constants::min_latitude())) + { + // if the box degenerates to the south or north pole + // just ignore it + continue; + } + + coordinate_type lon_left = geometry::get<min_corner, 0>(*it); + coordinate_type lon_right = geometry::get<max_corner, 0>(*it); + + if (math::larger(lon_right, max_longitude)) + { + intervals.push_back(interval_type(lon_left, max_longitude)); + intervals.push_back + (interval_type(min_longitude, lon_right - period)); + } + else + { + intervals.push_back(interval_type(lon_left, lon_right)); + } + } + + coordinate_type lon_min = 0; + coordinate_type lon_max = 0; + envelope_range_of_longitudes + < + units_type + >::apply(intervals, lon_min, lon_max); + + // do not convert units; conversion will be performed at a + // higher level + + // assign now the min/max longitude/latitude values + detail::indexed_point_view<Box, min_corner> mbr_min(mbr); + detail::indexed_point_view<Box, max_corner> mbr_max(mbr); + + geometry::set<0>(mbr_min, lon_min); + geometry::set<1>(mbr_min, geometry::get<min_corner, 1>(*it_min)); + geometry::set<0>(mbr_max, lon_max); + geometry::set<1>(mbr_max, geometry::get<max_corner, 1>(*it_max)); + + // what remains to be done is to compute the envelope range + // for the remaining dimensions (if any) + envelope_range_of_boxes_by_expansion + < + 2, dimension<Box>::value + >::apply(range_of_boxes, mbr); + } +}; + + +}} // namespace detail::envelope +#endif // DOXYGEN_NO_DETAIL + +}} // namespace boost::geometry + +#endif // BOOST_GEOMETRY_ALGORITHMS_DETAIL_ENVELOPE_RANGE_OF_BOXES_HPP diff --git a/boost/geometry/algorithms/detail/envelope/segment.hpp b/boost/geometry/algorithms/detail/envelope/segment.hpp new file mode 100644 index 0000000000..570f0e1a43 --- /dev/null +++ b/boost/geometry/algorithms/detail/envelope/segment.hpp @@ -0,0 +1,386 @@ +// Boost.Geometry (aka GGL, Generic Geometry Library) + +// Copyright (c) 2007-2015 Barend Gehrels, Amsterdam, the Netherlands. +// Copyright (c) 2008-2015 Bruno Lalande, Paris, France. +// Copyright (c) 2009-2015 Mateusz Loskot, London, UK. + +// This file was modified by Oracle on 2015. +// Modifications 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_SEGMENT_HPP +#define BOOST_GEOMETRY_ALGORITHMS_DETAIL_ENVELOPE_SEGMENT_HPP + +#include <cstddef> +#include <utility> + +#include <boost/numeric/conversion/cast.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/cs.hpp> +#include <boost/geometry/core/point_type.hpp> +#include <boost/geometry/core/radian_access.hpp> +#include <boost/geometry/core/tags.hpp> + +#include <boost/geometry/util/math.hpp> + +#include <boost/geometry/geometries/helper_geometry.hpp> + +#include <boost/geometry/strategies/compare.hpp> + +#include <boost/geometry/algorithms/detail/assign_indexed_point.hpp> +#include <boost/geometry/algorithms/detail/normalize.hpp> + +#include <boost/geometry/algorithms/detail/envelope/point.hpp> +#include <boost/geometry/algorithms/detail/envelope/transform_units.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 +{ + + +template <std::size_t Dimension, std::size_t DimensionCount> +struct envelope_one_segment +{ + template<typename Point, typename Box> + static inline void apply(Point const& p1, Point const& p2, Box& mbr) + { + envelope_one_point<Dimension, DimensionCount>::apply(p1, mbr); + detail::expand::point_loop + < + strategy::compare::default_strategy, + strategy::compare::default_strategy, + Dimension, + DimensionCount + >::apply(mbr, p2); + } +}; + + +// Computes the MBR of a segment given by (lon1, lat1) and (lon2, +// lat2), and with azimuths a1 and a2 at the two endpoints of the +// segment. +// It is assumed that the spherical coordinates of the segment are +// normalized and in radians. +// The longitudes and latitudes of the endpoints are overridden by +// those of the box. +class compute_mbr_of_segment +{ +private: + // computes the azimuths of the segment with endpoints (lon1, lat1) + // and (lon2, lat2) + template <typename CalculationType> + static inline void azimuths(CalculationType const& lon1, + CalculationType const& lat1, + CalculationType const& lon2, + CalculationType const& lat2, + CalculationType& a1, + CalculationType& a2) + { + BOOST_GEOMETRY_ASSERT(math::smaller(lon1, lon2)); + + CalculationType dlon = lon2 - lon1; + CalculationType sin_dlon = sin(dlon); + CalculationType cos_dlon = cos(dlon); + CalculationType cos_lat1 = cos(lat1); + CalculationType cos_lat2 = cos(lat2); + CalculationType sin_lat1 = sin(lat1); + CalculationType sin_lat2 = sin(lat2); + + a1 = atan2(sin_dlon * cos_lat2, + cos_lat1 * sin_lat2 - sin_lat1 * cos_lat2 * cos_dlon); + + a2 = atan2(-sin_dlon * cos_lat1, + cos_lat2 * sin_lat1 - sin_lat2 * cos_lat1 * cos_dlon); + a2 += math::pi<CalculationType>(); + } + + template <typename CalculationType> + static inline void swap(CalculationType& lon1, + CalculationType& lat1, + CalculationType& lon2, + CalculationType& lat2) + { + std::swap(lon1, lon2); + std::swap(lat1, lat2); + } + + template <typename CalculationType> + static inline bool contains_pi_half(CalculationType const& a1, + CalculationType const& a2) + { + // azimuths a1 and a2 are assumed to be in radians + BOOST_GEOMETRY_ASSERT(! math::equals(a1, a2)); + + static CalculationType const pi_half = math::half_pi<CalculationType>(); + + return (a1 < a2) + ? (a1 < pi_half && pi_half < a2) + : (a1 > pi_half && pi_half > a2); + } + + template <typename CoordinateType> + static inline bool crosses_antimeridian(CoordinateType const& lon1, + CoordinateType const& lon2) + { + return math::larger(math::abs(lon1 - lon2), math::pi<CoordinateType>()); + } + + template <typename CalculationType> + static inline CalculationType max_latitude(CalculationType const& azimuth, + CalculationType const& latitude) + { + // azimuth and latitude are assumed to be in radians + return acos( math::abs(cos(latitude) * sin(azimuth)) ); + } + + template <typename CalculationType> + static inline void compute_box_corners(CalculationType& lon1, + CalculationType& lat1, + CalculationType& lon2, + CalculationType& lat2, + CalculationType const& a1, + CalculationType const& a2) + { + // coordinates are assumed to be in radians + BOOST_GEOMETRY_ASSERT(! math::larger(lon1, lon2)); + + if (math::equals(a1, a2)) + { + // the segment must lie on the equator; nothing to do + BOOST_GEOMETRY_ASSERT(math::equals(lat1, CalculationType(0))); + BOOST_GEOMETRY_ASSERT(math::equals(lat2, CalculationType(0))); + return; + } + + if (math::larger(lat1, lat2)) + { + std::swap(lat1, lat2); + } + + if (contains_pi_half(a1, a2)) + { + CalculationType mid_lat = lat1 + lat2; + if (mid_lat < 0) + { + // update using min latitude + CalculationType lat_min = -max_latitude(a1, lat1); + + if (math::larger(lat1, lat_min)) + { + lat1 = lat_min; + } + } + else if (mid_lat > 0) + { + // update using max latitude + CalculationType lat_max = max_latitude(a1, lat1); + + if (math::smaller(lat2, lat_max)) + { + lat2 = lat_max; + } + } + } + } + + template <typename CalculationType> + static inline void apply(CalculationType& lon1, + CalculationType& lat1, + CalculationType& lon2, + CalculationType& lat2) + { + CalculationType const half_pi = math::half_pi<CalculationType>(); + + bool is_pole1 = math::equals(math::abs(lat1), half_pi); + bool is_pole2 = math::equals(math::abs(lat2), half_pi); + + if (is_pole1 && is_pole2) + { + // both points are poles; nothing more to do: + // longitudes are already normalized to 0 + BOOST_GEOMETRY_ASSERT(lon1 == CalculationType(0) + && + lon2 == CalculationType(0)); + } + else if (is_pole1 && !is_pole2) + { + // first point is a pole, second point is not: + // make the longitude of the first point the same as that + // of the second point + lon1 = lon2; + } + else if (!is_pole1 && is_pole2) + { + // second point is a pole, first point is not: + // make the longitude of the second point the same as that + // of the first point + lon2 = lon1; + } + + if (math::equals(lon1, lon2)) + { + // segment lies on a meridian + if (math::larger(lat1, lat2)) + { + std::swap(lat1, lat2); + } + return; + } + + BOOST_GEOMETRY_ASSERT(!is_pole1 && !is_pole2); + + if (math::larger(lon1, lon2)) + { + swap(lon1, lat1, lon2, lat2); + } + + if (crosses_antimeridian(lon1, lon2)) + { + lon1 += math::two_pi<CalculationType>(); + swap(lon1, lat1, lon2, lat2); + } + + CalculationType a1 = 0, a2 = 0; + azimuths(lon1, lat1, lon2, lat2, a1, a2); + + compute_box_corners(lon1, lat1, lon2, lat2, a1, a2); + } + +public: + template <typename CalculationType, typename Box> + static inline void apply(CalculationType lon1, + CalculationType lat1, + CalculationType lon2, + CalculationType lat2, + Box& mbr) + { + typedef typename coordinate_type<Box>::type box_coordinate_type; + + typedef typename helper_geometry + < + Box, box_coordinate_type, radian + >::type helper_box_type; + + helper_box_type radian_mbr; + + apply(lon1, lat1, lon2, lat2); + + geometry::set + < + min_corner, 0 + >(radian_mbr, boost::numeric_cast<box_coordinate_type>(lon1)); + + geometry::set + < + min_corner, 1 + >(radian_mbr, boost::numeric_cast<box_coordinate_type>(lat1)); + + geometry::set + < + max_corner, 0 + >(radian_mbr, boost::numeric_cast<box_coordinate_type>(lon2)); + + geometry::set + < + max_corner, 1 + >(radian_mbr, boost::numeric_cast<box_coordinate_type>(lat2)); + + transform_units(radian_mbr, mbr); + } +}; + + +template <std::size_t DimensionCount> +struct envelope_segment_on_sphere +{ + template <typename Point, typename Box> + static inline void apply(Point const& p1, Point const& p2, Box& mbr) + { + // first compute the envelope range for the first two coordinates + Point p1_normalized = detail::return_normalized<Point>(p1); + Point p2_normalized = detail::return_normalized<Point>(p2); + + compute_mbr_of_segment::apply(geometry::get_as_radian<0>(p1_normalized), + geometry::get_as_radian<1>(p1_normalized), + geometry::get_as_radian<0>(p2_normalized), + geometry::get_as_radian<1>(p2_normalized), + mbr); + + // now compute the envelope range for coordinates of + // dimension 2 and higher + envelope_one_segment<2, DimensionCount>::apply(p1, p2, mbr); + } + + template <typename Segment, typename Box> + static inline void apply(Segment const& segment, Box& mbr) + { + typename point_type<Segment>::type p[2]; + detail::assign_point_from_index<0>(segment, p[0]); + detail::assign_point_from_index<1>(segment, p[1]); + apply(p[0], p[1], mbr); + } +}; + + + +template <std::size_t DimensionCount, typename CS_Tag> +struct envelope_segment + : envelope_one_segment<0, DimensionCount> +{}; + + +template <std::size_t DimensionCount> +struct envelope_segment<DimensionCount, spherical_equatorial_tag> + : envelope_segment_on_sphere<DimensionCount> +{}; + + + +}} // namespace detail::envelope +#endif // DOXYGEN_NO_DETAIL + + +#ifndef DOXYGEN_NO_DISPATCH +namespace dispatch +{ + + +template <typename Segment, typename CS_Tag> +struct envelope<Segment, segment_tag, CS_Tag> +{ + template <typename Box> + static inline void apply(Segment const& segment, Box& mbr) + { + typename point_type<Segment>::type p[2]; + detail::assign_point_from_index<0>(segment, p[0]); + detail::assign_point_from_index<1>(segment, p[1]); + detail::envelope::envelope_segment + < + dimension<Segment>::value, CS_Tag + >::apply(p[0], p[1], mbr); + } +}; + + +} // namespace dispatch +#endif // DOXYGEN_NO_DISPATCH + +}} // namespace boost::geometry + +#endif // BOOST_GEOMETRY_ALGORITHMS_DETAIL_ENVELOPE_SEGMENT_HPP diff --git a/boost/geometry/algorithms/detail/envelope/transform_units.hpp b/boost/geometry/algorithms/detail/envelope/transform_units.hpp new file mode 100644 index 0000000000..0c5382a47b --- /dev/null +++ b/boost/geometry/algorithms/detail/envelope/transform_units.hpp @@ -0,0 +1,103 @@ +// 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_TRANSFORM_UNITS_HPP +#define BOOST_GEOMETRY_ALGORITHMS_DETAIL_ENVELOPE_TRANSFORM_UNITS_HPP + +#include <cstddef> + +#include <boost/geometry/core/tag.hpp> +#include <boost/geometry/core/tags.hpp> + +#include <boost/geometry/strategies/strategy_transform.hpp> + +#include <boost/geometry/views/detail/indexed_point_view.hpp> +#include <boost/geometry/views/detail/two_dimensional_view.hpp> + +#include <boost/geometry/algorithms/not_implemented.hpp> +#include <boost/geometry/algorithms/transform.hpp> + + +namespace boost { namespace geometry +{ + +#ifndef DOXYGEN_NO_DETAIL +namespace detail { namespace envelope +{ + + +template +< + typename GeometryIn, + typename GeometryOut, + typename TagIn = typename tag<GeometryIn>::type, + typename TagOut = typename tag<GeometryOut>::type +> +struct transform_units_impl + : not_implemented<TagIn, TagOut> +{}; + +template <typename PointIn, typename PointOut> +struct transform_units_impl<PointIn, PointOut, point_tag, point_tag> +{ + static inline void apply(PointIn const& point_in, PointOut& point_out) + { + detail::two_dimensional_view<PointIn const> view_in(point_in); + detail::two_dimensional_view<PointOut> view_out(point_out); + + geometry::transform(view_in, view_out); + } +}; + +template <typename BoxIn, typename BoxOut> +struct transform_units_impl<BoxIn, BoxOut, box_tag, box_tag> +{ + template <std::size_t Index> + static inline void apply(BoxIn const& box_in, BoxOut& box_out) + { + typedef detail::indexed_point_view<BoxIn const, Index> view_in_type; + typedef detail::indexed_point_view<BoxOut, Index> view_out_type; + + view_in_type view_in(box_in); + view_out_type view_out(box_out); + + transform_units_impl + < + view_in_type, view_out_type + >::apply(view_in, view_out); + } + + static inline void apply(BoxIn const& box_in, BoxOut& box_out) + { + apply<min_corner>(box_in, box_out); + apply<max_corner>(box_in, box_out); + } +}; + + +// Short utility to transform the units of the first two coordinates of +// geometry_in to the units of geometry_out +template <typename GeometryIn, typename GeometryOut> +inline void transform_units(GeometryIn const& geometry_in, + GeometryOut& geometry_out) +{ + transform_units_impl + < + GeometryIn, GeometryOut + >::apply(geometry_in, geometry_out); +}; + + +}} // namespace detail::envelope +#endif // DOXYGEN_NO_DETAIL + +}} // namespace boost:geometry + +#endif // BOOST_GEOMETRY_ALGORITHMS_DETAIL_ENVELOPE_TRANSFORM_UNITS_HPP |