solver.go

Functions

Functions

func SolveCubic

SolveCubic finds real roots of the cubic equation ax^3 + bx^2 + cx + d = 0.

Returns roots (not necessarily sorted).

 

The implementation uses the method from:

https://momentsingraphics.de/CubicRoots.html

which is based on Jim Blinn's "How to Solve a Cubic Equation".

func SolveCubic(a, b, c, d float64) []float64 {
	// Handle degenerate case where a is zero
	aRecip := 1.0 / a
	const oneThird = 1.0 / 3.0

	scaledB := b * (oneThird * aRecip)
	scaledC := c * (oneThird * aRecip)
	scaledD := d * aRecip

	// Check if scaling resulted in non-finite values (a is zero or too small)
	if !isFinite(scaledB) || !isFinite(scaledC) || !isFinite(scaledD) {
		// Cubic coefficient is zero or nearly so - solve as quadratic
		return SolveQuadratic(b, c, d)
	}

	// Use scaled coefficients
	c0, c1, c2 := scaledD, scaledC, scaledB

	// (d0, d1, d2) is called "Delta" in the article
	d0 := (-c2)*c2 + c1
	d1 := (-c1)*c2 + c0
	d2 := c2*c0 - c1*c1

	// d is called "Discriminant"
	disc := 4.0*d0*d2 - d1*d1

	// de is called "Depressed.x", Depressed.y = d0
	de := (-2.0*c2)*d0 + d1

	if disc < 0.0 {
		// One real root
		sq := math.Sqrt(-0.25 * disc)
		r := -0.5 * de
		t1 := math.Cbrt(r+sq) + math.Cbrt(r-sq)
		return []float64{t1 - c2}
	} else if disc == 0.0 {
		// Two real roots (one is a double root)
		t1 := math.Copysign(math.Sqrt(-d0), de)
		return []float64{t1 - c2, -2.0*t1 - c2}
	}

	// Three distinct real roots
	th := math.Atan2(math.Sqrt(disc), -de) * oneThird
	thSin, thCos := math.Sincos(th)

	r0 := thCos
	ss3 := thSin * math.Sqrt(3.0)
	r1 := 0.5 * (-thCos + ss3)
	r2 := 0.5 * (-thCos - ss3)
	t := 2.0 * math.Sqrt(-d0)

	return []float64{
		t*r0 - c2,
		t*r1 - c2,
		t*r2 - c2,
	}
}

func SolveCubicInUnitInterval

SolveCubicInUnitInterval returns roots of ax^3 + bx^2 + cx + d = 0 that lie in [0, 1].

This is useful for finding parameter values on Bezier curves.

func SolveCubicInUnitInterval(a, b, c, d float64) []float64 {
	roots := SolveCubic(a, b, c, d)
	return filterRootsToUnitInterval(roots)
}

func SolveQuadratic

SolveQuadratic finds real roots of the quadratic equation ax^2 + bx + c = 0.

Returns roots sorted in ascending order.

 

The function is numerically robust:

- If a is zero or nearly zero, treats as linear equation

- If all coefficients are zero, returns a single 0.0

- Handles edge cases with NaN and Inf gracefully

func SolveQuadratic(a, b, c float64) []float64 {
	// Scale coefficients to avoid overflow in discriminant calculation
	sc0 := c / a
	sc1 := b / a

	// Check if coefficients are valid (not Inf/NaN)
	if !isFinite(sc0) || !isFinite(sc1) {
		return solveQuadraticLinear(b, c)
	}

	// Normal case: valid quadratic
	return solveQuadraticNormal(sc0, sc1)
}

func SolveQuadraticInUnitInterval

SolveQuadraticInUnitInterval returns roots of ax^2 + bx + c = 0 that lie in [0, 1].

This is useful for finding parameter values on Bezier curves.

func SolveQuadraticInUnitInterval(a, b, c float64) []float64 {
	roots := SolveQuadratic(a, b, c)
	return filterRootsToUnitInterval(roots)
}