strategies/cartesian/distance_projected_point_ax.hpp

0001 // Boost.Geometry (aka GGL, Generic Geometry Library)
0002
0003 // Copyright (c) 2008-2014 Bruno Lalande, Paris, France.
0004 // Copyright (c) 2008-2014 Barend Gehrels, Amsterdam, the Netherlands.
0005 // Copyright (c) 2009-2014 Mateusz Loskot, London, UK.
0006
0007 // This file was modified by Oracle on 2014.
0008 // Modifications copyright (c) 2014, Oracle and/or its affiliates.
0009
0010 // Contributed and/or modified by Menelaos Karavelas, on behalf of Oracle
0011 // Contributed and/or modified by Adam Wulkiewicz, on behalf of Oracle
0012
0013 // Parts of Boost.Geometry are redesigned from Geodan's Geographic Library
0014 // (geolib/GGL), copyright (c) 1995-2010 Geodan, Amsterdam, the Netherlands.
0015
0016 // Use, modification and distribution is subject to the Boost Software License,
0017 // Version 1.0. (See accompanying file LICENSE_1_0.txt or copy at
0018 // http://www.boost.org/LICENSE_1_0.txt)
0019
0020 #ifndef BOOST_GEOMETRY_STRATEGIES_CARTESIAN_DISTANCE_PROJECTED_POINT_AX_HPP
0021 #define BOOST_GEOMETRY_STRATEGIES_CARTESIAN_DISTANCE_PROJECTED_POINT_AX_HPP
0022
0023 #include <boost/config/pragma_message.hpp>
0024 BOOST_PRAGMA_MESSAGE("This include file is deprecated and will be removed in Boost 1.88")
0025
0026 #include <algorithm>
0027
0028 #include <boost/concept_check.hpp>
0029 #include <boost/core/ignore_unused.hpp>
0030
0031 #include <boost/geometry/core/access.hpp>
0032 #include <boost/geometry/core/point_type.hpp>
0033
0034 #include <boost/geometry/algorithms/convert.hpp>
0035 #include <boost/geometry/arithmetic/arithmetic.hpp>
0036 #include <boost/geometry/arithmetic/dot_product.hpp>
0037
0038 #include <boost/geometry/strategies/tags.hpp>
0039 #include <boost/geometry/strategies/distance.hpp>
0040 #include <boost/geometry/strategies/default_distance_result.hpp>
0041 #include <boost/geometry/strategies/cartesian/distance_pythagoras.hpp>
0042 #include <boost/geometry/strategies/cartesian/distance_projected_point.hpp>
0043
0044 #include <boost/geometry/util/select_coordinate_type.hpp>
0045
0046 // Helper geometry (projected point on line)
0047 #include <boost/geometry/geometries/point.hpp>
0048
0049
0050 namespace boost { namespace geometry
0051 {
0052
0053
0054 namespace strategy { namespace distance
0055 {
0056
0057
0058 #ifndef DOXYGEN_NO_DETAIL
0059 namespace detail
0060 {
0061
0062 template <typename T>
0063 struct projected_point_ax_result
0064 {
0065     typedef T value_type;
0066
0067     projected_point_ax_result(T const& c = T(0))
0068         : atd(c), xtd(c)
0069     {}
0070
0071     projected_point_ax_result(T const& a, T const& x)
0072         : atd(a), xtd(x)
0073     {}
0074
0075     friend inline bool operator<(projected_point_ax_result const& left,
0076                                  projected_point_ax_result const& right)
0077     {
0078         return left.xtd < right.xtd || left.atd < right.atd;
0079     }
0080
0081     T atd, xtd;
0082 };
0083
0084 // This less-comparator may be used as a parameter of detail::douglas_peucker.
0085 // In this simplify strategy distances are compared in 2 places
0086 // 1. to choose the furthest candidate (md < dist)
0087 // 2. to check if the candidate is further than max_distance (max_distance < md)
0088 template <typename Distance>
0089 class projected_point_ax_less
0090 {
0091 public:
0092     projected_point_ax_less(Distance const& max_distance)
0093         : m_max_distance(max_distance)
0094     {}
0095
0096     inline bool operator()(Distance const& left, Distance const& right) const
0097     {
0098         //return left.xtd < right.xtd && right.atd < m_max_distance.atd;
0099
0100         typedef typename Distance::value_type value_type;
0101
0102         value_type const lx = left.xtd > m_max_distance.xtd ? left.xtd - m_max_distance.xtd : 0;
0103         value_type const rx = right.xtd > m_max_distance.xtd ? right.xtd - m_max_distance.xtd : 0;
0104         value_type const la = left.atd > m_max_distance.atd ? left.atd - m_max_distance.atd : 0;
0105         value_type const ra = right.atd > m_max_distance.atd ? right.atd - m_max_distance.atd : 0;
0106
0107         value_type const l = (std::max)(lx, la);
0108         value_type const r = (std::max)(rx, ra);
0109
0110         return l < r;
0111     }
0112 private:
0113     Distance const& m_max_distance;
0114 };
0115
0116 // This strategy returns 2-component Point/Segment distance.
0117 // The ATD (along track distance) is parallel to the Segment
0118 // and is a distance between Point projected into a line defined by a Segment and the nearest Segment's endpoint.
0119 // If the projected Point intersects the Segment the ATD is equal to 0.
0120 // The XTD (cross track distance) is perpendicular to the Segment
0121 // and is a distance between input Point and its projection.
0122 // If the Segment has length equal to 0, ATD and XTD has value equal
0123 // to the distance between the input Point and one of the Segment's endpoints.
0124 //
0125 //          p3         p4
0126 //          ^         7
0127 //          |        /
0128 // p1<-----e========e----->p2
0129 //
0130 // p1: atd=D,   xtd=0
0131 // p2: atd=D,   xtd=0
0132 // p3: atd=0,   xtd=D
0133 // p4: atd=D/2, xtd=D
0134 template
0135 <
0136     typename CalculationType = void,
0137     typename Strategy = pythagoras<CalculationType>
0138 >
0139 class projected_point_ax
0140 {
0141 public :
0142     template <typename Point, typename PointOfSegment>
0143     struct calculation_type
0144         : public projected_point<CalculationType, Strategy>
0145             ::template calculation_type<Point, PointOfSegment>
0146     {};
0147
0148     template <typename Point, typename PointOfSegment>
0149     struct result_type
0150     {
0151         typedef projected_point_ax_result
0152                     <
0153                         typename calculation_type<Point, PointOfSegment>::type
0154                     > type;
0155     };
0156
0157 public :
0158
0159     template <typename Point, typename PointOfSegment>
0160     inline typename result_type<Point, PointOfSegment>::type
0161     apply(Point const& p, PointOfSegment const& p1, PointOfSegment const& p2) const
0162     {
0163         assert_dimension_equal<Point, PointOfSegment>();
0164
0165         typedef typename calculation_type<Point, PointOfSegment>::type calculation_type;
0166
0167         // A projected point of points in Integer coordinates must be able to be
0168         // represented in FP.
0169         typedef model::point
0170             <
0171                 calculation_type,
0172                 dimension<PointOfSegment>::value,
0173                 coordinate_system_t<PointOfSegment>
0174             > fp_point_type;
0175
0176         // For convenience
0177         typedef fp_point_type fp_vector_type;
0178
0179         /*
0180             Algorithm [p: (px,py), p1: (x1,y1), p2: (x2,y2)]
0181             VECTOR v(x2 - x1, y2 - y1)
0182             VECTOR w(px - x1, py - y1)
0183             c1 = w . v
0184             c2 = v . v
0185             b = c1 / c2
0186             RETURN POINT(x1 + b * vx, y1 + b * vy)
0187         */
0188
0189         // v is multiplied below with a (possibly) FP-value, so should be in FP
0190         // For consistency we define w also in FP
0191         fp_vector_type v, w, projected;
0192
0193         geometry::convert(p2, v);
0194         geometry::convert(p, w);
0195         geometry::convert(p1, projected);
0196         subtract_point(v, projected);
0197         subtract_point(w, projected);
0198
0199         Strategy strategy;
0200         boost::ignore_unused(strategy);
0201
0202         typename result_type<Point, PointOfSegment>::type result;
0203
0204         calculation_type const zero = calculation_type();
0205         calculation_type const c2 = dot_product(v, v);
0206         if ( math::equals(c2, zero) )
0207         {
0208             result.xtd = strategy.apply(p, projected);
0209             // assume that the 0-length segment is perpendicular to the Pt->ProjPt vector
0210             result.atd = 0;
0211             return result;
0212         }
0213
0214         calculation_type const c1 = dot_product(w, v);
0215         calculation_type const b = c1 / c2;
0216         multiply_value(v, b);
0217         add_point(projected, v);
0218
0219         result.xtd = strategy.apply(p, projected);
0220
0221         if (c1 <= zero)
0222         {
0223             result.atd = strategy.apply(p1, projected);
0224         }
0225         else if (c2 <= c1)
0226         {
0227             result.atd = strategy.apply(p2, projected);
0228         }
0229         else
0230         {
0231             result.atd = 0;
0232         }
0233
0234         return result;
0235     }
0236 };
0237
0238 } // namespace detail
0239 #endif // DOXYGEN_NO_DETAIL
0240
0241 #ifndef DOXYGEN_NO_STRATEGY_SPECIALIZATIONS
0242 namespace services
0243 {
0244
0245
0246 template <typename CalculationType, typename Strategy>
0247 struct tag<detail::projected_point_ax<CalculationType, Strategy> >
0248 {
0249     typedef strategy_tag_distance_point_segment type;
0250 };
0251
0252
0253 template <typename CalculationType, typename Strategy, typename P, typename PS>
0254 struct return_type<detail::projected_point_ax<CalculationType, Strategy>, P, PS>
0255 {
0256     typedef typename detail::projected_point_ax<CalculationType, Strategy>
0257                         ::template result_type<P, PS>::type type;
0258 };
0259
0260
0261 template <typename CalculationType, typename Strategy>
0262 struct comparable_type<detail::projected_point_ax<CalculationType, Strategy> >
0263 {
0264     // Define a projected_point strategy with its underlying point-point-strategy
0265     // being comparable
0266     typedef detail::projected_point_ax
0267         <
0268             CalculationType,
0269             typename comparable_type<Strategy>::type
0270         > type;
0271 };
0272
0273
0274 template <typename CalculationType, typename Strategy>
0275 struct get_comparable<detail::projected_point_ax<CalculationType, Strategy> >
0276 {
0277     typedef typename comparable_type
0278         <
0279             detail::projected_point_ax<CalculationType, Strategy>
0280         >::type comparable_type;
0281 public :
0282     static inline comparable_type apply(detail::projected_point_ax<CalculationType, Strategy> const& )
0283     {
0284         return comparable_type();
0285     }
0286 };
0287
0288
0289 template <typename CalculationType, typename Strategy, typename P, typename PS>
0290 struct result_from_distance<detail::projected_point_ax<CalculationType, Strategy>, P, PS>
0291 {
0292 private :
0293     typedef typename return_type<detail::projected_point_ax<CalculationType, Strategy>, P, PS>::type return_type;
0294 public :
0295     template <typename T>
0296     static inline return_type apply(detail::projected_point_ax<CalculationType, Strategy> const& , T const& value)
0297     {
0298         Strategy s;
0299         return_type ret;
0300         ret.atd = result_from_distance<Strategy, P, PS>::apply(s, value.atd);
0301         ret.xtd = result_from_distance<Strategy, P, PS>::apply(s, value.xtd);
0302         return ret;
0303     }
0304 };
0305
0306
0307 } // namespace services
0308 #endif // DOXYGEN_NO_STRATEGY_SPECIALIZATIONS
0309
0310
0311 }} // namespace strategy::distance
0312
0313
0314 }} // namespace boost::geometry
0315
0316 #endif // BOOST_GEOMETRY_STRATEGIES_CARTESIAN_DISTANCE_PROJECTED_POINT_AX_HPP