]>
Commit | Line | Data |
---|---|---|
7c673cae FG |
1 | // Boost.Geometry (aka GGL, Generic Geometry Library) |
2 | ||
3 | // Copyright (c) 2007-2015 Barend Gehrels, Amsterdam, the Netherlands. | |
4 | // Copyright (c) 2008-2015 Bruno Lalande, Paris, France. | |
5 | // Copyright (c) 2009-2015 Mateusz Loskot, London, UK. | |
6 | ||
7 | // This file was modified by Oracle on 2015. | |
8 | // Modifications copyright (c) 2015, Oracle and/or its affiliates. | |
9 | ||
10 | // Contributed and/or modified by Menelaos Karavelas, on behalf of Oracle | |
11 | ||
12 | // Parts of Boost.Geometry are redesigned from Geodan's Geographic Library | |
13 | // (geolib/GGL), copyright (c) 1995-2010 Geodan, Amsterdam, the Netherlands. | |
14 | ||
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) | |
18 | ||
19 | #ifndef BOOST_GEOMETRY_STRATEGIES_CARTESIAN_SIDE_BY_TRIANGLE_HPP | |
20 | #define BOOST_GEOMETRY_STRATEGIES_CARTESIAN_SIDE_BY_TRIANGLE_HPP | |
21 | ||
22 | #include <boost/mpl/if.hpp> | |
23 | #include <boost/type_traits/is_integral.hpp> | |
24 | #include <boost/type_traits/is_void.hpp> | |
25 | ||
26 | #include <boost/geometry/arithmetic/determinant.hpp> | |
27 | #include <boost/geometry/core/access.hpp> | |
28 | #include <boost/geometry/util/select_coordinate_type.hpp> | |
29 | #include <boost/geometry/strategies/side.hpp> | |
30 | ||
31 | #include <boost/geometry/algorithms/detail/relate/less.hpp> | |
32 | #include <boost/geometry/algorithms/detail/equals/point_point.hpp> | |
33 | ||
34 | ||
35 | namespace boost { namespace geometry | |
36 | { | |
37 | ||
38 | namespace strategy { namespace side | |
39 | { | |
40 | ||
41 | /*! | |
42 | \brief Check at which side of a segment a point lies: | |
43 | left of segment (> 0), right of segment (< 0), on segment (0) | |
44 | \ingroup strategies | |
45 | \tparam CalculationType \tparam_calculation | |
46 | */ | |
47 | template <typename CalculationType = void> | |
48 | class side_by_triangle | |
49 | { | |
50 | template <typename Policy> | |
51 | struct eps_policy | |
52 | { | |
53 | eps_policy() {} | |
54 | template <typename Type> | |
55 | eps_policy(Type const& a, Type const& b, Type const& c, Type const& d) | |
56 | : policy(a, b, c, d) | |
57 | {} | |
58 | Policy policy; | |
59 | }; | |
60 | ||
61 | struct eps_empty | |
62 | { | |
63 | eps_empty() {} | |
64 | template <typename Type> | |
65 | eps_empty(Type const&, Type const&, Type const&, Type const&) {} | |
66 | }; | |
67 | ||
68 | public : | |
69 | ||
70 | // Template member function, because it is not always trivial | |
71 | // or convenient to explicitly mention the typenames in the | |
72 | // strategy-struct itself. | |
73 | ||
74 | // Types can be all three different. Therefore it is | |
75 | // not implemented (anymore) as "segment" | |
76 | ||
77 | template | |
78 | < | |
79 | typename CoordinateType, | |
80 | typename PromotedType, | |
81 | typename P1, | |
82 | typename P2, | |
83 | typename P, | |
84 | typename EpsPolicy | |
85 | > | |
86 | static inline | |
87 | PromotedType side_value(P1 const& p1, P2 const& p2, P const& p, EpsPolicy & eps_policy) | |
88 | { | |
89 | CoordinateType const x = get<0>(p); | |
90 | CoordinateType const y = get<1>(p); | |
91 | ||
92 | CoordinateType const sx1 = get<0>(p1); | |
93 | CoordinateType const sy1 = get<1>(p1); | |
94 | CoordinateType const sx2 = get<0>(p2); | |
95 | CoordinateType const sy2 = get<1>(p2); | |
96 | ||
97 | PromotedType const dx = sx2 - sx1; | |
98 | PromotedType const dy = sy2 - sy1; | |
99 | PromotedType const dpx = x - sx1; | |
100 | PromotedType const dpy = y - sy1; | |
101 | ||
102 | eps_policy = EpsPolicy(dx, dy, dpx, dpy); | |
103 | ||
104 | return geometry::detail::determinant<PromotedType> | |
105 | ( | |
106 | dx, dy, | |
107 | dpx, dpy | |
108 | ); | |
109 | ||
110 | } | |
111 | ||
112 | template | |
113 | < | |
114 | typename CoordinateType, | |
115 | typename PromotedType, | |
116 | typename P1, | |
117 | typename P2, | |
118 | typename P | |
119 | > | |
120 | static inline | |
121 | PromotedType side_value(P1 const& p1, P2 const& p2, P const& p) | |
122 | { | |
123 | eps_empty dummy; | |
124 | return side_value<CoordinateType, PromotedType>(p1, p2, p, dummy); | |
125 | } | |
126 | ||
127 | ||
128 | template | |
129 | < | |
130 | typename CoordinateType, | |
131 | typename PromotedType, | |
132 | bool AreAllIntegralCoordinates | |
133 | > | |
134 | struct compute_side_value | |
135 | { | |
136 | template <typename P1, typename P2, typename P, typename EpsPolicy> | |
137 | static inline PromotedType apply(P1 const& p1, P2 const& p2, P const& p, EpsPolicy & epsp) | |
138 | { | |
139 | return side_value<CoordinateType, PromotedType>(p1, p2, p, epsp); | |
140 | } | |
141 | }; | |
142 | ||
143 | template <typename CoordinateType, typename PromotedType> | |
144 | struct compute_side_value<CoordinateType, PromotedType, false> | |
145 | { | |
146 | template <typename P1, typename P2, typename P, typename EpsPolicy> | |
147 | static inline PromotedType apply(P1 const& p1, P2 const& p2, P const& p, EpsPolicy & epsp) | |
148 | { | |
149 | // For robustness purposes, first check if any two points are | |
150 | // the same; in this case simply return that the points are | |
151 | // collinear | |
152 | if (geometry::detail::equals::equals_point_point(p1, p2) | |
153 | || geometry::detail::equals::equals_point_point(p1, p) | |
154 | || geometry::detail::equals::equals_point_point(p2, p)) | |
155 | { | |
156 | return PromotedType(0); | |
157 | } | |
158 | ||
159 | // The side_by_triangle strategy computes the signed area of | |
160 | // the point triplet (p1, p2, p); as such it is (in theory) | |
161 | // invariant under cyclic permutations of its three arguments. | |
162 | // | |
163 | // In the context of numerical errors that arise in | |
164 | // floating-point computations, and in order to make the strategy | |
165 | // consistent with respect to cyclic permutations of its three | |
166 | // arguments, we cyclically permute them so that the first | |
167 | // argument is always the lexicographically smallest point. | |
168 | ||
169 | geometry::detail::relate::less less; | |
170 | if (less(p, p1)) | |
171 | { | |
172 | if (less(p, p2)) | |
173 | { | |
174 | // p is the lexicographically smallest | |
175 | return side_value<CoordinateType, PromotedType>(p, p1, p2, epsp); | |
176 | } | |
177 | else | |
178 | { | |
179 | // p2 is the lexicographically smallest | |
180 | return side_value<CoordinateType, PromotedType>(p2, p, p1, epsp); | |
181 | } | |
182 | } | |
183 | ||
184 | if (less(p1, p2)) | |
185 | { | |
186 | // p1 is the lexicographically smallest | |
187 | return side_value<CoordinateType, PromotedType>(p1, p2, p, epsp); | |
188 | } | |
189 | else | |
190 | { | |
191 | // p2 is the lexicographically smallest | |
192 | return side_value<CoordinateType, PromotedType>(p2, p, p1, epsp); | |
193 | } | |
194 | } | |
195 | }; | |
196 | ||
197 | ||
198 | template <typename P1, typename P2, typename P> | |
199 | static inline int apply(P1 const& p1, P2 const& p2, P const& p) | |
200 | { | |
201 | typedef typename coordinate_type<P1>::type coordinate_type1; | |
202 | typedef typename coordinate_type<P2>::type coordinate_type2; | |
203 | typedef typename coordinate_type<P>::type coordinate_type3; | |
204 | ||
205 | typedef typename boost::mpl::if_c | |
206 | < | |
207 | boost::is_void<CalculationType>::type::value, | |
208 | typename select_most_precise | |
209 | < | |
210 | typename select_most_precise | |
211 | < | |
212 | coordinate_type1, coordinate_type2 | |
213 | >::type, | |
214 | coordinate_type3 | |
215 | >::type, | |
216 | CalculationType | |
217 | >::type coordinate_type; | |
218 | ||
219 | // Promote float->double, small int->int | |
220 | typedef typename select_most_precise | |
221 | < | |
222 | coordinate_type, | |
223 | double | |
224 | >::type promoted_type; | |
225 | ||
226 | bool const are_all_integral_coordinates = | |
227 | boost::is_integral<coordinate_type1>::value | |
228 | && boost::is_integral<coordinate_type2>::value | |
229 | && boost::is_integral<coordinate_type3>::value; | |
230 | ||
231 | eps_policy< math::detail::equals_factor_policy<promoted_type> > epsp; | |
232 | promoted_type s = compute_side_value | |
233 | < | |
234 | coordinate_type, promoted_type, are_all_integral_coordinates | |
235 | >::apply(p1, p2, p, epsp); | |
236 | ||
237 | promoted_type const zero = promoted_type(); | |
238 | return math::detail::equals_by_policy(s, zero, epsp.policy) ? 0 | |
239 | : s > zero ? 1 | |
240 | : -1; | |
241 | } | |
242 | ||
243 | }; | |
244 | ||
245 | ||
246 | #ifndef DOXYGEN_NO_STRATEGY_SPECIALIZATIONS | |
247 | namespace services | |
248 | { | |
249 | ||
250 | template <typename CalculationType> | |
251 | struct default_strategy<cartesian_tag, CalculationType> | |
252 | { | |
253 | typedef side_by_triangle<CalculationType> type; | |
254 | }; | |
255 | ||
256 | } | |
257 | #endif | |
258 | ||
259 | }} // namespace strategy::side | |
260 | ||
261 | }} // namespace boost::geometry | |
262 | ||
263 | ||
264 | #endif // BOOST_GEOMETRY_STRATEGIES_CARTESIAN_SIDE_BY_TRIANGLE_HPP |