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.
Bx(t) = c0x + c1xt + c2xt2 + c3xt3
By(t) = c0y + c1yt + c2yt2 + c3yt3
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
c0x + c1xt + c2xt2 + c3xt3 – 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 By(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.