1 // Copyright (c) 2005,2006 INRIA Sophia-Antipolis (France)
2 // All rights reserved.
3 //
4 // This file is part of CGAL (www.cgal.org)
5 //
6 // $URL: https://github.com/CGAL/cgal/blob/v5.3/Number_types/include/CGAL/Number_types/internal_functions_comparison_root_of_2.h $
7 // $Id: internal_functions_comparison_root_of_2.h 0779373 2020-03-26T13:31:46+01:00 Sébastien Loriot
8 // SPDX-License-Identifier: LGPL-3.0-or-later OR LicenseRef-Commercial
9 //
10 //
11 // Author(s) : Sylvain Pion, Monique Teillaud, Athanasios Kakargias
12 // Olivier Devillers
13
14 #ifndef CGAL_NUMBER_TypeS_ROOT_OF_COMPARISON_FUNCTIONS_22_H
15 #define CGAL_NUMBER_TypeS_ROOT_OF_COMPARISON_FUNCTIONS_22_H
16
17 #include <CGAL/enum.h>
18 #include <CGAL/kernel_assertions.h>
19
20 namespace CGAL {
21 namespace internal {
22
23 // Maybe we can trash this
24 /*1 1*/template <class FT>
25 /*1 1*/Comparison_result
compare_11_11(const FT & A1,const FT & B1,const FT & A2,const FT & B2)26 compare_11_11( const FT& A1, const FT& B1,
27 const FT& A2, const FT& B2 )
28 {
29 // Compares roots of (A1 X + B1) and (A2 X + B2).
30 CGAL_precondition( A1 > 0 & A2 > 0 );
31 return CGAL_NTS compare(B2*A1, B1*A2);
32 }
33
34 /*2 1*/template <class FT>
35 /*1 1*/Comparison_result
compare_21_11(const FT & A2,const FT & B2,const FT & C2,const FT & A1,const FT & B1)36 compare_21_11(const FT& A2, const FT& B2, const FT& C2,
37 const FT& A1, const FT& B1 )
38 {
39 // Compares roots of (A1 X + B1) and the smaller of (A2 X^2 + B2 X + C2).
40 CGAL_precondition(A2 > 0);
41
42 // First, we compare the root of P1 to the root of the derivative of P2.
43
44 int cmp = compare_11_11<FT>(A1, B1, A2*2, B2);
45
46 if (cmp > 0)
47 return LARGER;
48
49 // If it doesn't work, we evaluate the sign of P2 at the root of P1.
50
51 FT p2 = B1 * (A1*B2 - A2*B1) - C2 * CGAL_NTS square(A1);
52
53 return CGAL_NTS sign(p2);
54 }
55
56 /*2 2*/template <class FT>
57 /*2 1*/Comparison_result
compare_22_21(const FT & A1p,const FT & B1p,const FT & C1p,const FT & A2p,const FT & B2p,const FT & C2p)58 compare_22_21( const FT& A1p, const FT& B1p, const FT& C1p,
59 const FT& A2p, const FT& B2p, const FT& C2p )
60 {
61 // Compares the larger root of (A1 X^2 + B1 X + C1)
62 // to the smaller root of (A2 X^2 + B2 X + C2)
63 // It boils down to the code from the DFMT paper
64 // by multiplying A* and C* by 2, and B* by -1.
65
66 CGAL_precondition(A1p > 0 & A2p > 0);
67
68 FT A1 = 2 * A1p;
69 FT C1 = 2 * C1p;
70 FT B1 = -B1p;
71
72 FT A2 = 2 * A2p;
73 FT C2 = 2 * C2p;
74 FT B2 = -B2p;
75
76 // Now compares the larger root of (A1 X^2 -2B1 X + C1)
77 // to the smaller root of (A2 X^2 -2B2 X + C2)
78 FT J = calcJ(A1,B1,A2,B2);
79
80 if ( J < 0 ) return LARGER; // r1 > l2
81
82 FT K = calcK(A1,B1,C1,A2,B2,C2);
83
84 if ( K < 0 ) return LARGER; // r1 > l2
85
86 FT Jp = calcJp(B1,C1,B2,C2);
87
88 if ( Jp < 0 ) return SMALLER; // r1 < l2
89
90 FT P4 = calcP4(J,Jp,A1,C1,A2,C2);
91
92 return - CGAL_NTS sign(P4);
93 // if ( P4< FT(0) ) return LARGER; // r1 > l2
94 // if ( P4> FT(0) ) return SMALLER; // r1 < l2
95 // return EQUAL;
96 }
97
98 /*2 2*/template <class FT> inline
99 /*1 2*/Comparison_result
compare_22_12(const FT & A1,const FT & B1,const FT & C1,const FT & A2,const FT & B2,const FT & C2)100 compare_22_12( const FT& A1, const FT& B1, const FT& C1,
101 const FT& A2, const FT& B2, const FT& C2 )
102 {
103 // _22_12 boils down to _22_21 by :
104 // - swapping the two polynomials
105 // - changing the sign of the result
106 return - compare_22_21(A2, B2, C2, A1, B1, C1);
107 }
108
109 /*2 2*/template <class FT>
110 /*1 1*/Comparison_result
compare_22_11(const FT & A1p,const FT & B1p,const FT & C1p,const FT & A2p,const FT & B2p,const FT & C2p)111 compare_22_11( const FT& A1p, const FT& B1p, const FT& C1p,
112 const FT& A2p, const FT& B2p, const FT& C2p )
113 {
114 // Compares the smaller root of (A1 X^2 + B1 X + C1)
115 // to the smaller root of (A2 X^2 + B2 X + C2)
116 // It boils down to the code from the DFMT paper
117 // by multiplying A* and C* by 2, and B* by -1.
118
119 CGAL_precondition(A1p > 0 & A2p > 0);
120
121 FT A1 = 2 * A1p;
122 FT C1 = 2 * C1p;
123 FT B1 = -B1p;
124
125 FT A2 = 2 * A2p;
126 FT C2 = 2 * C2p;
127 FT B2 = -B2p;
128
129 // Compares the smaller root of (A1 X^2 -2B1 X + C1)
130 // to the smaller root of (A2 X^2 -2B2 X + C2)
131 FT J = calcJ(A1,B1,A2,B2);
132 FT K = calcK(A1,B1,C1,A2,B2,C2);
133
134 if (J > 0)
135 {
136 if (K > 0) return SMALLER; // l1 < l2
137
138 FT I1= calcI(A1,B1,C1);
139 FT I2= calcI(A2,B2,C2);
140 FT D = calcD(A1,I1,A2,I2);
141
142 if (D > 0) return SMALLER; // l1 < l2
143
144 FT Jp = calcJp(B1,C1,B2,C2);
145
146 if (Jp < 0) return LARGER; // l1 > l2
147
148 FT P4 = calcP4(I1,I2,K);
149
150 return CGAL_NTS sign(P4);
151 }
152
153 // J <= 0
154 if (K > 0) return LARGER; // l1 > l2
155
156 FT I1= calcI(A1,B1,C1);
157 FT I2= calcI(A2,B2,C2);
158 FT D = calcD(A1,I1,A2,I2);
159
160 if (D < 0) return LARGER; // l1 > l2
161
162 FT Jp = calcJp(B1,C1,B2,C2);
163
164 if (Jp > 0) return SMALLER; // l1 < l2
165
166 FT P4 = calcP4(I1,I2,K);
167
168 return - CGAL_NTS sign(P4);
169 }
170
171 /*2 2*/template <class FT> inline
172 /*2 2*/Comparison_result
compare_22_22(const FT & A1,const FT & B1,const FT & C1,const FT & A2,const FT & B2,const FT & C2)173 compare_22_22( const FT& A1, const FT& B1, const FT& C1,
174 const FT& A2, const FT& B2, const FT& C2 )
175 {
176 // _22_22 boils down to _22_11 by :
177 // - changing the sign of the two roots (X <-> -X in the polynomial)
178 // - swapping the two polynomials
179 return compare_22_11<FT>(A2, -B2, C2, A1, -B1, C1);
180 }
181
182 template <class FT>
calcI(const FT & A,const FT & B,const FT & C)183 inline FT calcI(const FT& A, const FT& B, const FT& C)
184 { return CGAL_NTS square(B)-A*C; }
185
186 template <class FT>
calcJ(const FT & A1,const FT & B1,const FT & A2,const FT & B2)187 inline FT calcJ(const FT& A1, const FT& B1, const FT& A2, const FT& B2)
188 { return A1*B2-A2*B1; }
189
190 template <class FT>
calcK(const FT & A1,const FT & B1,const FT & C1,const FT & A2,const FT & B2,const FT & C2)191 inline FT calcK(const FT& A1, const FT& B1, const FT& C1,
192 const FT& A2, const FT& B2, const FT& C2)
193 { return C1*A2+A1*C2-2*B1*B2; }
194
195 template <class FT>
calcJp(const FT & B1,const FT & C1,const FT & B2,const FT & C2)196 inline FT calcJp(const FT& B1, const FT& C1, const FT& B2, const FT& C2)
197 { return B1*C2-C1*B2; }
198
199 template <class FT>
calcP4(const FT & J,const FT & Jp,const FT & A1,const FT & C1,const FT & A2,const FT & C2)200 inline FT calcP4(const FT& J, const FT& Jp,
201 const FT& A1, const FT& C1,
202 const FT& A2, const FT& C2)
203 { return CGAL_NTS square(A1*C2-C1*A2)-4*J*Jp;}
204
205 template <class FT>
calcP4(const FT & I1,const FT & I2,const FT & K)206 inline FT calcP4(const FT& I1, const FT& I2, const FT& K)
207 { return CGAL_NTS square(K)-4*I1*I2;}
208
209 template <class FT>
calcD(const FT & A1,const FT & I1,const FT & A2,const FT & I2)210 inline FT calcD(const FT& A1, const FT& I1, const FT& A2, const FT& I2)
211 { return I1*CGAL_NTS square(A2) - I2*CGAL_NTS square(A1);}
212
213 } // namespace internal
214 } // namespace CGAL
215
216 #endif // CGAL_NUMBER_TypeS_ROOT_OF_COMPARISON_FUNCTIONS_22_H
217