1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
|
// Copyright (c) 2000,2001
// Utrecht University (The Netherlands),
// ETH Zurich (Switzerland),
// INRIA Sophia-Antipolis (France),
// Max-Planck-Institute Saarbruecken (Germany),
// and Tel-Aviv University (Israel). All rights reserved.
//
// This file is part of CGAL (www.cgal.org)
//
// $URL: https://github.com/CGAL/cgal/blob/v6.1.1/Kernel_23/include/CGAL/Kernel/Conic_misc.h $
// $Id: include/CGAL/Kernel/Conic_misc.h 08b27d3db14 $
// SPDX-License-Identifier: LGPL-3.0-or-later OR LicenseRef-Commercial
//
//
// Author(s) : Bernd Gaertner, Sven Schoenherr <sven@inf.ethz.ch>
#ifndef CGAL_CONIC_MISC_H
#define CGAL_CONIC_MISC_H
#include <cmath>
#include <CGAL/number_utils.h>
#include <CGAL/kernel_assertions.h>
#include <boost/math/special_functions/cbrt.hpp>
namespace CGAL {
template < class R>
class Conic_2;
enum Conic_type
{
HYPERBOLA = -1,
PARABOLA,
ELLIPSE
};
typedef CGAL::Bounded_side Convex_side;
const Convex_side ON_CONVEX_SIDE = CGAL::ON_BOUNDED_SIDE;
const Convex_side ON_NONCONVEX_SIDE = CGAL::ON_UNBOUNDED_SIDE;
template < class NT >
NT best_value (NT *values, int nr_values,
NT a2, NT a1, NT a0,
NT b3, NT b2, NT b1, NT b0)
{
bool det_positive = false;
NT d, q, max_det = 0, det, best = -1;
for (int i=0; i<nr_values; ++i) {
NT x = values[i];
d = (a2*x+a1)*x+a0;
q = ((b3*x+b2)*x+b1)*x+b0;
det = d*d*d/(q*q);
// if q==0, this root value doesn't qualify for the
// best value. Under roundoff errors, q might be very
// small but nonzero, so that the value is erroneously
// being considered; however, d should be very small
// in this case as well, so that det won't compete
// for max_det below.
if (CGAL_NTS is_positive(det) && !CGAL_NTS is_zero(q))
if (!det_positive || (det > max_det)) {
max_det = det;
best = x;
det_positive = true;
}
}
CGAL_kernel_precondition (det_positive);
return best;
}
template < class NT >
int solve_cubic (NT c3, NT c2, NT c1, NT c0,
NT& r1, NT& r2, NT& r3)
{
if (c3 == 0.0) {
// quadratic equation
if (c2 == 0) {
// linear equation
CGAL_kernel_precondition (c1 != 0);
r1 = -c0/c1;
return 1;
}
NT D = c1*c1-4*c2*c0;
if (D < 0.0)
// only complex roots
return 0;
if (D == 0.0) {
// one real root
r1 = -c1/(2.0*c2);
return 1;
}
// two real roots
r1 = (-c1 + CGAL_NTS sqrt(D))/(2.0*c2);
r2 = (-c1 - CGAL_NTS sqrt(D))/(2.0*c2);
return 2;
}
// cubic equation
// define the gamma_i
NT g2 = c2/c3,
g1 = c1/c3,
g0 = c0/c3;
// define a, b
NT a = g1 - g2*g2/3.0,
b = 2.0*g2*g2*g2/27.0 - g1*g2/3.0 + g0;
if (a == 0) {
// one real root
r1 = boost::math::cbrt(-b) - g2 / 3.0;
// r1 = std::exp(std::log(-b) / 3.0) - g2 / 3.0;
return 1;
}
// define D
NT D = a*a*a/27.0 + b*b/4.0;
if (D >= 0.0) {
// real case
NT u = boost::math::cbrt(-b / 2.0 + CGAL_NTS sqrt(D)),
// NT u = std::exp(std::log(-b/2.0 + CGAL_NTS sqrt(D)) / 3.0),
alpha = 1.0 - a/(3.0*u*u);
if (D == 0) {
// two distinct real roots
r1 = u*alpha - g2/3.0;
r2 = -0.5*alpha*u - g2/3.0;
return 2;
}
// one real root
r1 = u*alpha - g2/3.0;
return 1;
}
// complex case
NT r_prime = CGAL_NTS sqrt(-a/3),
phi_prime = acos (-b/(2.0*r_prime*r_prime*r_prime))/3.0,
u_R = r_prime * cos (phi_prime),
u_I = r_prime * sin (phi_prime);
// three distinct real roots
r1 = 2.0*u_R - g2/3.0;
r2 = -u_R + u_I*std::sqrt(3.0) - g2/3.0;
r3 = -u_R - u_I*std::sqrt(3.0) - g2/3.0;
return 3;
}
} //namespace CGAL
#endif // CGAL_CONIC_MISC_H
// ===== EOF ==================================================================
|
