Closest distance from a point to point on bezier curve?
Author
I have a feeling that there is no non-iterative solution to this but i'm gonna ask it anyway :).
Lets say i have a 3D bezier curve and a point in space, lets call it point A. How do i find the closest point that lies on the bezier curve to my point A?
ive also wrestled with this problem, and i think you guessed right.
i believe that after writing out the equation i found myself facing a 6-th order polynomal to solve: not going to happen. good iterative methods are your friend.
i believe that after writing out the equation i found myself facing a 6-th order polynomal to solve: not going to happen. good iterative methods are your friend.
oh, 6th order polynomial, ouch, that's tricky!...
but if you're wanting the explanation for the analytic solution anyway, here it comes:
i don't know exactly how a bezier curve is reprensented, but i guess it has also an analityc representation depending on a parameter like:
f(t): t -> x(t), y(t), z(t)
so, for each t, you get the coordinates. Then, you can compute the distance D from the point P to each point of the curve given by f(t).
Lastly, derive this expression: dD/dt
Since f(t) should always be the same expression with different coefficients, the same applies to it's derative.
The minimum distance then simply happens when dD/dt = 0, so you can compute the t out of it, which gives you the nearest point.
If the equation has no solution (in the domain of t!), it means that an extreme point of the curve is the solution.
but if you're wanting the explanation for the analytic solution anyway, here it comes:
i don't know exactly how a bezier curve is reprensented, but i guess it has also an analityc representation depending on a parameter like:
f(t): t -> x(t), y(t), z(t)
so, for each t, you get the coordinates. Then, you can compute the distance D from the point P to each point of the curve given by f(t).
Lastly, derive this expression: dD/dt
Since f(t) should always be the same expression with different coefficients, the same applies to it's derative.
The minimum distance then simply happens when dD/dt = 0, so you can compute the t out of it, which gives you the nearest point.
If the equation has no solution (in the domain of t!), it means that an extreme point of the curve is the solution.
well i just did it like this:
distance between points = sqrt(dx^2+dy^2)
or d^2 = dx^2+dy^2.
where dx is the distance from the point in question to an arbitrary point on your curve, so dx = point.x - curve.x, meaning this term will have the same degree as your curve.
assuming were talking about a third degree polynomal, it doesnt take a genius to spot that dx^2+dy^2 will yield a polynomal of double the degree of the original curve.
so there is an anallitical solution for second order curves, although that would involve solving a fourth order polynomal, which is a pain, and that an analitical solution isnt even possible for the more common third order polynomals, since poly's of the third degree have no analitical solution per definition.
distance between points = sqrt(dx^2+dy^2)
or d^2 = dx^2+dy^2.
where dx is the distance from the point in question to an arbitrary point on your curve, so dx = point.x - curve.x, meaning this term will have the same degree as your curve.
assuming were talking about a third degree polynomal, it doesnt take a genius to spot that dx^2+dy^2 will yield a polynomal of double the degree of the original curve.
so there is an anallitical solution for second order curves, although that would involve solving a fourth order polynomal, which is a pain, and that an analitical solution isnt even possible for the more common third order polynomals, since poly's of the third degree have no analitical solution per definition.
Quote:Original post by Eelco
since poly's of the third degree have no analitical solution per definition.
this is simply wrong, look again in calculus. It can be solved but it is complicated.
I believe that only once you get to 5th order polys are they unsolveable analytically. 4th order are just really really wrong.
But you can always try to apprximate a high order poly with a lower order in the section youre observing.
But you can always try to apprximate a high order poly with a lower order in the section youre observing.
oh sorry i obviously meant to say sixth order :P. should be clear from the context though, third order squared == 6th order, hehe.
to rephrase:
so there is an analitical solution for second order curves, although that would involve solving a fourth order polynomal, which is a pain, and that an analitical solution isnt even possible for the more common third order SPLINES, since poly's of the SIXTH degree have no analitical solution per definition.
:)
to rephrase:
so there is an analitical solution for second order curves, although that would involve solving a fourth order polynomal, which is a pain, and that an analitical solution isnt even possible for the more common third order SPLINES, since poly's of the SIXTH degree have no analitical solution per definition.
:)
For a bézier spline with four points A, B, C, D it would be:
f(t) = (t-1)^3*A + 3*t*(t-1)^2*B + 3*t^2*(t-1)*C + t^3*D;
f(t) = (t-1)^3*A + 3*t*(t-1)^2*B + 3*t^2*(t-1)*C + t^3*D;
Author
Ok thanks for the replies, i think i'll give it a miss since i think i'll end up with a headache if i attempt it.
healeyx76, these where the curves i was talking about:
http://astronomy.swin.edu.au/~pbourke/curves/bezier/
specifically bezier curves with 4 control points (3rd order polynomial).
healeyx76, these where the curves i was talking about:
http://astronomy.swin.edu.au/~pbourke/curves/bezier/
specifically bezier curves with 4 control points (3rd order polynomial).
This topic is closed to new replies.
Advertisement
Popular Topics
Advertisement
