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