Does the point lie on the Bezier curve?

Someone recently asked me how to tell if a point lies on a Bezier curve.

For the purposes of discussion, it’s a quadratic Bezier curve and all 3 control points are known (or the start and end points and the 1 control point if you prefer). You can read more about the reverse process of finding the control points here, which is the reference point of that person’s question.

The answer is actually straightforward. Substitute everything into the Bezier curve equation and solve for t. Here’s the quadratic Bezier equation:
B(t) = (1-t)^2 * p0 + 2(1-t)t * p1 + t^2 * p2

Let’s say p0 is [1,1] and p1 is [1.5,4.5] and p2 is [2,3]. We’ll keep the points in 2 dimensions to keep the maths working less cumbersome. And let’s say the point you want to check is [1.8,3.4]. We substitute all the points into the equation, and we get this:

[1.8,3.4] = (1-t)^2 * [1,1] + 2(1-t)t * [1.5,4.5] + t^2 * [2,3]

I know, it doesn’t look pretty. But hey, we’re doing this by hand. If you’re writing code to generalise the solution, the code will probably look just a little uglier, but the solution will come out faster. Like probably instantly given the current modern processors.

Because we’re dealing with 2 dimensional points, that equation splits into 2 separate equations (with scalars instead of vectors as coefficients), like so:
1.8 = (1-t)^2 * 1 + 2(1-t)t * 1.5 + t^2 * 2
3.4 = (1-t)^2 * 1 + 2(1-t)t * 4.5 + t^2 * 3

If you have 3 dimensional points, you’d have 3 equations. Note that even then, the degree of your equations remains as 2. The degree of the Bezier curve is independent of the number of dimensions you’re working with.

If you simplify
1.8 = (1-t)^2 * 1 + 2(1-t)t * 1.5 + t^2 * 2

You get t = 0.8. It so happens that in this case, there’s only one solution.

If you simplify
3.4 = (1-t)^2 * 1 + 2(1-t)t * 4.5 + t^2 * 3

You get
5*t^2 – 7*t + 2.4 = 0

and after solving for that, you get t = 0.6 or t = 0.8 (you’re a smart person, you know how to solve a quadratic equation, right?)

Now, the solution t=0.8 appears in the solution sets of both equations. Therefore, the point [1.8,3.4] lies on the Bezier curve. In fact, t=0.8 is the t value.

Multiple solutions

What if you get multiple t values appearing in multiple solution sets of equations?

Consider the case where p0 is [1,1], p1 is [2,3], and p2 is [1,1]. Notice that the start and end points are the same point. Let’s say you want to know if the point [1,1] lies on the curve (yes I know it’s the same point). Substituting all the points, we get:

[1,1] = (1-t)^2 * [1,1] + 2(1-t)t * [2,3] + t^2 * [1,1]

This gives us the 2 equations:
1 = 1 – 2*t + t^2 + 4*t – 4*t^2 + t^2
1 = 1 – 2*t + t^2 + 6*t – 6*t^2 + t^2

They simplify to:
2*t^2 – 2*t = 0
4*t^2 – 4*t = 0

Hey presto! The solution set is t=0 or t=1 for both equations. Therefore, the point [1,1] lies on the curve. In fact, it lies on the curve where t=0 or t=1. And t=0 and t=1 happens to coincide with the start and end points respectively.

The whole point (haha!) is that, as long as you have at least one value of t that appears in the solution sets of all the equations, then said point you’re checking lies on the curve.

Higher degree Bezier curves

This is a toughie. If you have a cubic Bezier curve, then you’re solving a degree 3 polynomial (of t). If you have a Bezier curve of degree N, then you’re solving a degree N polynomial.

There are algorithms to solve generic degree polynomials, but they are out of scope here. Assuming the highest degree of Bezier curves you’ll ever work with is 3 (cubic), then this Wikipedia article on cubic functions will help. Remember, cubic Bezier curve equations are still cubic equations.

Higher dimensionality

The number of dimensions you’re working with determines the number of equations you need to solve. If you’re working with 5 dimensional points, then you need to solve for 5 equations.

For example, if you’re working with cubic Bezier curves and using 5 dimensional points, then you need to solve 5 cubic functions. You will have possibly 3 (unique) t values for each equation. Let’s say your solution sets are as follows:
t = -1, 3, 5
t = 0, 1, 3
t = -2, 2, 3
t = 3, 3, 4 (yay repeated values!)
t = 3, 6, 8

The value t=3 appears in all 5 sets of solutions, therefore your point lies on the curve.

Keep it real

In the process of solving your equations, there’s a possibility that you might get imaginary solutions. You know, those involving the square root of -1. Dismiss them.

Your Bezier curve is in the real world. The point you’re checking must therefore also lie in the real world.

