Debian Codegraph @

deps/boost/geometry/extensions/strategies/cartesian/closest_point.hpp

raw
1 // Boost.Geometry (aka GGL, Generic Geometry Library)
2
3 // Copyright (c) 2007-2013 Barend Gehrels, Amsterdam, the Netherlands.
4 // Copyright (c) 2008-2013 Bruno Lalande, Paris, France.
5 // Copyright (c) 2009-2013 Mateusz Loskot, London, UK.
6 // Copyright (c) 2013 Adam Wulkiewicz, Lodz, Poland.
7 // Copyright (c) 2017 Artem Pavlenko, UK
8
9 // Use, modification and distribution is subject to the Boost Software License,
10 // Version 1.0. (See accompanying file LICENSE_1_0.txt or copy at
11 // http://www.boost.org/LICENSE_1_0.txt)
12
13 #ifndef BOOST_GEOMETRY_STRATEGY_CARTESIAN_CLOSEST_POINT_HPP
14 #define BOOST_GEOMETRY_STRATEGY_CARTESIAN_CLOSEST_POINT_HPP
15
16 #include <boost/type_traits/remove_const.hpp>
17
18 #include <boost/geometry/core/access.hpp>
19 #include <boost/geometry/core/point_type.hpp>
20
21 #include <boost/geometry/algorithms/convert.hpp>
22 #include <boost/geometry/arithmetic/arithmetic.hpp>
23 #include <boost/geometry/arithmetic/dot_product.hpp>
24
25 #include <boost/geometry/strategies/tags.hpp>
26 #include <boost/geometry/strategies/distance.hpp>
27 #include <boost/geometry/strategies/default_distance_result.hpp>
28 #include <boost/geometry/strategies/cartesian/distance_pythagoras.hpp>
29
30 #include <boost/geometry/util/select_coordinate_type.hpp>
31
32 #include <boost/geometry/algorithms/detail/overlay/segment_identifier.hpp>
33
34
35 namespace boost { namespace geometry
36 {
37
38 template <typename Point>
39 struct closest_point_result
40 {
41 typedef Point point_type;
42 typedef typename default_distance_result<Point>::type distance_type;
43 distance_type distance;
44 Point closest_point;
45
46 inline closest_point_result()
47 : distance(distance_type())
48 {}
49 };
50
51
52 namespace strategy { namespace distance
53 {
54
55 template
56 <
57 typename CalculationType = void,
58 typename Strategy = pythagoras<CalculationType>
59 >
60 struct calculate_closest_point
61 {
62 public :
63 // The three typedefs below are necessary to calculate distances
64 // from segments defined in integer coordinates.
65
66 // Integer coordinates can still result in FP distances.
67 // There is a division, which must be represented in FP.
68 // So promote.
69 template <typename Point, typename PointOfSegment>
70 struct calculation_type
71 : promote_floating_point
72 <
73 typename strategy::distance::services::return_type
74 <
75 Strategy,
76 Point,
77 PointOfSegment
78 >::type
79 >
80 {};
81
82
83 public :
84
85 // Helper function
86 template <typename Point1, typename Point2>
87 inline typename calculation_type<Point1, Point2>::type
88 apply_point_point(Point1 const& p1, Point2 const& p2) const
89 {
90 Strategy point_point_strategy;
91 boost::ignore_unused_variable_warning(point_point_strategy);
92 return point_point_strategy.apply(p1, p2);
93 }
94
95 template <typename Point, typename PointOfSegment, typename Result>
96 inline void apply(Point const& p,
97 PointOfSegment const& p1, PointOfSegment const& p2,
98 Result& result) const
99 {
100 assert_dimension_equal<Point, PointOfSegment>();
101
102 typedef typename calculation_type<Point, PointOfSegment>::type calculation_type;
103
104 //// A projected point of points in Integer coordinates must be able to be
105 //// represented in FP.
106 typedef model::point
107 <
108 calculation_type,
109 dimension<PointOfSegment>::value,
110 typename coordinate_system<PointOfSegment>::type
111 > fp_point_type;
112
113 // For convenience
114 typedef fp_point_type fp_vector_type;
115 fp_vector_type v, w;
116
117 geometry::convert(p2, v);
118 geometry::convert(p, w);
119 subtract_point(v, p1);
120 subtract_point(w, p1);
121
122 calculation_type const zero = calculation_type();
123
124 calculation_type const c1 = dot_product(w, v);
125 calculation_type const c2 = dot_product(v, v);
126
127 if (c1 < zero)
128 {
129 result.distance = apply_point_point(p, p1);
130 result.closest_point = p1;
131 }
132 else if(c1 > c2)
133 {
134 result.distance = apply_point_point(p, p2);
135 result.closest_point = p2;
136 }
137 else
138 {
139 Strategy point_point_strategy;
140 boost::ignore_unused_variable_warning(point_point_strategy);
141
142 if (geometry::math::equals(c2, zero))
143 {
144 geometry::convert(p1, result.closest_point);
145 result.distance = apply_point_point(p, p1);
146 return;
147 }
148
149 calculation_type const b = c1 / c2;
150 geometry::convert(p1, result.closest_point);
151 multiply_value(v, b);
152 add_point(result.closest_point, v);
153 result.distance = apply_point_point(p, result.closest_point);
154 }
155 }
156 };
157
158 }} // namespace strategy::distance
159
160
161 }} // namespace boost::geometry
162
163
164 #endif // BOOST_GEOMETRY_STRATEGY_CARTESIAN_CLOSEST_POINT_HPP