Chris@16: // Boost.Geometry (aka GGL, Generic Geometry Library)
Chris@16: 
Chris@101: // Copyright (c) 2008-2014 Bruno Lalande, Paris, France.
Chris@101: // Copyright (c) 2008-2014 Barend Gehrels, Amsterdam, the Netherlands.
Chris@101: // Copyright (c) 2009-2014 Mateusz Loskot, London, UK.
Chris@101: 
Chris@101: // This file was modified by Oracle on 2014.
Chris@101: // Modifications copyright (c) 2014, Oracle and/or its affiliates.
Chris@101: 
Chris@101: // Contributed and/or modified by Menelaos Karavelas, on behalf of Oracle
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_STRATEGIES_CARTESIAN_DISTANCE_PROJECTED_POINT_HPP
Chris@16: #define BOOST_GEOMETRY_STRATEGIES_CARTESIAN_DISTANCE_PROJECTED_POINT_HPP
Chris@16: 
Chris@16: 
Chris@16: #include <boost/concept_check.hpp>
Chris@16: #include <boost/mpl/if.hpp>
Chris@16: #include <boost/type_traits.hpp>
Chris@16: 
Chris@16: #include <boost/geometry/core/access.hpp>
Chris@16: #include <boost/geometry/core/point_type.hpp>
Chris@16: 
Chris@16: #include <boost/geometry/algorithms/convert.hpp>
Chris@16: #include <boost/geometry/arithmetic/arithmetic.hpp>
Chris@16: #include <boost/geometry/arithmetic/dot_product.hpp>
Chris@16: 
Chris@16: #include <boost/geometry/strategies/tags.hpp>
Chris@16: #include <boost/geometry/strategies/distance.hpp>
Chris@16: #include <boost/geometry/strategies/default_distance_result.hpp>
Chris@16: #include <boost/geometry/strategies/cartesian/distance_pythagoras.hpp>
Chris@16: 
Chris@16: #include <boost/geometry/util/select_coordinate_type.hpp>
Chris@16: 
Chris@16: // Helper geometry (projected point on line)
Chris@16: #include <boost/geometry/geometries/point.hpp>
Chris@16: 
Chris@16: 
Chris@16: namespace boost { namespace geometry
Chris@16: {
Chris@16: 
Chris@16: 
Chris@16: namespace strategy { namespace distance
Chris@16: {
Chris@16: 
Chris@16: /*!
Chris@16: \brief Strategy for distance point to segment
Chris@16: \ingroup strategies
Chris@16: \details Calculates distance using projected-point method, and (optionally) Pythagoras
Chris@16: \author Adapted from: http://geometryalgorithms.com/Archive/algorithm_0102/algorithm_0102.htm
Chris@16: \tparam CalculationType \tparam_calculation
Chris@16: \tparam Strategy underlying point-point distance strategy
Chris@16: \par Concepts for Strategy:
Chris@16: - cartesian_distance operator(Point,Point)
Chris@16: \note If the Strategy is a "comparable::pythagoras", this strategy
Chris@16:     automatically is a comparable projected_point strategy (so without sqrt)
Chris@16: 
Chris@16: \qbk{
Chris@16: [heading See also]
Chris@16: [link geometry.reference.algorithms.distance.distance_3_with_strategy distance (with strategy)]
Chris@16: }
Chris@16: 
Chris@16: */
Chris@16: template
Chris@16: <
Chris@16:     typename CalculationType = void,
Chris@16:     typename Strategy = pythagoras<CalculationType>
Chris@16: >
Chris@16: class projected_point
Chris@16: {
Chris@16: public :
Chris@16:     // The three typedefs below are necessary to calculate distances
Chris@16:     // from segments defined in integer coordinates.
Chris@16: 
Chris@16:     // Integer coordinates can still result in FP distances.
Chris@16:     // There is a division, which must be represented in FP.
Chris@16:     // So promote.
Chris@16:     template <typename Point, typename PointOfSegment>
Chris@16:     struct calculation_type
Chris@16:         : promote_floating_point
Chris@16:           <
Chris@16:               typename strategy::distance::services::return_type
Chris@16:                   <
Chris@16:                       Strategy,
Chris@16:                       Point,
Chris@16:                       PointOfSegment
Chris@16:                   >::type
Chris@16:           >
Chris@16:     {};
Chris@16: 
Chris@16: public :
Chris@16: 
Chris@16:     template <typename Point, typename PointOfSegment>
Chris@16:     inline typename calculation_type<Point, PointOfSegment>::type
Chris@16:     apply(Point const& p, PointOfSegment const& p1, PointOfSegment const& p2) const
Chris@16:     {
Chris@16:         assert_dimension_equal<Point, PointOfSegment>();
Chris@16: 
Chris@16:         typedef typename calculation_type<Point, PointOfSegment>::type calculation_type;
Chris@16: 
Chris@16:         // A projected point of points in Integer coordinates must be able to be
Chris@16:         // represented in FP.
Chris@16:         typedef model::point
Chris@16:             <
Chris@16:                 calculation_type,
Chris@16:                 dimension<PointOfSegment>::value,
Chris@16:                 typename coordinate_system<PointOfSegment>::type
Chris@16:             > fp_point_type;
Chris@16: 
Chris@16:         // For convenience
Chris@16:         typedef fp_point_type fp_vector_type;
Chris@16: 
Chris@101:         /*
Chris@101:             Algorithm [p: (px,py), p1: (x1,y1), p2: (x2,y2)]
Chris@16:             VECTOR v(x2 - x1, y2 - y1)
Chris@16:             VECTOR w(px - x1, py - y1)
Chris@16:             c1 = w . v
Chris@16:             c2 = v . v
Chris@16:             b = c1 / c2
Chris@16:             RETURN POINT(x1 + b * vx, y1 + b * vy)
Chris@16:         */
Chris@16: 
Chris@16:         // v is multiplied below with a (possibly) FP-value, so should be in FP
Chris@16:         // For consistency we define w also in FP
Chris@101:         fp_vector_type v, w, projected;
Chris@16: 
Chris@16:         geometry::convert(p2, v);
Chris@16:         geometry::convert(p, w);
Chris@101:         geometry::convert(p1, projected);
Chris@101:         subtract_point(v, projected);
Chris@101:         subtract_point(w, projected);
Chris@16: 
Chris@16:         Strategy strategy;
Chris@16:         boost::ignore_unused_variable_warning(strategy);
Chris@16: 
Chris@16:         calculation_type const zero = calculation_type();
Chris@16:         calculation_type const c1 = dot_product(w, v);
Chris@16:         if (c1 <= zero)
Chris@16:         {
Chris@16:             return strategy.apply(p, p1);
Chris@16:         }
Chris@16:         calculation_type const c2 = dot_product(v, v);
Chris@16:         if (c2 <= c1)
Chris@16:         {
Chris@16:             return strategy.apply(p, p2);
Chris@16:         }
Chris@16: 
Chris@16:         // See above, c1 > 0 AND c2 > c1 so: c2 != 0
Chris@16:         calculation_type const b = c1 / c2;
Chris@16: 
Chris@16:         multiply_value(v, b);
Chris@16:         add_point(projected, v);
Chris@16: 
Chris@16:         return strategy.apply(p, projected);
Chris@16:     }
Chris@16: };
Chris@16: 
Chris@16: #ifndef DOXYGEN_NO_STRATEGY_SPECIALIZATIONS
Chris@16: namespace services
Chris@16: {
Chris@16: 
Chris@16: template <typename CalculationType, typename Strategy>
Chris@16: struct tag<projected_point<CalculationType, Strategy> >
Chris@16: {
Chris@16:     typedef strategy_tag_distance_point_segment type;
Chris@16: };
Chris@16: 
Chris@16: 
Chris@16: template <typename CalculationType, typename Strategy, typename P, typename PS>
Chris@16: struct return_type<projected_point<CalculationType, Strategy>, P, PS>
Chris@16:     : projected_point<CalculationType, Strategy>::template calculation_type<P, PS>
Chris@16: {};
Chris@16: 
Chris@16: 
Chris@16: 
Chris@16: template <typename CalculationType, typename Strategy>
Chris@16: struct comparable_type<projected_point<CalculationType, Strategy> >
Chris@16: {
Chris@16:     // Define a projected_point strategy with its underlying point-point-strategy
Chris@16:     // being comparable
Chris@16:     typedef projected_point
Chris@16:         <
Chris@16:             CalculationType,
Chris@16:             typename comparable_type<Strategy>::type
Chris@16:         > type;
Chris@16: };
Chris@16: 
Chris@16: 
Chris@16: template <typename CalculationType, typename Strategy>
Chris@16: struct get_comparable<projected_point<CalculationType, Strategy> >
Chris@16: {
Chris@16:     typedef typename comparable_type
Chris@16:         <
Chris@16:             projected_point<CalculationType, Strategy>
Chris@16:         >::type comparable_type;
Chris@16: public :
Chris@16:     static inline comparable_type apply(projected_point<CalculationType, Strategy> const& )
Chris@16:     {
Chris@16:         return comparable_type();
Chris@16:     }
Chris@16: };
Chris@16: 
Chris@16: 
Chris@16: template <typename CalculationType, typename Strategy, typename P, typename PS>
Chris@16: struct result_from_distance<projected_point<CalculationType, Strategy>, P, PS>
Chris@16: {
Chris@16: private :
Chris@16:     typedef typename return_type<projected_point<CalculationType, Strategy>, P, PS>::type return_type;
Chris@16: public :
Chris@16:     template <typename T>
Chris@16:     static inline return_type apply(projected_point<CalculationType, Strategy> const& , T const& value)
Chris@16:     {
Chris@16:         Strategy s;
Chris@16:         return result_from_distance<Strategy, P, PS>::apply(s, value);
Chris@16:     }
Chris@16: };
Chris@16: 
Chris@16: 
Chris@16: // Get default-strategy for point-segment distance calculation
Chris@16: // while still have the possibility to specify point-point distance strategy (PPS)
Chris@16: // It is used in algorithms/distance.hpp where users specify PPS for distance
Chris@16: // of point-to-segment or point-to-linestring.
Chris@16: // Convenient for geographic coordinate systems especially.
Chris@16: template <typename Point, typename PointOfSegment, typename Strategy>
Chris@101: struct default_strategy
Chris@101:     <
Chris@101:         point_tag, segment_tag, Point, PointOfSegment,
Chris@101:         cartesian_tag, cartesian_tag, Strategy
Chris@101:     >
Chris@16: {
Chris@16:     typedef strategy::distance::projected_point
Chris@16:     <
Chris@16:         void,
Chris@16:         typename boost::mpl::if_
Chris@16:             <
Chris@16:                 boost::is_void<Strategy>,
Chris@16:                 typename default_strategy
Chris@16:                     <
Chris@101:                         point_tag, point_tag, Point, PointOfSegment,
Chris@16:                         cartesian_tag, cartesian_tag
Chris@16:                     >::type,
Chris@16:                 Strategy
Chris@16:             >::type
Chris@16:     > type;
Chris@16: };
Chris@16: 
Chris@101: template <typename PointOfSegment, typename Point, typename Strategy>
Chris@101: struct default_strategy
Chris@101:     <
Chris@101:         segment_tag, point_tag, PointOfSegment, Point,
Chris@101:         cartesian_tag, cartesian_tag, Strategy
Chris@101:     >
Chris@101: {
Chris@101:     typedef typename default_strategy
Chris@101:         <
Chris@101:             point_tag, segment_tag, Point, PointOfSegment,
Chris@101:             cartesian_tag, cartesian_tag, Strategy
Chris@101:         >::type type;
Chris@101: };
Chris@101: 
Chris@16: 
Chris@16: } // namespace services
Chris@16: #endif // DOXYGEN_NO_STRATEGY_SPECIALIZATIONS
Chris@16: 
Chris@16: 
Chris@16: }} // namespace strategy::distance
Chris@16: 
Chris@16: 
Chris@16: }} // namespace boost::geometry
Chris@16: 
Chris@16: 
Chris@16: #endif // BOOST_GEOMETRY_STRATEGIES_CARTESIAN_DISTANCE_PROJECTED_POINT_HPP