Chris@16: // Boost.Geometry (aka GGL, Generic Geometry Library) Chris@16: Chris@16: // Copyright (c) 2007-2012 Barend Gehrels, Amsterdam, the Netherlands. Chris@16: // Copyright (c) 2008-2012 Bruno Lalande, Paris, France. Chris@16: // Copyright (c) 2009-2012 Mateusz Loskot, London, UK. Chris@16: Chris@16: // Parts of Boost.Geometry are redesigned from Geodan's Geographic Library Chris@16: // (geolib/GGL), copyright (c) 1995-2010 Geodan, Amsterdam, the Netherlands. Chris@16: Chris@16: // Use, modification and distribution is subject to the Boost Software License, Chris@16: // Version 1.0. (See accompanying file LICENSE_1_0.txt or copy at Chris@16: // http://www.boost.org/LICENSE_1_0.txt) Chris@16: Chris@16: #ifndef BOOST_GEOMETRY_ALGORITHMS_DISTANCE_HPP Chris@16: #define BOOST_GEOMETRY_ALGORITHMS_DISTANCE_HPP Chris@16: Chris@16: Chris@16: #include Chris@16: #include Chris@16: #include Chris@16: #include Chris@16: Chris@16: #include Chris@16: #include Chris@16: #include Chris@16: #include Chris@16: Chris@16: #include Chris@16: #include Chris@16: Chris@16: #include Chris@16: #include Chris@16: Chris@16: #include Chris@16: #include Chris@16: #include Chris@16: #include Chris@16: Chris@16: #include Chris@16: #include Chris@16: Chris@16: Chris@16: namespace boost { namespace geometry Chris@16: { Chris@16: Chris@16: #ifndef DOXYGEN_NO_DETAIL Chris@16: namespace detail { namespace distance Chris@16: { Chris@16: Chris@16: // To avoid spurious namespaces here: Chris@16: using strategy::distance::services::return_type; Chris@16: Chris@16: template Chris@16: struct point_to_point Chris@16: { Chris@16: static inline typename return_type::type Chris@16: apply(P1 const& p1, P2 const& p2, Strategy const& strategy) Chris@16: { Chris@16: boost::ignore_unused_variable_warning(strategy); Chris@16: return strategy.apply(p1, p2); Chris@16: } Chris@16: }; Chris@16: Chris@16: Chris@16: template Chris@16: struct point_to_segment Chris@16: { Chris@16: static inline typename return_type::type>::type Chris@16: apply(Point const& point, Segment const& segment, Strategy const& ) Chris@16: { Chris@16: typename strategy::distance::services::default_strategy Chris@16: < Chris@16: segment_tag, Chris@16: Point, Chris@16: typename point_type::type, Chris@16: typename cs_tag::type, Chris@16: typename cs_tag::type>::type, Chris@16: Strategy Chris@16: >::type segment_strategy; Chris@16: Chris@16: typename point_type::type p[2]; Chris@16: geometry::detail::assign_point_from_index<0>(segment, p[0]); Chris@16: geometry::detail::assign_point_from_index<1>(segment, p[1]); Chris@16: return segment_strategy.apply(point, p[0], p[1]); Chris@16: } Chris@16: }; Chris@16: Chris@16: Chris@16: template Chris@16: < Chris@16: typename Point, Chris@16: typename Range, Chris@16: closure_selector Closure, Chris@16: typename PPStrategy, Chris@16: typename PSStrategy Chris@16: > Chris@16: struct point_to_range Chris@16: { Chris@16: typedef typename return_type::type>::type return_type; Chris@16: Chris@16: static inline return_type apply(Point const& point, Range const& range, Chris@16: PPStrategy const& pp_strategy, PSStrategy const& ps_strategy) Chris@16: { Chris@16: return_type const zero = return_type(0); Chris@16: Chris@16: if (boost::size(range) == 0) Chris@16: { Chris@16: return zero; Chris@16: } Chris@16: Chris@16: typedef typename closeable_view::type view_type; Chris@16: Chris@16: view_type view(range); Chris@16: Chris@16: // line of one point: return point distance Chris@16: typedef typename boost::range_iterator::type iterator_type; Chris@16: iterator_type it = boost::begin(view); Chris@16: iterator_type prev = it++; Chris@16: if (it == boost::end(view)) Chris@16: { Chris@16: return pp_strategy.apply(point, *boost::begin(view)); Chris@16: } Chris@16: Chris@16: // Create comparable (more efficient) strategy Chris@16: typedef typename strategy::distance::services::comparable_type::type eps_strategy_type; Chris@16: eps_strategy_type eps_strategy = strategy::distance::services::get_comparable::apply(ps_strategy); Chris@16: Chris@16: // start with first segment distance Chris@16: return_type d = eps_strategy.apply(point, *prev, *it); Chris@16: return_type rd = ps_strategy.apply(point, *prev, *it); Chris@16: Chris@16: // check if other segments are closer Chris@16: for (++prev, ++it; it != boost::end(view); ++prev, ++it) Chris@16: { Chris@16: return_type const ds = eps_strategy.apply(point, *prev, *it); Chris@16: if (geometry::math::equals(ds, zero)) Chris@16: { Chris@16: return ds; Chris@16: } Chris@16: else if (ds < d) Chris@16: { Chris@16: d = ds; Chris@16: rd = ps_strategy.apply(point, *prev, *it); Chris@16: } Chris@16: } Chris@16: Chris@16: return rd; Chris@16: } Chris@16: }; Chris@16: Chris@16: Chris@16: template Chris@16: < Chris@16: typename Point, Chris@16: typename Ring, Chris@16: closure_selector Closure, Chris@16: typename PPStrategy, Chris@16: typename PSStrategy Chris@16: > Chris@16: struct point_to_ring Chris@16: { Chris@16: typedef std::pair Chris@16: < Chris@16: typename return_type::type>::type, bool Chris@16: > distance_containment; Chris@16: Chris@16: static inline distance_containment apply(Point const& point, Chris@16: Ring const& ring, Chris@16: PPStrategy const& pp_strategy, PSStrategy const& ps_strategy) Chris@16: { Chris@16: return distance_containment Chris@16: ( Chris@16: point_to_range Chris@16: < Chris@16: Point, Chris@16: Ring, Chris@16: Closure, Chris@16: PPStrategy, Chris@16: PSStrategy Chris@16: >::apply(point, ring, pp_strategy, ps_strategy), Chris@16: geometry::within(point, ring) Chris@16: ); Chris@16: } Chris@16: }; Chris@16: Chris@16: Chris@16: Chris@16: template Chris@16: < Chris@16: typename Point, Chris@16: typename Polygon, Chris@16: closure_selector Closure, Chris@16: typename PPStrategy, Chris@16: typename PSStrategy Chris@16: > Chris@16: struct point_to_polygon Chris@16: { Chris@16: typedef typename return_type::type>::type return_type; Chris@16: typedef std::pair distance_containment; Chris@16: Chris@16: static inline distance_containment apply(Point const& point, Chris@16: Polygon const& polygon, Chris@16: PPStrategy const& pp_strategy, PSStrategy const& ps_strategy) Chris@16: { Chris@16: // Check distance to all rings Chris@16: typedef point_to_ring Chris@16: < Chris@16: Point, Chris@16: typename ring_type::type, Chris@16: Closure, Chris@16: PPStrategy, Chris@16: PSStrategy Chris@16: > per_ring; Chris@16: Chris@16: distance_containment dc = per_ring::apply(point, Chris@16: exterior_ring(polygon), pp_strategy, ps_strategy); Chris@16: Chris@16: typename interior_return_type::type rings Chris@16: = interior_rings(polygon); Chris@16: for (BOOST_AUTO_TPL(it, boost::begin(rings)); it != boost::end(rings); ++it) Chris@16: { Chris@16: distance_containment dcr = per_ring::apply(point, Chris@16: *it, pp_strategy, ps_strategy); Chris@16: if (dcr.first < dc.first) Chris@16: { Chris@16: dc.first = dcr.first; Chris@16: } Chris@16: // If it was inside, and also inside inner ring, Chris@16: // turn off the inside-flag, it is outside the polygon Chris@16: if (dc.second && dcr.second) Chris@16: { Chris@16: dc.second = false; Chris@16: } Chris@16: } Chris@16: return dc; Chris@16: } Chris@16: }; Chris@16: Chris@16: Chris@16: // Helper metafunction for default strategy retrieval Chris@16: template Chris@16: struct default_strategy Chris@16: : strategy::distance::services::default_strategy Chris@16: < Chris@16: point_tag, Chris@16: typename point_type::type, Chris@16: typename point_type::type Chris@16: > Chris@16: {}; Chris@16: Chris@16: Chris@16: }} // namespace detail::distance Chris@16: #endif // DOXYGEN_NO_DETAIL Chris@16: Chris@16: Chris@16: #ifndef DOXYGEN_NO_DISPATCH Chris@16: namespace dispatch Chris@16: { Chris@16: Chris@16: Chris@16: using strategy::distance::services::return_type; Chris@16: Chris@16: Chris@16: template Chris@16: < Chris@16: typename Geometry1, typename Geometry2, Chris@16: typename Strategy = typename detail::distance::default_strategy::type, Chris@16: typename Tag1 = typename tag_cast::type, multi_tag>::type, Chris@16: typename Tag2 = typename tag_cast::type, multi_tag>::type, Chris@16: typename StrategyTag = typename strategy::distance::services::tag::type, Chris@16: bool Reverse = reverse_dispatch::type::value Chris@16: > Chris@16: struct distance: not_implemented Chris@16: {}; Chris@16: Chris@16: Chris@16: // If reversal is needed, perform it Chris@16: template Chris@16: < Chris@16: typename Geometry1, typename Geometry2, typename Strategy, Chris@16: typename Tag1, typename Tag2, typename StrategyTag Chris@16: > Chris@16: struct distance Chris@16: < Chris@16: Geometry1, Geometry2, Strategy, Chris@16: Tag1, Tag2, StrategyTag, Chris@16: true Chris@16: > Chris@16: : distance Chris@16: { Chris@16: typedef typename strategy::distance::services::return_type Chris@16: < Chris@16: Strategy, Chris@16: typename point_type::type, Chris@16: typename point_type::type Chris@16: >::type return_type; Chris@16: Chris@16: static inline return_type apply( Chris@16: Geometry1 const& g1, Chris@16: Geometry2 const& g2, Chris@16: Strategy const& strategy) Chris@16: { Chris@16: return distance Chris@16: < Chris@16: Geometry2, Geometry1, Strategy, Chris@16: Tag2, Tag1, StrategyTag, Chris@16: false Chris@16: >::apply(g2, g1, strategy); Chris@16: } Chris@16: }; Chris@16: Chris@16: Chris@16: // Point-point Chris@16: template Chris@16: struct distance Chris@16: < Chris@16: P1, P2, Strategy, Chris@16: point_tag, point_tag, strategy_tag_distance_point_point, Chris@16: false Chris@16: > Chris@16: : detail::distance::point_to_point Chris@16: {}; Chris@16: Chris@16: Chris@16: // Point-line version 1, where point-point strategy is specified Chris@16: template Chris@16: struct distance Chris@16: < Chris@16: Point, Linestring, Strategy, Chris@16: point_tag, linestring_tag, strategy_tag_distance_point_point, Chris@16: false Chris@16: > Chris@16: { Chris@16: Chris@16: static inline typename return_type::type>::type Chris@16: apply(Point const& point, Chris@16: Linestring const& linestring, Chris@16: Strategy const& strategy) Chris@16: { Chris@16: typedef typename strategy::distance::services::default_strategy Chris@16: < Chris@16: segment_tag, Chris@16: Point, Chris@16: typename point_type::type, Chris@16: typename cs_tag::type, Chris@16: typename cs_tag::type>::type, Chris@16: Strategy Chris@16: >::type ps_strategy_type; Chris@16: Chris@16: return detail::distance::point_to_range Chris@16: < Chris@16: Point, Linestring, closed, Strategy, ps_strategy_type Chris@16: >::apply(point, linestring, strategy, ps_strategy_type()); Chris@16: } Chris@16: }; Chris@16: Chris@16: Chris@16: // Point-line version 2, where point-segment strategy is specified Chris@16: template Chris@16: struct distance Chris@16: < Chris@16: Point, Linestring, Strategy, Chris@16: point_tag, linestring_tag, strategy_tag_distance_point_segment, Chris@16: false Chris@16: > Chris@16: { Chris@16: static inline typename return_type::type>::type Chris@16: apply(Point const& point, Chris@16: Linestring const& linestring, Chris@16: Strategy const& strategy) Chris@16: { Chris@16: typedef typename Strategy::point_strategy_type pp_strategy_type; Chris@16: return detail::distance::point_to_range Chris@16: < Chris@16: Point, Linestring, closed, pp_strategy_type, Strategy Chris@16: >::apply(point, linestring, pp_strategy_type(), strategy); Chris@16: } Chris@16: }; Chris@16: Chris@16: // Point-ring , where point-segment strategy is specified Chris@16: template Chris@16: struct distance Chris@16: < Chris@16: Point, Ring, Strategy, Chris@16: point_tag, ring_tag, strategy_tag_distance_point_point, Chris@16: false Chris@16: > Chris@16: { Chris@16: typedef typename return_type::type>::type return_type; Chris@16: Chris@16: static inline return_type apply(Point const& point, Chris@16: Ring const& ring, Chris@16: Strategy const& strategy) Chris@16: { Chris@16: typedef typename strategy::distance::services::default_strategy Chris@16: < Chris@16: segment_tag, Chris@16: Point, Chris@16: typename point_type::type Chris@16: >::type ps_strategy_type; Chris@16: Chris@16: std::pair Chris@16: dc = detail::distance::point_to_ring Chris@16: < Chris@16: Point, Ring, Chris@16: geometry::closure::value, Chris@16: Strategy, ps_strategy_type Chris@16: >::apply(point, ring, strategy, ps_strategy_type()); Chris@16: Chris@16: return dc.second ? return_type(0) : dc.first; Chris@16: } Chris@16: }; Chris@16: Chris@16: Chris@16: // Point-polygon , where point-segment strategy is specified Chris@16: template Chris@16: struct distance Chris@16: < Chris@16: Point, Polygon, Strategy, Chris@16: point_tag, polygon_tag, strategy_tag_distance_point_point, Chris@16: false Chris@16: > Chris@16: { Chris@16: typedef typename return_type::type>::type return_type; Chris@16: Chris@16: static inline return_type apply(Point const& point, Chris@16: Polygon const& polygon, Chris@16: Strategy const& strategy) Chris@16: { Chris@16: typedef typename strategy::distance::services::default_strategy Chris@16: < Chris@16: segment_tag, Chris@16: Point, Chris@16: typename point_type::type Chris@16: >::type ps_strategy_type; Chris@16: Chris@16: std::pair Chris@16: dc = detail::distance::point_to_polygon Chris@16: < Chris@16: Point, Polygon, Chris@16: geometry::closure::value, Chris@16: Strategy, ps_strategy_type Chris@16: >::apply(point, polygon, strategy, ps_strategy_type()); Chris@16: Chris@16: return dc.second ? return_type(0) : dc.first; Chris@16: } Chris@16: }; Chris@16: Chris@16: Chris@16: Chris@16: // Point-segment version 1, with point-point strategy Chris@16: template Chris@16: struct distance Chris@16: < Chris@16: Point, Segment, Strategy, Chris@16: point_tag, segment_tag, strategy_tag_distance_point_point, Chris@16: false Chris@16: > : detail::distance::point_to_segment Chris@16: {}; Chris@16: Chris@16: // Point-segment version 2, with point-segment strategy Chris@16: template Chris@16: struct distance Chris@16: < Chris@16: Point, Segment, Strategy, Chris@16: point_tag, segment_tag, strategy_tag_distance_point_segment, Chris@16: false Chris@16: > Chris@16: { Chris@16: static inline typename return_type::type>::type Chris@16: apply(Point const& point, Chris@16: Segment const& segment, Chris@16: Strategy const& strategy) Chris@16: { Chris@16: Chris@16: typename point_type::type p[2]; Chris@16: geometry::detail::assign_point_from_index<0>(segment, p[0]); Chris@16: geometry::detail::assign_point_from_index<1>(segment, p[1]); Chris@16: return strategy.apply(point, p[0], p[1]); Chris@16: } Chris@16: }; Chris@16: Chris@16: Chris@16: Chris@16: } // namespace dispatch Chris@16: #endif // DOXYGEN_NO_DISPATCH Chris@16: Chris@16: /*! Chris@16: \brief \brief_calc2{distance} \brief_strategy Chris@16: \ingroup distance Chris@16: \details Chris@16: \details \details_calc{area}. \brief_strategy. \details_strategy_reasons Chris@16: Chris@16: \tparam Geometry1 \tparam_geometry Chris@16: \tparam Geometry2 \tparam_geometry Chris@16: \tparam Strategy \tparam_strategy{Distance} Chris@16: \param geometry1 \param_geometry Chris@16: \param geometry2 \param_geometry Chris@16: \param strategy \param_strategy{distance} Chris@16: \return \return_calc{distance} Chris@16: \note The strategy can be a point-point strategy. In case of distance point-line/point-polygon Chris@16: it may also be a point-segment strategy. Chris@16: Chris@16: \qbk{distinguish,with strategy} Chris@16: Chris@16: \qbk{ Chris@16: [heading Available Strategies] Chris@16: \* [link geometry.reference.strategies.strategy_distance_pythagoras Pythagoras (cartesian)] Chris@16: \* [link geometry.reference.strategies.strategy_distance_haversine Haversine (spherical)] Chris@16: \* [link geometry.reference.strategies.strategy_distance_cross_track Cross track (spherical\, point-to-segment)] Chris@16: \* [link geometry.reference.strategies.strategy_distance_projected_point Projected point (cartesian\, point-to-segment)] Chris@16: \* more (currently extensions): Vincenty\, Andoyer (geographic) Chris@16: } Chris@16: */ Chris@16: Chris@16: /* Chris@16: Note, in case of a Compilation Error: Chris@16: if you get: Chris@16: - "Failed to specialize function template ..." Chris@16: - "error: no matching function for call to ..." Chris@16: for distance, it is probably so that there is no specialization Chris@16: for return_type<...> for your strategy. Chris@16: */ Chris@16: template Chris@16: inline typename strategy::distance::services::return_type Chris@16: < Chris@16: Strategy, Chris@16: typename point_type::type, Chris@16: typename point_type::type Chris@16: >::type Chris@16: distance(Geometry1 const& geometry1, Chris@16: Geometry2 const& geometry2, Chris@16: Strategy const& strategy) Chris@16: { Chris@16: concept::check(); Chris@16: concept::check(); Chris@16: Chris@16: detail::throw_on_empty_input(geometry1); Chris@16: detail::throw_on_empty_input(geometry2); Chris@16: Chris@16: return dispatch::distance Chris@16: < Chris@16: Geometry1, Chris@16: Geometry2, Chris@16: Strategy Chris@16: >::apply(geometry1, geometry2, strategy); Chris@16: } Chris@16: Chris@16: Chris@16: /*! Chris@16: \brief \brief_calc2{distance} Chris@16: \ingroup distance Chris@16: \details The default strategy is used, corresponding to the coordinate system of the geometries Chris@16: \tparam Geometry1 \tparam_geometry Chris@16: \tparam Geometry2 \tparam_geometry Chris@16: \param geometry1 \param_geometry Chris@16: \param geometry2 \param_geometry Chris@16: \return \return_calc{distance} Chris@16: Chris@16: \qbk{[include reference/algorithms/distance.qbk]} Chris@16: */ Chris@16: template Chris@16: inline typename default_distance_result::type distance( Chris@16: Geometry1 const& geometry1, Geometry2 const& geometry2) Chris@16: { Chris@16: concept::check(); Chris@16: concept::check(); Chris@16: Chris@16: return distance(geometry1, geometry2, Chris@16: typename detail::distance::default_strategy::type()); Chris@16: } Chris@16: Chris@16: }} // namespace boost::geometry Chris@16: Chris@16: #endif // BOOST_GEOMETRY_ALGORITHMS_DISTANCE_HPP