1 // Copyright (c) 1999,2016
2 // Utrecht University (The Netherlands),
3 // ETH Zurich (Switzerland),
4 // INRIA Sophia-Antipolis (France),
5 // Max-Planck-Institute Saarbruecken (Germany),
6 // and Tel-Aviv University (Israel). All rights reserved.
7 //
8 // This file is part of CGAL (www.cgal.org)
9 //
10 // $URL: https://github.com/CGAL/cgal/blob/v5.3/Homogeneous_kernel/include/CGAL/Homogeneous/predicates_on_pointsH2.h $
11 // $Id: predicates_on_pointsH2.h 0779373 2020-03-26T13:31:46+01:00 Sébastien Loriot
12 // SPDX-License-Identifier: LGPL-3.0-or-later OR LicenseRef-Commercial
13 //
14 //
15 // Author(s) : Stefan Schirra, Olivier Devillers, Mariette Yvinec
16
17
18 #ifndef CGAL_PREDICATES_ON_POINTSH2_H
19 #define CGAL_PREDICATES_ON_POINTSH2_H
20
21 #include <CGAL/Homogeneous/PointH2.h>
22
23 namespace CGAL {
24
25 template < class R>
26 CGAL_KERNEL_INLINE
27 bool
equal_xy(const PointH2<R> & p,const PointH2<R> & q)28 equal_xy(const PointH2<R>& p,
29 const PointH2<R>& q)
30 {
31 typedef typename R::RT RT;
32
33 // Using these references allows to spare calls to [pq].hw().
34 const RT& phw = p.hw();
35 const RT& qhw = q.hw();
36
37 return (p.hx()*qhw == q.hx()*phw) && (p.hy()*qhw == q.hy()*phw);
38 }
39
40 template <class R>
41 CGAL_KERNEL_MEDIUM_INLINE
42 Oriented_side
_where_wrt_L_wedge(const PointH2<R> & p,const PointH2<R> & q)43 _where_wrt_L_wedge( const PointH2<R>& p, const PointH2<R>& q )
44 {
45 Sign xs = CGAL_NTS sign( q.hx()*p.hw() - p.hx()*q.hw() ); // sign( qx - px )
46 Sign ys = CGAL_NTS sign( q.hy()*p.hw() - p.hy()*q.hw() ); // sign( qy - py )
47
48 if (( xs == NEGATIVE ) || ( ys == NEGATIVE ))
49 return ON_NEGATIVE_SIDE;
50 if (( xs == POSITIVE ) && ( ys == POSITIVE ))
51 return ON_POSITIVE_SIDE;
52 return ON_ORIENTED_BOUNDARY;
53 }
54
55 template <class RT>
56 Comparison_result
compare_power_distanceH2(const RT & phx,const RT & phy,const RT & phw,const Quotient<RT> & pwt,const RT & qhx,const RT & qhy,const RT & qhw,const Quotient<RT> & qwt,const RT & rhx,const RT & rhy,const RT & rhw)57 compare_power_distanceH2(const RT& phx, const RT& phy, const RT& phw,
58 const Quotient<RT>& pwt,
59 const RT& qhx, const RT& qhy, const RT& qhw,
60 const Quotient<RT>& qwt,
61 const RT& rhx, const RT& rhy, const RT& rhw)
62 {
63 // returns SMALLER if r is closer to p w.r.t. the power metric
64 RT dphx = rhx * phw - phx * rhw;
65 RT dphy = rhy * phw - phy * rhw;
66 RT dqhx = rhx * qhw - qhx * rhw;
67 RT dqhy = rhy * qhw - qhy * rhw;
68 RT dphw = CGAL_NTS square(phw);
69 RT dqhw = CGAL_NTS square(qhw);
70 RT drhw = CGAL_NTS square(rhw);
71
72 RT npwt = pwt.numerator();
73 RT dpwt = pwt.denominator();
74 RT nqwt = qwt.numerator();
75 RT dqwt = qwt.denominator();
76
77
78 RT dh1 = (CGAL_NTS square(dphx) + CGAL_NTS square(dphy))*dpwt - npwt * dphw * drhw;
79 RT dh2 = (CGAL_NTS square(dqhx) + CGAL_NTS square(dqhy))*dqwt - nqwt * dqhw * drhw;
80 return CGAL_NTS compare(dh1 * dqhw * dqwt, dh2 * dphw * dpwt );
81 }
82
83
84 template <class RT>
85 Oriented_side
power_testH2(const RT & phx,const RT & phy,const RT & phw,const Quotient<RT> & pwt,const RT & qhx,const RT & qhy,const RT & qhw,const Quotient<RT> & qwt,const RT & rhx,const RT & rhy,const RT & rhw,const Quotient<RT> & rwt,const RT & thx,const RT & thy,const RT & thw,const Quotient<RT> & twt)86 power_testH2( const RT &phx, const RT &phy, const RT &phw, const Quotient<RT> &pwt,
87 const RT &qhx, const RT &qhy, const RT &qhw, const Quotient<RT> &qwt,
88 const RT &rhx, const RT &rhy, const RT &rhw, const Quotient<RT> &rwt,
89 const RT &thx, const RT &thy, const RT &thw, const Quotient<RT> &twt)
90 {
91 RT npwt = pwt.numerator();
92 RT dpwt = pwt.denominator();
93 RT nqwt = qwt.numerator();
94 RT dqwt = qwt.denominator();
95 RT nrwt = rwt.numerator();
96 RT drwt = rwt.denominator();
97 RT ntwt = twt.numerator();
98 RT dtwt = twt.denominator();
99
100 RT dphx = phx*phw;
101 RT dphy = phy*phw;
102 RT dphw = CGAL_NTS square(phw);
103 RT dpz = (CGAL_NTS square(phx) + CGAL_NTS square(phy))*dpwt - npwt*dphw;
104
105 RT dqhx = qhx*qhw;
106 RT dqhy = qhy*qhw;
107 RT dqhw = CGAL_NTS square(qhw);
108 RT dqz = (CGAL_NTS square(qhx) + CGAL_NTS square(qhy))*dqwt - nqwt*dqhw;
109
110 RT drhx = rhx*rhw;
111 RT drhy = rhy*rhw;
112 RT drhw = CGAL_NTS square(rhw);
113 RT drz = (CGAL_NTS square(rhx) + CGAL_NTS square(rhy)) *drwt - nrwt*drhw;
114
115 RT dthx = thx*thw;
116 RT dthy = thy*thw;
117 RT dthw = CGAL_NTS square(thw);
118 RT dtz = (CGAL_NTS square(thx) + CGAL_NTS square(thy))*dtwt - ntwt*dthw;
119
120 dthx *= dtwt;
121 dthy *= dtwt;
122 dthw *= dtwt;
123
124 return sign_of_determinant(dphx, dphy, dpz, dphw,
125 dqhx, dqhy, dqz, dqhw,
126 drhx, drhy, drz, drhw,
127 dthx, dthy, dtz, dthw);
128 }
129
130
131 template <class RT>
132 Oriented_side
power_testH2(const RT & phx,const RT & phy,const RT & phw,const Quotient<RT> & pwt,const RT & qhx,const RT & qhy,const RT & qhw,const Quotient<RT> & qwt,const RT & thx,const RT & thy,const RT & thw,const Quotient<RT> & twt)133 power_testH2( const RT &phx, const RT &phy, const RT &phw, const Quotient<RT> &pwt,
134 const RT &qhx, const RT &qhy, const RT &qhw, const Quotient<RT> &qwt,
135 const RT &thx, const RT &thy, const RT &thw, const Quotient<RT> &twt)
136 {
137 RT npwt = pwt.numerator();
138 RT dpwt = pwt.denominator();
139 RT nqwt = qwt.numerator();
140 RT dqwt = qwt.denominator();
141 RT ntwt = twt.numerator();
142 RT dtwt = twt.denominator();
143
144 // Test if we can project on the (x) axis. If not, then on the
145 // (y) axis
146 RT pa, qa, ta;
147
148 if (phx * qhw != qhx * phw )
149 {
150 pa = phx*phw;
151 qa = qhx*qhw;
152 ta = thx*thw;
153 }
154 else
155 {
156 pa = phy*phw;
157 qa = qhy*qhw;
158 ta = thy*thw;
159 }
160
161 RT dphw = CGAL_NTS square(phw);
162 RT dpz = (CGAL_NTS square(phx) + CGAL_NTS square(phy))*dpwt - npwt*dphw;
163
164 RT dqhw = CGAL_NTS square(qhw);
165 RT dqz = (CGAL_NTS square(qhx) + CGAL_NTS square(qhy))*dqwt - nqwt*dqhw;
166
167 RT dthw = CGAL_NTS square(thw);
168 RT dtz = (CGAL_NTS square(thx) + CGAL_NTS square(thy))*dtwt - ntwt*dthw;
169
170 pa *= dtwt;
171 qa *= dtwt;
172 ta *= dtwt;
173
174 return CGAL_NTS compare(pa, qa) * sign_of_determinant(pa, dpz, dphw,
175 qa, dqz, dqhw,
176 ta, dtz, dthw);
177 }
178
179 #if 0
180 // Unused, undocumented, un-functorized.
181 template < class R >
182 CGAL_KERNEL_MEDIUM_INLINE
183 Comparison_result
184 compare_deltax_deltay(const PointH2<R>& p,
185 const PointH2<R>& q,
186 const PointH2<R>& r,
187 const PointH2<R>& s)
188 {
189 return CGAL_NTS compare(
190 CGAL_NTS abs(p.hx()*q.hw() - q.hx()*p.hw()) * r.hw()*s.hw(),
191 CGAL_NTS abs(r.hy()*s.hw() - s.hy()*r.hw()) * p.hw()*q.hw());
192 }
193 #endif
194
195 } //namespace CGAL
196
197 #endif // CGAL_PREDICATES_ON_POINTSH2_H
198