ceph/src/boost/libs/geometry/include/boost/geometry/strategies/cartesian/distance_projected_point_ax.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 // Contributed and/or modified by Adam Wulkiewicz, on behalf of Oracle
  12
  13 // Parts of Boost.Geometry are redesigned from Geodan's Geographic Library
  14 // (geolib/GGL), copyright (c) 1995-2010 Geodan, Amsterdam, the Netherlands.
  15
  16 // Use, modification and distribution is subject to the Boost Software License,
  17 // Version 1.0. (See accompanying file LICENSE_1_0.txt or copy at
  18 // http://www.boost.org/LICENSE_1_0.txt)
  19
  20 #ifndef BOOST_GEOMETRY_STRATEGIES_CARTESIAN_DISTANCE_PROJECTED_POINT_AX_HPP
  21 #define BOOST_GEOMETRY_STRATEGIES_CARTESIAN_DISTANCE_PROJECTED_POINT_AX_HPP
  22
  23
  24 #include <algorithm>
  25
  26 #include <boost/concept_check.hpp>
  27
  28 #include <boost/geometry/core/access.hpp>
  29 #include <boost/geometry/core/point_type.hpp>
  30
  31 #include <boost/geometry/algorithms/convert.hpp>
  32 #include <boost/geometry/arithmetic/arithmetic.hpp>
  33 #include <boost/geometry/arithmetic/dot_product.hpp>
  34
  35 #include <boost/geometry/strategies/tags.hpp>
  36 #include <boost/geometry/strategies/distance.hpp>
  37 #include <boost/geometry/strategies/default_distance_result.hpp>
  38 #include <boost/geometry/strategies/cartesian/distance_pythagoras.hpp>
  39 #include <boost/geometry/strategies/cartesian/distance_projected_point.hpp>
  40
  41 #include <boost/geometry/util/select_coordinate_type.hpp>
  42
  43 // Helper geometry (projected point on line)
  44 #include <boost/geometry/geometries/point.hpp>
  45
  46
  47 namespace boost { namespace geometry
  48 {
  49
  50
  51 namespace strategy { namespace distance
  52 {
  53
  54
  55 #ifndef DOXYGEN_NO_DETAIL
  56 namespace detail
  57 {
  58
  59 template <typename T>
  60 struct projected_point_ax_result
  61 {
  62     typedef T value_type;
  63
  64     projected_point_ax_result(T const& c = T(0))
  65         : atd(c), xtd(c)
  66     {}
  67
  68     projected_point_ax_result(T const& a, T const& x)
  69         : atd(a), xtd(x)
  70     {}
  71
  72     friend inline bool operator<(projected_point_ax_result const& left,
  73                                  projected_point_ax_result const& right)
  74     {
  75         return left.xtd < right.xtd || left.atd < right.atd;
  76     }
  77
  78     T atd, xtd;
  79 };
  80
  81 // This less-comparator may be used as a parameter of detail::douglas_peucker.
  82 // In this simplify strategy distances are compared in 2 places
  83 // 1. to choose the furthest candidate (md < dist)
  84 // 2. to check if the candidate is further than max_distance (max_distance < md)
  85 template <typename Distance>
  86 class projected_point_ax_less
  87 {
  88 public:
  89     projected_point_ax_less(Distance const& max_distance)
  90         : m_max_distance(max_distance)
  91     {}
  92
  93     inline bool operator()(Distance const& left, Distance const& right) const
  94     {
  95         //return left.xtd < right.xtd && right.atd < m_max_distance.atd;
  96
  97         typedef typename Distance::value_type value_type;
  98
  99         value_type const lx = left.xtd > m_max_distance.xtd ? left.xtd - m_max_distance.xtd : 0;
 100         value_type const rx = right.xtd > m_max_distance.xtd ? right.xtd - m_max_distance.xtd : 0;
 101         value_type const la = left.atd > m_max_distance.atd ? left.atd - m_max_distance.atd : 0;
 102         value_type const ra = right.atd > m_max_distance.atd ? right.atd - m_max_distance.atd : 0;
 103
 104         value_type const l = (std::max)(lx, la);
 105         value_type const r = (std::max)(rx, ra);
 106
 107         return l < r;
 108     }
 109 private:
 110     Distance const& m_max_distance;
 111 };
 112
 113 // This strategy returns 2-component Point/Segment distance.
 114 // The ATD (along track distance) is parallel to the Segment
 115 // and is a distance between Point projected into a line defined by a Segment and the nearest Segment's endpoint.
 116 // If the projected Point intersects the Segment the ATD is equal to 0.
 117 // The XTD (cross track distance) is perpendicular to the Segment
 118 // and is a distance between input Point and its projection.
 119 // If the Segment has length equal to 0, ATD and XTD has value equal
 120 // to the distance between the input Point and one of the Segment's endpoints.
 121 //
 122 //          p3         p4
 123 //          ^         7
 124 //          |        /
 125 // p1<-----e========e----->p2
 126 //
 127 // p1: atd=D,   xtd=0
 128 // p2: atd=D,   xtd=0
 129 // p3: atd=0,   xtd=D
 130 // p4: atd=D/2, xtd=D
 131 template
 132 <
 133     typename CalculationType = void,
 134     typename Strategy = pythagoras<CalculationType>
 135 >
 136 class projected_point_ax
 137 {
 138 public :
 139     template <typename Point, typename PointOfSegment>
 140     struct calculation_type
 141         : public projected_point<CalculationType, Strategy>
 142             ::template calculation_type<Point, PointOfSegment>
 143     {};
 144
 145     template <typename Point, typename PointOfSegment>
 146     struct result_type
 147     {
 148         typedef projected_point_ax_result
 149                     <
 150                         typename calculation_type<Point, PointOfSegment>::type
 151                     > type;
 152     };
 153
 154 public :
 155
 156     template <typename Point, typename PointOfSegment>
 157     inline typename result_type<Point, PointOfSegment>::type
 158     apply(Point const& p, PointOfSegment const& p1, PointOfSegment const& p2) const
 159     {
 160         assert_dimension_equal<Point, PointOfSegment>();
 161
 162         typedef typename calculation_type<Point, PointOfSegment>::type calculation_type;
 163
 164         // A projected point of points in Integer coordinates must be able to be
 165         // represented in FP.
 166         typedef model::point
 167             <
 168                 calculation_type,
 169                 dimension<PointOfSegment>::value,
 170                 typename coordinate_system<PointOfSegment>::type
 171             > fp_point_type;
 172
 173         // For convenience
 174         typedef fp_point_type fp_vector_type;
 175
 176         /*
 177             Algorithm [p: (px,py), p1: (x1,y1), p2: (x2,y2)]
 178             VECTOR v(x2 - x1, y2 - y1)
 179             VECTOR w(px - x1, py - y1)
 180             c1 = w . v
 181             c2 = v . v
 182             b = c1 / c2
 183             RETURN POINT(x1 + b * vx, y1 + b * vy)
 184         */
 185
 186         // v is multiplied below with a (possibly) FP-value, so should be in FP
 187         // For consistency we define w also in FP
 188         fp_vector_type v, w, projected;
 189
 190         geometry::convert(p2, v);
 191         geometry::convert(p, w);
 192         geometry::convert(p1, projected);
 193         subtract_point(v, projected);
 194         subtract_point(w, projected);
 195
 196         Strategy strategy;
 197         boost::ignore_unused_variable_warning(strategy);
 198
 199         typename result_type<Point, PointOfSegment>::type result;
 200
 201         calculation_type const zero = calculation_type();
 202         calculation_type const c2 = dot_product(v, v);
 203         if ( math::equals(c2, zero) )
 204         {
 205             result.xtd = strategy.apply(p, projected);
 206             // assume that the 0-length segment is perpendicular to the Pt->ProjPt vector
 207             result.atd = 0;
 208             return result;
 209         }
 210
 211         calculation_type const c1 = dot_product(w, v);
 212         calculation_type const b = c1 / c2;
 213         multiply_value(v, b);
 214         add_point(projected, v);
 215
 216         result.xtd = strategy.apply(p, projected);
 217
 218         if (c1 <= zero)
 219         {
 220             result.atd = strategy.apply(p1, projected);
 221         }
 222         else if (c2 <= c1)
 223         {
 224             result.atd = strategy.apply(p2, projected);
 225         }
 226         else
 227         {
 228             result.atd = 0;
 229         }
 230
 231         return result;
 232     }
 233 };
 234
 235 } // namespace detail
 236 #endif // DOXYGEN_NO_DETAIL
 237
 238 #ifndef DOXYGEN_NO_STRATEGY_SPECIALIZATIONS
 239 namespace services
 240 {
 241
 242
 243 template <typename CalculationType, typename Strategy>
 244 struct tag<detail::projected_point_ax<CalculationType, Strategy> >
 245 {
 246     typedef strategy_tag_distance_point_segment type;
 247 };
 248
 249
 250 template <typename CalculationType, typename Strategy, typename P, typename PS>
 251 struct return_type<detail::projected_point_ax<CalculationType, Strategy>, P, PS>
 252 {
 253     typedef typename detail::projected_point_ax<CalculationType, Strategy>
 254                         ::template result_type<P, PS>::type type;
 255 };
 256
 257
 258 template <typename CalculationType, typename Strategy>
 259 struct comparable_type<detail::projected_point_ax<CalculationType, Strategy> >
 260 {
 261     // Define a projected_point strategy with its underlying point-point-strategy
 262     // being comparable
 263     typedef detail::projected_point_ax
 264         <
 265             CalculationType,
 266             typename comparable_type<Strategy>::type
 267         > type;
 268 };
 269
 270
 271 template <typename CalculationType, typename Strategy>
 272 struct get_comparable<detail::projected_point_ax<CalculationType, Strategy> >
 273 {
 274     typedef typename comparable_type
 275         <
 276             detail::projected_point_ax<CalculationType, Strategy>
 277         >::type comparable_type;
 278 public :
 279     static inline comparable_type apply(detail::projected_point_ax<CalculationType, Strategy> const& )
 280     {
 281         return comparable_type();
 282     }
 283 };
 284
 285
 286 template <typename CalculationType, typename Strategy, typename P, typename PS>
 287 struct result_from_distance<detail::projected_point_ax<CalculationType, Strategy>, P, PS>
 288 {
 289 private :
 290     typedef typename return_type<detail::projected_point_ax<CalculationType, Strategy>, P, PS>::type return_type;
 291 public :
 292     template <typename T>
 293     static inline return_type apply(detail::projected_point_ax<CalculationType, Strategy> const& , T const& value)
 294     {
 295         Strategy s;
 296         return_type ret;
 297         ret.atd = result_from_distance<Strategy, P, PS>::apply(s, value.atd);
 298         ret.xtd = result_from_distance<Strategy, P, PS>::apply(s, value.xtd);
 299         return ret;
 300     }
 301 };
 302
 303
 304 } // namespace services
 305 #endif // DOXYGEN_NO_STRATEGY_SPECIALIZATIONS
 306
 307
 308 }} // namespace strategy::distance
 309
 310
 311 }} // namespace boost::geometry
 312
 313
 314 #endif // BOOST_GEOMETRY_STRATEGIES_CARTESIAN_DISTANCE_PROJECTED_POINT_AX_HPP