1
2#include "equation-solver.h"
3
4#define _USE_MATH_DEFINES
5#include <cmath>
6
7namespace msdfgen {
8
9int solveQuadratic(double x[2], double a, double b, double c) {
10 // a == 0 -> linear equation
11 if (a == 0 || fabs(b) > 1e12*fabs(a)) {
12 // a == 0, b == 0 -> no solution
13 if (b == 0) {
14 if (c == 0)
15 return -1; // 0 == 0
16 return 0;
17 }
18 x[0] = -c/b;
19 return 1;
20 }
21 double dscr = b*b-4*a*c;
22 if (dscr > 0) {
23 dscr = sqrt(dscr);
24 x[0] = (-b+dscr)/(2*a);
25 x[1] = (-b-dscr)/(2*a);
26 return 2;
27 } else if (dscr == 0) {
28 x[0] = -b/(2*a);
29 return 1;
30 } else
31 return 0;
32}
33
34static int solveCubicNormed(double x[3], double a, double b, double c) {
35 double a2 = a*a;
36 double q = 1/9.*(a2-3*b);
37 double r = 1/54.*(a*(2*a2-9*b)+27*c);
38 double r2 = r*r;
39 double q3 = q*q*q;
40 a *= 1/3.;
41 if (r2 < q3) {
42 double t = r/sqrt(q3);
43 if (t < -1) t = -1;
44 if (t > 1) t = 1;
45 t = acos(t);
46 q = -2*sqrt(q);
47 x[0] = q*cos(1/3.*t)-a;
48 x[1] = q*cos(1/3.*(t+2*M_PI))-a;
49 x[2] = q*cos(1/3.*(t-2*M_PI))-a;
50 return 3;
51 } else {
52 double u = (r < 0 ? 1 : -1)*pow(fabs(r)+sqrt(r2-q3), 1/3.);
53 double v = u == 0 ? 0 : q/u;
54 x[0] = (u+v)-a;
55 if (u == v || fabs(u-v) < 1e-12*fabs(u+v)) {
56 x[1] = -.5*(u+v)-a;
57 return 2;
58 }
59 return 1;
60 }
61}
62
63int solveCubic(double x[3], double a, double b, double c, double d) {
64 if (a != 0) {
65 double bn = b/a;
66 if (fabs(bn) < 1e6) // Above this ratio, the numerical error gets larger than if we treated a as zero
67 return solveCubicNormed(x, bn, c/a, d/a);
68 }
69 return solveQuadratic(x, b, c, d);
70}
71
72}
73