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