diff options
Diffstat (limited to 'boost/geometry/algorithms/distance.hpp')
| -rw-r--r-- | boost/geometry/algorithms/distance.hpp | 587 |
1 files changed, 11 insertions, 576 deletions
diff --git a/boost/geometry/algorithms/distance.hpp b/boost/geometry/algorithms/distance.hpp index 11c2bc929b..dcfe597cd0 100644 --- a/boost/geometry/algorithms/distance.hpp +++ b/boost/geometry/algorithms/distance.hpp @@ -1,8 +1,14 @@ // Boost.Geometry (aka GGL, Generic Geometry Library) -// Copyright (c) 2007-2012 Barend Gehrels, Amsterdam, the Netherlands. -// Copyright (c) 2008-2012 Bruno Lalande, Paris, France. -// Copyright (c) 2009-2012 Mateusz Loskot, London, UK. +// Copyright (c) 2007-2014 Barend Gehrels, Amsterdam, the Netherlands. +// Copyright (c) 2008-2014 Bruno Lalande, Paris, France. +// Copyright (c) 2009-2014 Mateusz Loskot, London, UK. +// Copyright (c) 2013-2014 Adam Wulkiewicz, Lodz, Poland. + +// This file was modified by Oracle on 2014. +// Modifications copyright (c) 2014, 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. @@ -14,578 +20,7 @@ #ifndef BOOST_GEOMETRY_ALGORITHMS_DISTANCE_HPP #define BOOST_GEOMETRY_ALGORITHMS_DISTANCE_HPP - -#include <boost/mpl/if.hpp> -#include <boost/range.hpp> -#include <boost/typeof/typeof.hpp> - -#include <boost/geometry/core/cs.hpp> -#include <boost/geometry/core/closure.hpp> -#include <boost/geometry/core/reverse_dispatch.hpp> -#include <boost/geometry/core/tag_cast.hpp> - -#include <boost/geometry/algorithms/not_implemented.hpp> -#include <boost/geometry/algorithms/detail/throw_on_empty_input.hpp> - -#include <boost/geometry/geometries/segment.hpp> -#include <boost/geometry/geometries/concepts/check.hpp> - -#include <boost/geometry/strategies/distance.hpp> -#include <boost/geometry/strategies/default_distance_result.hpp> -#include <boost/geometry/algorithms/assign.hpp> -#include <boost/geometry/algorithms/within.hpp> - -#include <boost/geometry/views/closeable_view.hpp> -#include <boost/geometry/util/math.hpp> - - -namespace boost { namespace geometry -{ - -#ifndef DOXYGEN_NO_DETAIL -namespace detail { namespace distance -{ - -// To avoid spurious namespaces here: -using strategy::distance::services::return_type; - -template <typename P1, typename P2, typename Strategy> -struct point_to_point -{ - static inline typename return_type<Strategy>::type apply(P1 const& p1, - P2 const& p2, Strategy const& strategy) - { - return strategy.apply(p1, p2); - } -}; - - -template<typename Point, typename Segment, typename Strategy> -struct point_to_segment -{ - static inline typename return_type<Strategy>::type apply(Point const& point, - Segment const& segment, Strategy const& ) - { - typename strategy::distance::services::default_strategy - < - segment_tag, - Point, - typename point_type<Segment>::type, - typename cs_tag<Point>::type, - typename cs_tag<typename point_type<Segment>::type>::type, - Strategy - >::type segment_strategy; - - typename point_type<Segment>::type p[2]; - geometry::detail::assign_point_from_index<0>(segment, p[0]); - geometry::detail::assign_point_from_index<1>(segment, p[1]); - return segment_strategy.apply(point, p[0], p[1]); - } -}; - - -template -< - typename Point, - typename Range, - closure_selector Closure, - typename PPStrategy, - typename PSStrategy -> -struct point_to_range -{ - typedef typename return_type<PSStrategy>::type return_type; - - static inline return_type apply(Point const& point, Range const& range, - PPStrategy const& pp_strategy, PSStrategy const& ps_strategy) - { - return_type const zero = return_type(0); - - if (boost::size(range) == 0) - { - return zero; - } - - typedef typename closeable_view<Range const, Closure>::type view_type; - - view_type view(range); - - // line of one point: return point distance - typedef typename boost::range_iterator<view_type const>::type iterator_type; - iterator_type it = boost::begin(view); - iterator_type prev = it++; - if (it == boost::end(view)) - { - return pp_strategy.apply(point, *boost::begin(view)); - } - - // Create comparable (more efficient) strategy - typedef typename strategy::distance::services::comparable_type<PSStrategy>::type eps_strategy_type; - eps_strategy_type eps_strategy = strategy::distance::services::get_comparable<PSStrategy>::apply(ps_strategy); - - // start with first segment distance - return_type d = eps_strategy.apply(point, *prev, *it); - return_type rd = ps_strategy.apply(point, *prev, *it); - - // check if other segments are closer - for (++prev, ++it; it != boost::end(view); ++prev, ++it) - { - return_type const ds = eps_strategy.apply(point, *prev, *it); - if (geometry::math::equals(ds, zero)) - { - return ds; - } - else if (ds < d) - { - d = ds; - rd = ps_strategy.apply(point, *prev, *it); - } - } - - return rd; - } -}; - - -template -< - typename Point, - typename Ring, - closure_selector Closure, - typename PPStrategy, - typename PSStrategy -> -struct point_to_ring -{ - typedef std::pair - < - typename return_type<PPStrategy>::type, bool - > distance_containment; - - static inline distance_containment apply(Point const& point, - Ring const& ring, - PPStrategy const& pp_strategy, PSStrategy const& ps_strategy) - { - return distance_containment - ( - point_to_range - < - Point, - Ring, - Closure, - PPStrategy, - PSStrategy - >::apply(point, ring, pp_strategy, ps_strategy), - geometry::within(point, ring) - ); - } -}; - - - -template -< - typename Point, - typename Polygon, - closure_selector Closure, - typename PPStrategy, - typename PSStrategy -> -struct point_to_polygon -{ - typedef typename return_type<PPStrategy>::type return_type; - typedef std::pair<return_type, bool> distance_containment; - - static inline distance_containment apply(Point const& point, - Polygon const& polygon, - PPStrategy const& pp_strategy, PSStrategy const& ps_strategy) - { - // Check distance to all rings - typedef point_to_ring - < - Point, - typename ring_type<Polygon>::type, - Closure, - PPStrategy, - PSStrategy - > per_ring; - - distance_containment dc = per_ring::apply(point, - exterior_ring(polygon), pp_strategy, ps_strategy); - - typename interior_return_type<Polygon const>::type rings - = interior_rings(polygon); - for (BOOST_AUTO_TPL(it, boost::begin(rings)); it != boost::end(rings); ++it) - { - distance_containment dcr = per_ring::apply(point, - *it, pp_strategy, ps_strategy); - if (dcr.first < dc.first) - { - dc.first = dcr.first; - } - // If it was inside, and also inside inner ring, - // turn off the inside-flag, it is outside the polygon - if (dc.second && dcr.second) - { - dc.second = false; - } - } - return dc; - } -}; - - -// Helper metafunction for default strategy retrieval -template <typename Geometry1, typename Geometry2> -struct default_strategy - : strategy::distance::services::default_strategy - < - point_tag, - typename point_type<Geometry1>::type, - typename point_type<Geometry2>::type - > -{}; - - -}} // namespace detail::distance -#endif // DOXYGEN_NO_DETAIL - - -#ifndef DOXYGEN_NO_DISPATCH -namespace dispatch -{ - - -using strategy::distance::services::return_type; - - -template -< - typename Geometry1, typename Geometry2, - typename Strategy = typename detail::distance::default_strategy<Geometry1, Geometry2>::type, - typename Tag1 = typename tag_cast<typename tag<Geometry1>::type, multi_tag>::type, - typename Tag2 = typename tag_cast<typename tag<Geometry2>::type, multi_tag>::type, - typename StrategyTag = typename strategy::distance::services::tag<Strategy>::type, - bool Reverse = reverse_dispatch<Geometry1, Geometry2>::type::value -> -struct distance: not_implemented<Tag1, Tag2> -{}; - - -// If reversal is needed, perform it -template -< - typename Geometry1, typename Geometry2, typename Strategy, - typename Tag1, typename Tag2, typename StrategyTag -> -struct distance -< - Geometry1, Geometry2, Strategy, - Tag1, Tag2, StrategyTag, - true -> - : distance<Geometry2, Geometry1, Strategy, Tag2, Tag1, StrategyTag, false> -{ - static inline typename return_type<Strategy>::type apply( - Geometry1 const& g1, - Geometry2 const& g2, - Strategy const& strategy) - { - return distance - < - Geometry2, Geometry1, Strategy, - Tag2, Tag1, StrategyTag, - false - >::apply(g2, g1, strategy); - } -}; - -// If reversal is needed and we got the strategy by default, invert it before -// proceeding to the reversal. -template -< - typename Geometry1, typename Geometry2, - typename Tag1, typename Tag2, typename StrategyTag -> -struct distance -< - Geometry1, Geometry2, - typename detail::distance::default_strategy<Geometry1, Geometry2>::type, - Tag1, Tag2, StrategyTag, - true -> - : distance - < - Geometry2, Geometry1, - typename detail::distance::default_strategy<Geometry2, Geometry1>::type, - Tag2, Tag1, StrategyTag, - false - > -{ - typedef typename detail::distance::default_strategy<Geometry2, Geometry1>::type reversed_strategy; - - static inline typename strategy::distance::services::return_type<reversed_strategy>::type apply( - Geometry1 const& g1, - Geometry2 const& g2, - typename detail::distance::default_strategy<Geometry1, Geometry2>::type const&) - { - return distance - < - Geometry2, Geometry1, reversed_strategy, - Tag2, Tag1, StrategyTag, - false - >::apply(g2, g1, reversed_strategy()); - } -}; - - -// Point-point -template <typename P1, typename P2, typename Strategy> -struct distance - < - P1, P2, Strategy, - point_tag, point_tag, strategy_tag_distance_point_point, - false - > - : detail::distance::point_to_point<P1, P2, Strategy> -{}; - - -// Point-line version 1, where point-point strategy is specified -template <typename Point, typename Linestring, typename Strategy> -struct distance -< - Point, Linestring, Strategy, - point_tag, linestring_tag, strategy_tag_distance_point_point, - false -> -{ - - static inline typename return_type<Strategy>::type apply(Point const& point, - Linestring const& linestring, - Strategy const& strategy) - { - typedef typename strategy::distance::services::default_strategy - < - segment_tag, - Point, - typename point_type<Linestring>::type - >::type ps_strategy_type; - - return detail::distance::point_to_range - < - Point, Linestring, closed, Strategy, ps_strategy_type - >::apply(point, linestring, strategy, ps_strategy_type()); - } -}; - - -// Point-line version 2, where point-segment strategy is specified -template <typename Point, typename Linestring, typename Strategy> -struct distance -< - Point, Linestring, Strategy, - point_tag, linestring_tag, strategy_tag_distance_point_segment, - false -> -{ - static inline typename return_type<Strategy>::type apply(Point const& point, - Linestring const& linestring, - Strategy const& strategy) - { - typedef typename Strategy::point_strategy_type pp_strategy_type; - return detail::distance::point_to_range - < - Point, Linestring, closed, pp_strategy_type, Strategy - >::apply(point, linestring, pp_strategy_type(), strategy); - } -}; - -// Point-ring , where point-segment strategy is specified -template <typename Point, typename Ring, typename Strategy> -struct distance -< - Point, Ring, Strategy, - point_tag, ring_tag, strategy_tag_distance_point_point, - false -> -{ - typedef typename return_type<Strategy>::type return_type; - - static inline return_type apply(Point const& point, - Ring const& ring, - Strategy const& strategy) - { - typedef typename strategy::distance::services::default_strategy - < - segment_tag, - Point, - typename point_type<Ring>::type - >::type ps_strategy_type; - - std::pair<return_type, bool> - dc = detail::distance::point_to_ring - < - Point, Ring, - geometry::closure<Ring>::value, - Strategy, ps_strategy_type - >::apply(point, ring, strategy, ps_strategy_type()); - - return dc.second ? return_type(0) : dc.first; - } -}; - - -// Point-polygon , where point-segment strategy is specified -template <typename Point, typename Polygon, typename Strategy> -struct distance -< - Point, Polygon, Strategy, - point_tag, polygon_tag, strategy_tag_distance_point_point, - false -> -{ - typedef typename return_type<Strategy>::type return_type; - - static inline return_type apply(Point const& point, - Polygon const& polygon, - Strategy const& strategy) - { - typedef typename strategy::distance::services::default_strategy - < - segment_tag, - Point, - typename point_type<Polygon>::type - >::type ps_strategy_type; - - std::pair<return_type, bool> - dc = detail::distance::point_to_polygon - < - Point, Polygon, - geometry::closure<Polygon>::value, - Strategy, ps_strategy_type - >::apply(point, polygon, strategy, ps_strategy_type()); - - return dc.second ? return_type(0) : dc.first; - } -}; - - - -// Point-segment version 1, with point-point strategy -template <typename Point, typename Segment, typename Strategy> -struct distance -< - Point, Segment, Strategy, - point_tag, segment_tag, strategy_tag_distance_point_point, - false -> : detail::distance::point_to_segment<Point, Segment, Strategy> -{}; - -// Point-segment version 2, with point-segment strategy -template <typename Point, typename Segment, typename Strategy> -struct distance -< - Point, Segment, Strategy, - point_tag, segment_tag, strategy_tag_distance_point_segment, - false -> -{ - static inline typename return_type<Strategy>::type apply(Point const& point, - Segment const& segment, Strategy const& strategy) - { - - typename point_type<Segment>::type p[2]; - geometry::detail::assign_point_from_index<0>(segment, p[0]); - geometry::detail::assign_point_from_index<1>(segment, p[1]); - return strategy.apply(point, p[0], p[1]); - } -}; - - - -} // namespace dispatch -#endif // DOXYGEN_NO_DISPATCH - -/*! -\brief \brief_calc2{distance} \brief_strategy -\ingroup distance -\details -\details \details_calc{area}. \brief_strategy. \details_strategy_reasons - -\tparam Geometry1 \tparam_geometry -\tparam Geometry2 \tparam_geometry -\tparam Strategy \tparam_strategy{Distance} -\param geometry1 \param_geometry -\param geometry2 \param_geometry -\param strategy \param_strategy{distance} -\return \return_calc{distance} -\note The strategy can be a point-point strategy. In case of distance point-line/point-polygon - it may also be a point-segment strategy. - -\qbk{distinguish,with strategy} - -\qbk{ -[heading Available Strategies] -\* [link geometry.reference.strategies.strategy_distance_pythagoras Pythagoras (cartesian)] -\* [link geometry.reference.strategies.strategy_distance_haversine Haversine (spherical)] -\* [link geometry.reference.strategies.strategy_distance_cross_track Cross track (spherical\, point-to-segment)] -\* [link geometry.reference.strategies.strategy_distance_projected_point Projected point (cartesian\, point-to-segment)] -\* more (currently extensions): Vincenty\, Andoyer (geographic) -} - */ - -/* -Note, in case of a Compilation Error: -if you get: - - "Failed to specialize function template ..." - - "error: no matching function for call to ..." -for distance, it is probably so that there is no specialization -for return_type<...> for your strategy. -*/ -template <typename Geometry1, typename Geometry2, typename Strategy> -inline typename strategy::distance::services::return_type<Strategy>::type distance( - Geometry1 const& geometry1, Geometry2 const& geometry2, - Strategy const& strategy) -{ - concept::check<Geometry1 const>(); - concept::check<Geometry2 const>(); - - detail::throw_on_empty_input(geometry1); - detail::throw_on_empty_input(geometry2); - - return dispatch::distance - < - Geometry1, - Geometry2, - Strategy - >::apply(geometry1, geometry2, strategy); -} - - -/*! -\brief \brief_calc2{distance} -\ingroup distance -\details The default strategy is used, corresponding to the coordinate system of the geometries -\tparam Geometry1 \tparam_geometry -\tparam Geometry2 \tparam_geometry -\param geometry1 \param_geometry -\param geometry2 \param_geometry -\return \return_calc{distance} - -\qbk{[include reference/algorithms/distance.qbk]} - */ -template <typename Geometry1, typename Geometry2> -inline typename default_distance_result<Geometry1, Geometry2>::type distance( - Geometry1 const& geometry1, Geometry2 const& geometry2) -{ - concept::check<Geometry1 const>(); - concept::check<Geometry2 const>(); - - return distance(geometry1, geometry2, - typename detail::distance::default_strategy<Geometry1, Geometry2>::type()); -} - -}} // namespace boost::geometry +#include <boost/geometry/algorithms/detail/distance/interface.hpp> +#include <boost/geometry/algorithms/detail/distance/implementation.hpp> #endif // BOOST_GEOMETRY_ALGORITHMS_DISTANCE_HPP |