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