Unless you’re working with some abstract imaginary Bezier curves on an advanced maths paper. Then good luck to you! The logic above for solving still applies.

Actual applications

When applying the above, you don’t usually get nice numbers like [1.8,3.4] lying on the curve with t=0.8. You get numbers with lots of numbers behind the decimal point that seems to continue forever. You don’t get exact values.

What if you get a t=0.798 for one equation, and t=0.802 for another equation?

Use your common sense. Set an error margin for what is acceptable.

My suggestion is to NOT use the values of t to check for the margin. Substitute the values of t into the equation, and then check the points if they’re within the error margin.

This means you don’t check the difference between t=0.798 and t=0.802, which is 0.04. Is 0.04 within your error margin? Maybe. But you’re not checking for this.

You substitute t=0.798 and t=0.802 into the equation, and you get 2 points: [1.798,3.40198] and [1.802,3.39798]

Then you say, “Are these points close enough that I consider them to be the same point?” Use whatever you think is appropriate. I think the Euclidean distance norm works fine. Then check if that “close enough” criteria is within your error margin.

If you’re checking for [1.8,3.4], then ask yourself, “Is [1.8,3.4] close enough to [1.798,3.40198]? And is [1.8,3.4] close enough to [1.802,3.39798]?”

Obviously, doing this by hand sucks big time. Good thing you’re a programmer.

Help! Getting a “nice” reverse engineered Bézier curve

Commenter Timo wants to know how to get a nice shape for a reverse engineered Bézier curve.

The question started from calculating the control points of a cubic Bézier curve if you’re given 4 points that lie on the curve, assuming the first and last given points were also the first and last control points. I wrote a similar article for a quadratic Bézier curve too.

To sum up, you have 1 degree of freedom when working on a quadratic Bézier curve. In the case of a cubic Bézier curve, you have 2 degrees of freedom, meaning 2 variables in the calculation that you have to decide on. Now this posed a problem, because there are an infinite number of solutions. How do you decide on a numeric value?

Well, for a quadratic Bézier curve, the simplest and obvious option is to choose the second given point (since the first and last control points are determinable) to be at the halfway mark. For a cubic Bézier curve, the second and third given points are chosen to be at the 1/3 and 2/3 mark along the curve respectively. Now this may or may not be suitable, but it does give you something to start with.

I want to state right now, that I had not been doing formal mathematics for a while. There is a limit to what I know, and I’m not an expert. I just know enough to figure out how to solve problems. Sometimes, it’s not enough. Keep that in mind.

“Nice curve” is subjective

Now Timo’s problem is getting a better shaped cubic Bézier curve from those calculations. Since the 4 given points are fixed, and the first and last control points are also fixed, the only thing you can manipulate are the second and third control points. Which in turn means deciding on values of u and v to get a “nice” cubic Bézier curve in the end.

This, “niceness”, is a subjective criteria. How do you determine if a cubic Bézier curve looks nice? Remember that we don’t have the control points yet. So we don’t know how the curve looks like. So we don’t even know if manipulating the second and third control point to not be at 1/3 and 2/3 will result in a nice curve. It’s a chicken and egg problem.

Apportioned chord length

During the correspondence with Timo, some solutions were discussed. The next simplest set of values to try for u and v are calculated based on the given points.

Let d1 be the distance between the first and second given point.
Let d2 be the distance between the second and third given point.
Let d3 be the distance between the third and last (fourth) given point.

Then let u = d1/(d1 + d2 + d3) and v = (d1 + d2)/(d1 + d2 + d3). This should result in a curve that’s “better shaped” than the (u,v) pair (1/3, 2/3). When I wrote that article for the cubic curve version, this was the next default set of values for u and v, but I didn’t want to add too much more. Well, nobody asked, so I left it as it was.

It turns out that Don Lancaster already wrote about it. He called it “apportioned chords” method.
http://www.tinaja.com/glib/nubz4pts1.pdf

Inflection points

Then Timo had another problem. He wanted the second and third given points to also lie at the “loop tips”. What are loop tips? After some clarification, I believe Timo is referring to the inflection points on the curve. An inflection point

is a point on a curve at which the curvature (second derivative) changes signs. The curve changes from being concave upwards (positive curvature) to concave downwards (negative curvature), or vice versa.

A cubic Bézier curve can have 0, 1 or 2 inflection points. If it’s a straight line, it has 0. If it’s U-shaped, it has 1. And if it zigzags, it has 2. And Adrian Colomitchi proved that there are at most 2 inflection points on a cubic Bézier curve.

UPDATE: The following diagram is wrong. Please refer to this article for the correct version. I was thinking of points where the second derivative was zero, not when it changed signs (as defined above).

Inflection points

As you can see, inflection points don’t necessarily have to coincide with the given points.

