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-2020.
8 // Modifications copyright (c) 2014-2020, Oracle and/or its affiliates.
9 // Contributed and/or modified by Menelaos Karavelas, on behalf of Oracle
10 // Contributed and/or modified by Adam Wulkiewicz, on behalf of Oracle
12 // Parts of Boost.Geometry are redesigned from Geodan's Geographic Library
13 // (geolib/GGL), copyright (c) 1995-2010 Geodan, Amsterdam, the Netherlands.
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)
19 #ifndef BOOST_GEOMETRY_STRATEGIES_CARTESIAN_DISTANCE_PROJECTED_POINT_HPP
20 #define BOOST_GEOMETRY_STRATEGIES_CARTESIAN_DISTANCE_PROJECTED_POINT_HPP
23 #include <type_traits>
25 #include <boost/concept_check.hpp>
26 #include <boost/core/ignore_unused.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/point_in_point.hpp>
40 #include <boost/geometry/strategies/cartesian/intersection.hpp>
42 // Helper geometry (projected point on line)
43 #include <boost/geometry/geometries/point.hpp>
46 namespace boost { namespace geometry
50 namespace strategy { namespace distance
54 \brief Strategy for distance point to segment
56 \details Calculates distance using projected-point method, and (optionally) Pythagoras
57 \author Adapted from: http://geometryalgorithms.com/Archive/algorithm_0102/algorithm_0102.htm
58 \tparam CalculationType \tparam_calculation
59 \tparam Strategy underlying point-point distance strategy
60 \par Concepts for Strategy:
61 - cartesian_distance operator(Point,Point)
62 \note If the Strategy is a "comparable::pythagoras", this strategy
63 automatically is a comparable projected_point strategy (so without sqrt)
67 [link geometry.reference.algorithms.distance.distance_3_with_strategy distance (with strategy)]
73 typename CalculationType = void,
74 typename Strategy = pythagoras<CalculationType>
79 typedef within::cartesian_point_point equals_point_point_strategy_type;
81 typedef intersection::cartesian_segments
84 > relate_segment_segment_strategy_type;
86 static inline relate_segment_segment_strategy_type get_relate_segment_segment_strategy()
88 return relate_segment_segment_strategy_type();
91 typedef within::cartesian_winding
93 void, void, CalculationType
94 > point_in_geometry_strategy_type;
96 static inline point_in_geometry_strategy_type get_point_in_geometry_strategy()
98 return point_in_geometry_strategy_type();
101 // The three typedefs below are necessary to calculate distances
102 // from segments defined in integer coordinates.
104 // Integer coordinates can still result in FP distances.
105 // There is a division, which must be represented in FP.
107 template <typename Point, typename PointOfSegment>
108 struct calculation_type
109 : promote_floating_point
111 typename strategy::distance::services::return_type
120 template <typename Point, typename PointOfSegment>
121 inline typename calculation_type<Point, PointOfSegment>::type
122 apply(Point const& p, PointOfSegment const& p1, PointOfSegment const& p2) const
124 assert_dimension_equal<Point, PointOfSegment>();
126 typedef typename calculation_type<Point, PointOfSegment>::type calculation_type;
128 // A projected point of points in Integer coordinates must be able to be
129 // represented in FP.
133 dimension<PointOfSegment>::value,
134 typename coordinate_system<PointOfSegment>::type
138 typedef fp_point_type fp_vector_type;
141 Algorithm [p: (px,py), p1: (x1,y1), p2: (x2,y2)]
142 VECTOR v(x2 - x1, y2 - y1)
143 VECTOR w(px - x1, py - y1)
147 RETURN POINT(x1 + b * vx, y1 + b * vy)
150 // v is multiplied below with a (possibly) FP-value, so should be in FP
151 // For consistency we define w also in FP
152 fp_vector_type v, w, projected;
154 geometry::convert(p2, v);
155 geometry::convert(p, w);
156 geometry::convert(p1, projected);
157 subtract_point(v, projected);
158 subtract_point(w, projected);
161 boost::ignore_unused(strategy);
163 calculation_type const zero = calculation_type();
164 calculation_type const c1 = dot_product(w, v);
167 return strategy.apply(p, p1);
169 calculation_type const c2 = dot_product(v, v);
172 return strategy.apply(p, p2);
175 // See above, c1 > 0 AND c2 > c1 so: c2 != 0
176 calculation_type const b = c1 / c2;
178 multiply_value(v, b);
179 add_point(projected, v);
181 return strategy.apply(p, projected);
184 template <typename CT>
185 inline CT vertical_or_meridian(CT const& lat1, CT const& lat2) const
192 #ifndef DOXYGEN_NO_STRATEGY_SPECIALIZATIONS
196 template <typename CalculationType, typename Strategy>
197 struct tag<projected_point<CalculationType, Strategy> >
199 typedef strategy_tag_distance_point_segment type;
203 template <typename CalculationType, typename Strategy, typename P, typename PS>
204 struct return_type<projected_point<CalculationType, Strategy>, P, PS>
205 : projected_point<CalculationType, Strategy>::template calculation_type<P, PS>
210 template <typename CalculationType, typename Strategy>
211 struct comparable_type<projected_point<CalculationType, Strategy> >
213 // Define a projected_point strategy with its underlying point-point-strategy
215 typedef projected_point
218 typename comparable_type<Strategy>::type
223 template <typename CalculationType, typename Strategy>
224 struct get_comparable<projected_point<CalculationType, Strategy> >
226 typedef typename comparable_type
228 projected_point<CalculationType, Strategy>
229 >::type comparable_type;
231 static inline comparable_type apply(projected_point<CalculationType, Strategy> const& )
233 return comparable_type();
238 template <typename CalculationType, typename Strategy, typename P, typename PS>
239 struct result_from_distance<projected_point<CalculationType, Strategy>, P, PS>
242 typedef typename return_type<projected_point<CalculationType, Strategy>, P, PS>::type return_type;
244 template <typename T>
245 static inline return_type apply(projected_point<CalculationType, Strategy> const& , T const& value)
248 return result_from_distance<Strategy, P, PS>::apply(s, value);
253 // Get default-strategy for point-segment distance calculation
254 // while still have the possibility to specify point-point distance strategy (PPS)
255 // It is used in algorithms/distance.hpp where users specify PPS for distance
256 // of point-to-segment or point-to-linestring.
257 // Convenient for geographic coordinate systems especially.
258 template <typename Point, typename PointOfSegment, typename Strategy>
259 struct default_strategy
261 point_tag, segment_tag, Point, PointOfSegment,
262 cartesian_tag, cartesian_tag, Strategy
265 typedef strategy::distance::projected_point
270 std::is_void<Strategy>::value,
271 typename default_strategy
273 point_tag, point_tag, Point, PointOfSegment,
274 cartesian_tag, cartesian_tag
281 template <typename PointOfSegment, typename Point, typename Strategy>
282 struct default_strategy
284 segment_tag, point_tag, PointOfSegment, Point,
285 cartesian_tag, cartesian_tag, Strategy
288 typedef typename default_strategy
290 point_tag, segment_tag, Point, PointOfSegment,
291 cartesian_tag, cartesian_tag, Strategy
296 } // namespace services
297 #endif // DOXYGEN_NO_STRATEGY_SPECIALIZATIONS
300 }} // namespace strategy::distance
303 }} // namespace boost::geometry
306 #endif // BOOST_GEOMETRY_STRATEGIES_CARTESIAN_DISTANCE_PROJECTED_POINT_HPP