1 // Boost.Geometry (aka GGL, Generic Geometry Library)
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.
7 // This file was modified by Oracle on 2014.
8 // Modifications copyright (c) 2014, Oracle and/or its affiliates.
10 // Contributed and/or modified by Menelaos Karavelas, on behalf of Oracle
11 // Contributed and/or modified by Adam Wulkiewicz, on behalf of Oracle
13 // Parts of Boost.Geometry are redesigned from Geodan's Geographic Library
14 // (geolib/GGL), copyright (c) 1995-2010 Geodan, Amsterdam, the Netherlands.
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)
20 #ifndef BOOST_GEOMETRY_STRATEGIES_CARTESIAN_DISTANCE_PROJECTED_POINT_AX_HPP
21 #define BOOST_GEOMETRY_STRATEGIES_CARTESIAN_DISTANCE_PROJECTED_POINT_AX_HPP
26 #include <boost/concept_check.hpp>
28 #include <boost/geometry/core/access.hpp>
29 #include <boost/geometry/core/point_type.hpp>
31 #include <boost/geometry/algorithms/convert.hpp>
32 #include <boost/geometry/arithmetic/arithmetic.hpp>
33 #include <boost/geometry/arithmetic/dot_product.hpp>
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>
41 #include <boost/geometry/util/select_coordinate_type.hpp>
43 // Helper geometry (projected point on line)
44 #include <boost/geometry/geometries/point.hpp>
47 namespace boost { namespace geometry
51 namespace strategy { namespace distance
55 #ifndef DOXYGEN_NO_DETAIL
60 struct projected_point_ax_result
64 projected_point_ax_result(T const& c = T(0))
68 projected_point_ax_result(T const& a, T const& x)
72 friend inline bool operator<(projected_point_ax_result const& left,
73 projected_point_ax_result const& right)
75 return left.xtd < right.xtd || left.atd < right.atd;
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
89 projected_point_ax_less(Distance const& max_distance)
90 : m_max_distance(max_distance)
93 inline bool operator()(Distance const& left, Distance const& right) const
95 //return left.xtd < right.xtd && right.atd < m_max_distance.atd;
97 typedef typename Distance::value_type value_type;
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;
104 value_type const l = (std::max)(lx, la);
105 value_type const r = (std::max)(rx, ra);
110 Distance const& m_max_distance;
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.
125 // p1<-----e========e----->p2
130 // p4: atd=D/2, xtd=D
133 typename CalculationType = void,
134 typename Strategy = pythagoras<CalculationType>
136 class projected_point_ax
139 template <typename Point, typename PointOfSegment>
140 struct calculation_type
141 : public projected_point<CalculationType, Strategy>
142 ::template calculation_type<Point, PointOfSegment>
145 template <typename Point, typename PointOfSegment>
148 typedef projected_point_ax_result
150 typename calculation_type<Point, PointOfSegment>::type
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
160 assert_dimension_equal<Point, PointOfSegment>();
162 typedef typename calculation_type<Point, PointOfSegment>::type calculation_type;
164 // A projected point of points in Integer coordinates must be able to be
165 // represented in FP.
169 dimension<PointOfSegment>::value,
170 typename coordinate_system<PointOfSegment>::type
174 typedef fp_point_type fp_vector_type;
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)
183 RETURN POINT(x1 + b * vx, y1 + b * vy)
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;
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);
197 boost::ignore_unused_variable_warning(strategy);
199 typename result_type<Point, PointOfSegment>::type result;
201 calculation_type const zero = calculation_type();
202 calculation_type const c2 = dot_product(v, v);
203 if ( math::equals(c2, zero) )
205 result.xtd = strategy.apply(p, projected);
206 // assume that the 0-length segment is perpendicular to the Pt->ProjPt vector
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);
216 result.xtd = strategy.apply(p, projected);
220 result.atd = strategy.apply(p1, projected);
224 result.atd = strategy.apply(p2, projected);
235 } // namespace detail
236 #endif // DOXYGEN_NO_DETAIL
238 #ifndef DOXYGEN_NO_STRATEGY_SPECIALIZATIONS
243 template <typename CalculationType, typename Strategy>
244 struct tag<detail::projected_point_ax<CalculationType, Strategy> >
246 typedef strategy_tag_distance_point_segment type;
250 template <typename CalculationType, typename Strategy, typename P, typename PS>
251 struct return_type<detail::projected_point_ax<CalculationType, Strategy>, P, PS>
253 typedef typename detail::projected_point_ax<CalculationType, Strategy>
254 ::template result_type<P, PS>::type type;
258 template <typename CalculationType, typename Strategy>
259 struct comparable_type<detail::projected_point_ax<CalculationType, Strategy> >
261 // Define a projected_point strategy with its underlying point-point-strategy
263 typedef detail::projected_point_ax
266 typename comparable_type<Strategy>::type
271 template <typename CalculationType, typename Strategy>
272 struct get_comparable<detail::projected_point_ax<CalculationType, Strategy> >
274 typedef typename comparable_type
276 detail::projected_point_ax<CalculationType, Strategy>
277 >::type comparable_type;
279 static inline comparable_type apply(detail::projected_point_ax<CalculationType, Strategy> const& )
281 return comparable_type();
286 template <typename CalculationType, typename Strategy, typename P, typename PS>
287 struct result_from_distance<detail::projected_point_ax<CalculationType, Strategy>, P, PS>
290 typedef typename return_type<detail::projected_point_ax<CalculationType, Strategy>, P, PS>::type return_type;
292 template <typename T>
293 static inline return_type apply(detail::projected_point_ax<CalculationType, Strategy> const& , T const& value)
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);
304 } // namespace services
305 #endif // DOXYGEN_NO_STRATEGY_SPECIALIZATIONS
308 }} // namespace strategy::distance
311 }} // namespace boost::geometry
314 #endif // BOOST_GEOMETRY_STRATEGIES_CARTESIAN_DISTANCE_PROJECTED_POINT_AX_HPP