By the way, I used Paint.NET for the illustration. I took a screenshot of me drawing the curve, still with the given points visible (noted by the small squares). Paint.NET appears to have succeeded in doing the very thing Timo wants, to render a cubic Bézier curve using 4 given points. Of course, I’m assuming the image editor is using cubic Bézier curves…

The math paper

I found another reference with a more explicit mathematical formulation to help Timo.
http://www.cis.usouthal.edu/~hain/general/Publications/Bezier/bezier%20cccg04%20paper.pdf

As of this writing, page 3 of that paper explicitly shows the calculation needed to find the inflection points of a cubic Bézier curve, if they exist. Let me emphasise that again. The curve might have 2 inflection points, only 1 inflection point, or none at all (a straight line, the trivial version of a Bezier curve, has no inflection points).

Maximum curvature

Then Timo found another forum posting for the fast calculation of maximum curvature. An inflection point would have the “maximum curvature”. The problem with that solution is that it assumes we have the control points.

So my suggestion was to do iteration. Use my method to get a set of control points. Perhaps use the apportioned chords to start off with a good set of control points. Then apply the maximum curvature solution to find the inflection points and the associated values of t. With those values of t, pump them back into my method to find a new set of control points. Pump those control points into the maximum curvature solution to find inflection points and their t values. Iterate till the t values between iterations are within acceptable margins of error.

Caveat: I don’t know if this combination of 2 algorithms in an iterative manner will converge. I have not tested this. Use at your own risk.

Scaling up to 3 dimensions

Anyway, Timo found another solution himself (he didn’t say what though). He still needed to handle that cusp point. What cusp point, you ask? It’s in page 3 of that paper I mentioned above. That paper is for 2 dimensional cubic Bézier curves. The degree of the curve is independent of the degree of the dimensions. Timo wants to know how the 3 dimensional case will look like.

Now, the method of finding inflection points is to do a cross product of the first derivative and second derivative of the cubic Bézier curve equation. The Bézier curve is parametrised into

x(t) = ax * t^3 + bx * t^2 + cx * t + dx
y(t) = ay * t^3 + by * t^2 + cy * t + dy

and using the Bézier basis matrix, the coefficients are

ax = -x0 + 3*x1 – 3*x2 + x3
bx = 3*x0 – 6*x1 + 3*x2
cx = -3*x0 + 3*x1
dx = x0

ay = -y0 + 3*y1 – 3*y2 + y3
by = 3*y0 – 6*y1 + 3*y2
cy = -3*y0 + 3*y1
dy = y0

Set the cross product to 0. The inflection points are found at values of t when you solve that equation:

x’ * y” – x” * y’ = 0

where x’ and x” are the first and second derivatives of x(t). Similarly for y’ and y”. The solution is in that paper I mentioned before.

This is if the curve is in 2D. The cross product of 2D vectors is a scalar. And we set the scalar to 0 to solve for t. The cross product of 3D vectors is a vector, and so we’re solving with a zero vector.

So with
z(t) = az * t^3 + bz * t^2 + cz * t + dz
for the third dimension, we have

x’ = 3 * ax * t^2 + 2 * bx * t + cx
y’ = 3 * ay * t^2 + 2 * by * t + cy
z’ = 3 * az * t^2 + 2 * bz * t + cz

x” = 6 * ax * t + 2 * bx
y” = 6 * ay * t + 2 * by
z” = 6 * az * t + 2 * bz

The cross product is the determinant of the following
Cross product

where i, j, k are the unit vectors. I’ll leave it to you to find out the formula for the determinant of a 3 by 3 matrix.

So we’re going to solve this:
0 = (y’ * z’’ – z’ * y’’) * i – (x’ * z’’ – z’ * x’’) * j + (x’ * y’’ – y’ * x’’) * k
where 0 is the zero vector.

This implies that

y’ * z’’ – z’ * y’’ = 0
x’ * z’’ – z’ * x’’ = 0
x’ * y’’ – y’ * x’’ = 0

This time the zeroes are scalars. We now have 3 times the number of equations to solve when compared to the 2D case. This means there are potentially 6 values of t for the inflection points to check. Hopefully, there will be repeated values of t. Hopefully, the number of unique values of t is 2 or less (remember Adrian’s proof?).

If a t value is repeated, it’s probably an inflection point. What if we get 6 unique values? Is a 6-unique-value case even possible? I don’t know. You’ll have to interpret the values in the best way you can, based on some assumptions and arguments.

What do you think?

So after reading through that entire article, what do you think? Comments on the methods I described? Do you have a new method? Your thoughts on whether this problem is even solvable? That I’m a complete idiot?

Let me know in a comment. Or better, write a blog post and tell me about it. Because if it took me that long to explain the solutions, your solution is probably just as long. It’s a Bézier curve. A picture might be appropriate.