boost/geometry/strategies/cartesian/distance_projected_point.hpp

   1 // Boost.Geometry (aka GGL, Generic Geometry Library)
   2
   3 // Copyright (c) 2008-2014 Bruno Lalande, Paris, France.
   4 // Copyright (c) 2008-2014 Barend Gehrels, Amsterdam, the Netherlands.
   5 // Copyright (c) 2009-2014 Mateusz Loskot, London, UK.
   6
   7 // This file was modified by Oracle on 2014.
   8 // Modifications copyright (c) 2014, Oracle and/or its affiliates.
   9
  10 // Contributed and/or modified by Menelaos Karavelas, on behalf of Oracle
  11
  12 // Parts of Boost.Geometry are redesigned from Geodan's Geographic Library
  13 // (geolib/GGL), copyright (c) 1995-2010 Geodan, Amsterdam, the Netherlands.
  14
  15 // Use, modification and distribution is subject to the Boost Software License,
  16 // Version 1.0. (See accompanying file LICENSE_1_0.txt or copy at
  17 // http://www.boost.org/LICENSE_1_0.txt)
  18
  19 #ifndef BOOST_GEOMETRY_STRATEGIES_CARTESIAN_DISTANCE_PROJECTED_POINT_HPP
  20 #define BOOST_GEOMETRY_STRATEGIES_CARTESIAN_DISTANCE_PROJECTED_POINT_HPP
  21
  22
  23 #include <boost/concept_check.hpp>
  24 #include <boost/mpl/if.hpp>
  25 #include <boost/type_traits.hpp>
  26
  27 #include <boost/geometry/core/access.hpp>
  28 #include <boost/geometry/core/point_type.hpp>
  29
  30 #include <boost/geometry/algorithms/convert.hpp>
  31 #include <boost/geometry/arithmetic/arithmetic.hpp>
  32 #include <boost/geometry/arithmetic/dot_product.hpp>
  33
  34 #include <boost/geometry/strategies/tags.hpp>
  35 #include <boost/geometry/strategies/distance.hpp>
  36 #include <boost/geometry/strategies/default_distance_result.hpp>
  37 #include <boost/geometry/strategies/cartesian/distance_pythagoras.hpp>
  38
  39 #include <boost/geometry/util/select_coordinate_type.hpp>
  40
  41 // Helper geometry (projected point on line)
  42 #include <boost/geometry/geometries/point.hpp>
  43
  44
  45 namespace boost { namespace geometry
  46 {
  47
  48
  49 namespace strategy { namespace distance
  50 {
  51
  52 /*!
  53 \brief Strategy for distance point to segment
  54 \ingroup strategies
  55 \details Calculates distance using projected-point method, and (optionally) Pythagoras
  56 \author Adapted from: http://geometryalgorithms.com/Archive/algorithm_0102/algorithm_0102.htm
  57 \tparam CalculationType \tparam_calculation
  58 \tparam Strategy underlying point-point distance strategy
  59 \par Concepts for Strategy:
  60 - cartesian_distance operator(Point,Point)
  61 \note If the Strategy is a "comparable::pythagoras", this strategy
  62     automatically is a comparable projected_point strategy (so without sqrt)
  63
  64 \qbk{
  65 [heading See also]
  66 [link geometry.reference.algorithms.distance.distance_3_with_strategy distance (with strategy)]
  67 }
  68
  69 */
  70 template
  71 <
  72     typename CalculationType = void,
  73     typename Strategy = pythagoras<CalculationType>
  74 >
  75 class projected_point
  76 {
  77 public :
  78     // The three typedefs below are necessary to calculate distances
  79     // from segments defined in integer coordinates.
  80
  81     // Integer coordinates can still result in FP distances.
  82     // There is a division, which must be represented in FP.
  83     // So promote.
  84     template <typename Point, typename PointOfSegment>
  85     struct calculation_type
  86         : promote_floating_point
  87           <
  88               typename strategy::distance::services::return_type
  89                   <
  90                       Strategy,
  91                       Point,
  92                       PointOfSegment
  93                   >::type
  94           >
  95     {};
  96
  97 public :
  98
  99     template <typename Point, typename PointOfSegment>
 100     inline typename calculation_type<Point, PointOfSegment>::type
 101     apply(Point const& p, PointOfSegment const& p1, PointOfSegment const& p2) const
 102     {
 103         assert_dimension_equal<Point, PointOfSegment>();
 104
 105         typedef typename calculation_type<Point, PointOfSegment>::type calculation_type;
 106
 107         // A projected point of points in Integer coordinates must be able to be
 108         // represented in FP.
 109         typedef model::point
 110             <
 111                 calculation_type,
 112                 dimension<PointOfSegment>::value,
 113                 typename coordinate_system<PointOfSegment>::type
 114             > fp_point_type;
 115
 116         // For convenience
 117         typedef fp_point_type fp_vector_type;
 118
 119         /*
 120             Algorithm [p: (px,py), p1: (x1,y1), p2: (x2,y2)]
 121             VECTOR v(x2 - x1, y2 - y1)
 122             VECTOR w(px - x1, py - y1)
 123             c1 = w . v
 124             c2 = v . v
 125             b = c1 / c2
 126             RETURN POINT(x1 + b * vx, y1 + b * vy)
 127         */
 128
 129         // v is multiplied below with a (possibly) FP-value, so should be in FP
 130         // For consistency we define w also in FP
 131         fp_vector_type v, w, projected;
 132
 133         geometry::convert(p2, v);
 134         geometry::convert(p, w);
 135         geometry::convert(p1, projected);
 136         subtract_point(v, projected);
 137         subtract_point(w, projected);
 138
 139         Strategy strategy;
 140         boost::ignore_unused_variable_warning(strategy);
 141
 142         calculation_type const zero = calculation_type();
 143         calculation_type const c1 = dot_product(w, v);
 144         if (c1 <= zero)
 145         {
 146             return strategy.apply(p, p1);
 147         }
 148         calculation_type const c2 = dot_product(v, v);
 149         if (c2 <= c1)
 150         {
 151             return strategy.apply(p, p2);
 152         }
 153
 154         // See above, c1 > 0 AND c2 > c1 so: c2 != 0
 155         calculation_type const b = c1 / c2;
 156
 157         multiply_value(v, b);
 158         add_point(projected, v);
 159
 160         return strategy.apply(p, projected);
 161     }
 162 };
 163
 164 #ifndef DOXYGEN_NO_STRATEGY_SPECIALIZATIONS
 165 namespace services
 166 {
 167
 168 template <typename CalculationType, typename Strategy>
 169 struct tag<projected_point<CalculationType, Strategy> >
 170 {
 171     typedef strategy_tag_distance_point_segment type;
 172 };
 173
 174
 175 template <typename CalculationType, typename Strategy, typename P, typename PS>
 176 struct return_type<projected_point<CalculationType, Strategy>, P, PS>
 177     : projected_point<CalculationType, Strategy>::template calculation_type<P, PS>
 178 {};
 179
 180
 181
 182 template <typename CalculationType, typename Strategy>
 183 struct comparable_type<projected_point<CalculationType, Strategy> >
 184 {
 185     // Define a projected_point strategy with its underlying point-point-strategy
 186     // being comparable
 187     typedef projected_point
 188         <
 189             CalculationType,
 190             typename comparable_type<Strategy>::type
 191         > type;
 192 };
 193
 194
 195 template <typename CalculationType, typename Strategy>
 196 struct get_comparable<projected_point<CalculationType, Strategy> >
 197 {
 198     typedef typename comparable_type
 199         <
 200             projected_point<CalculationType, Strategy>
 201         >::type comparable_type;
 202 public :
 203     static inline comparable_type apply(projected_point<CalculationType, Strategy> const& )
 204     {
 205         return comparable_type();
 206     }
 207 };
 208
 209
 210 template <typename CalculationType, typename Strategy, typename P, typename PS>
 211 struct result_from_distance<projected_point<CalculationType, Strategy>, P, PS>
 212 {
 213 private :
 214     typedef typename return_type<projected_point<CalculationType, Strategy>, P, PS>::type return_type;
 215 public :
 216     template <typename T>
 217     static inline return_type apply(projected_point<CalculationType, Strategy> const& , T const& value)
 218     {
 219         Strategy s;
 220         return result_from_distance<Strategy, P, PS>::apply(s, value);
 221     }
 222 };
 223
 224
 225 // Get default-strategy for point-segment distance calculation
 226 // while still have the possibility to specify point-point distance strategy (PPS)
 227 // It is used in algorithms/distance.hpp where users specify PPS for distance
 228 // of point-to-segment or point-to-linestring.
 229 // Convenient for geographic coordinate systems especially.
 230 template <typename Point, typename PointOfSegment, typename Strategy>
 231 struct default_strategy
 232     <
 233         point_tag, segment_tag, Point, PointOfSegment,
 234         cartesian_tag, cartesian_tag, Strategy
 235     >
 236 {
 237     typedef strategy::distance::projected_point
 238     <
 239         void,
 240         typename boost::mpl::if_
 241             <
 242                 boost::is_void<Strategy>,
 243                 typename default_strategy
 244                     <
 245                         point_tag, point_tag, Point, PointOfSegment,
 246                         cartesian_tag, cartesian_tag
 247                     >::type,
 248                 Strategy
 249             >::type
 250     > type;
 251 };
 252
 253 template <typename PointOfSegment, typename Point, typename Strategy>
 254 struct default_strategy
 255     <
 256         segment_tag, point_tag, PointOfSegment, Point,
 257         cartesian_tag, cartesian_tag, Strategy
 258     >
 259 {
 260     typedef typename default_strategy
 261         <
 262             point_tag, segment_tag, Point, PointOfSegment,
 263             cartesian_tag, cartesian_tag, Strategy
 264         >::type type;
 265 };
 266
 267
 268 } // namespace services
 269 #endif // DOXYGEN_NO_STRATEGY_SPECIALIZATIONS
 270
 271
 272 }} // namespace strategy::distance
 273
 274
 275 }} // namespace boost::geometry
 276
 277
 278 #endif // BOOST_GEOMETRY_STRATEGIES_CARTESIAN_DISTANCE_PROJECTED_POINT_HPP