Bezier Y at X Algorithm

A few requests for the algorithm behind the Bezier y-at-x and x-at-y methods have been received.  The code is self-contained in the com.degrafa.geometry.AdvancedQuadraticBezier and AdvancedCubicBezier classes.  Both classes accept control points in their constructors and use classes from com.degrafa.utilities.math .  The latter classes are independent from any internal Degrafa architecture.  So, people who maintain their own Bezier class libraries have a path to include the y-at-x and x-at-y capability.

Finding the y-coordinates at a given x or the x-coordinates at a given y is an exercise in root-finding.  Suppose the Bezier curve is B(t) which is quadratic or cubic in t.  For the cubic Bezier, the vector equation for the curve produces two scalar equations, one for the x-coordinates and one for the y-coordinates, i.e.

B_x(t) = c_0x + c_1xt + c_2xt² + c_3xt³

B_y(t) = c_0y + c_1yt + c_2yt² + c_3yt³

For the y-at-x case, the required y-coordinates are found at the t-parameters corresponding to the intersection of B(t) with the vertical line x = a, or

c_0x + c_1xt + c_2xt² + c_3xt³ – a = 0

The problem reduces to one of finding roots of a cubic polynomial. This starts by finding one root.  Synthetic division is used to factor out the single root leaving a quadratic polynomial.  The two possible roots of that polynomial are found with the venerable quadratic formula.  Only roots in [0,1] are valid solutions to the y-at-x problem.  The roots (values of t) are used to compute the y-coordinates using the equation for B_y(t).  With a quadratic Bezier, roots are found directly with the quadratic formula.

The x-at-y problem is similar in that the required x-coordinates are the intersection of B(t) with the horizontal line y = a.  There is one degenerate case where the Bezier curve is a segment of a horizontal or vertical line and the single parameter describing the line is the input value.  For example, a cubic Bezier curve is the line x = a and the y-coordinates for x = a are desired.  Theoretically, there are an infinite number.  The Degrafa code does not currently handle this case.  Some argue that no values should be returned while otheres argue that perhaps t = 0, t = 1/2 and t = 1 should be returned.

Given the rarity of this case actually occurring, the argument is postponed in lieu of more important developments.  Tomorrow, I’ll post some code from the demos.