piyush_soni Posts: 4, Reputation: 1 New Member #1 Nov 19, 2008, 05:04 PM
Distance of a point from bezier
How to find closest distance of a point P(Px, Py) from a bezier curve given by four control points A, B, C and D?
 harum Posts: 339, Reputation: 27 Full Member #2 Nov 19, 2008, 07:54 PM
Four points are necessary to define parametric cubic Bézier curve: S(t), where 0<= t <=1. Find the equation for parametric parametric cubic Bézier curve. The distance between your given point P and the curve as a function of parameter t: D(t)=sqrt( (Px-Sx(t))^2 + (Py-Sy(t))^2 ). Find the value of parameter t, Tmin, which minimizes this function and here you go: Xmin = Sx(Tmin), etc.
 piyush_soni Posts: 4, Reputation: 1 New Member #3 Nov 19, 2008, 11:53 PM
Originally Posted by harum
Four points are necessary to define parametric cubic Bézier curve: S(t), where 0<= t <=1. Find the equation for parametric parametric cubic Bézier curve. The distance between your given point P and the curve as a function of parameter t: D(t)=sqrt( (Px-Sx(t))^2 + (Py-Sy(t))^2 ). Find the value of parameter t, Tmin, which minimizes this function and here you go: Xmin = Sx(Tmin), etc.
I wouldn't have come to this forum if it was that simple. I could figure out that much myself. The problem is: to find the minimum t, I have to equate the derivate of this distance to zero, which gives rise to solving a fifth degree polynomial.
 harum Posts: 339, Reputation: 27 Full Member #4 Nov 20, 2008, 09:29 AM
Yes, 5th degree polynomial. Could you find zeros numerically? I suspect this is your only option, because analytical solutions do not exist for equations of degrees higher than 4th. Or do they?
 piyush_soni Posts: 4, Reputation: 1 New Member #5 Nov 20, 2008, 12:09 PM
Yes, I was trying to figure out a robust as well as efficient method to do that numerically, as you are right the analytical solution doesn't exist and the problem is : the only numerical way known to me is Newton-Raphson, but the problem is it is not guaranteed to converge. So I am unable to implement it in a computer program. Do you know any other method which is guaranteed to converge?
 harum Posts: 339, Reputation: 27 Full Member #6 Nov 20, 2008, 03:45 PM

Yes, this is not unusual for Newton-like methods. Have you tried Durand–Kerner method?
 LeonardG Posts: 2, Reputation: 2 New Member #7 Feb 7, 2011, 07:46 PM
Recipe for point to Bezier minimum or maximum distance calculation.

We want to find the minimum distance from a point to a cubic Bezier segment and find the "t" value for the corresponding point on the Bezier.

If the segment has a singularity (forms a cusp at a point where the derivative is undefined) then it should first be divided into two segments at the singularity and the problem solved separately for each piece.

Inputs to the routine are the point in question and the Bezier segment description with two, three, or four control points. Things the overall routine should return include whether a valid point was obtained, the curve "t" value at the closest location, the corresponding point on the curve, and the Euclidian distance from the measured point.

One could work out the algebra in detail, but this is subject to clerical errors. A high quality tool for symbolic manipulation would help. In my experience, at least one of the tools available free on the internet is unreliable in one term.

In order to get the task done I took a more direct programmatic approach. Some of the tools needed:

1.) Convert a Bezier definition into polynomial form:
The formula for the cubic Bezier (defined by four points) with uniform 1.0 weights on the interval 0 to 1:
B(t) = P0*(1-t)^3, + P1* (*1-t)^2)*t, + P2*(1-t)*t^2 + P3*t^3
Write a routine to cast this into the form a[0] + a[1]*t + a[2]*t^2 + a[3]*t^3
The preferred format will include the degree of the polynomial (three in the above examples) and an array of a terms. For general graphics use we usually not require degrees higher than 9 (for computing cubic bezier intersections). Here the maximum degree will be 5.

2.) Write a routine to differentiate a polynomial of the above form.

4.) And a polynomial multiplier.

5.) A degree reduction routine (if the highest order term is zero the degree may be reduced).

6.) A normalization routine, in which all terms are divided by the highest degree non-zero term, required by the root solver

7.) A polynomial root solver. I have found Durand-Kerner to be satisfactory. Items 5 and 6 above are needed to preprocess the input for DK.

87.) A real root extractor to process the DK result and extract only the real roots, provided that real root detection (imaginary part zero) is done with a "fuzzy" (near zero) comparison.

We are only interested in the real roots in the range zero to one, and depending upon the overall path routine may wish to ignore roots close to zero or close to one, and accept roots "close enough" to one of the range limits, even though slightly out of range, converting these to zero or one.

Steps of the algorithm:

i.) Given Bezier Bz(t), derive Ax(t) and Ay(t), the polynomial forms for the x and y axis

ii.) From the polynomials subtract the appropriate ordinate of the point in question, i.e.:
Ax.a[0] -= P.x;
Ay.a[0] -= P.y;

iii.) Obtain the derivatives Dx(t) and Dy(t)

I've.) Calculate the polynomial products Ax(t)*Dx(t) and Ay(t)*Dy(t)

v.) Sum the polynomial products. This is in fact one-half of the value of the algebraic derivative but since we seek a zero it does not matter.

vi.) Normalize the results

vii.) Obtain the complex roots

viii.) Select the real roots in the range 0 to 1

ix.) Compute the point on the curve corresponding to each reasonable t value and select the t value generating the smallest distance - if there is only one check that it is not a maximum.

If only a single t in that range is found there remains one more check to perform, since this may in fact be a maximum distance (e.g, the point being measured is within an arch or loop); determine the distance to either of the end points, and if less than the distance to the single point found then reject that solution as being a maximum.

Following this recipe, nothing is especially difficult and the individual routines are easily tested, unlike the alternative algebraic methods in which it is easy to introduce errors of transcription

This method will also work for the quadratic case with the solving of a third degree polynomial, or the quadratic could be promoted and solved as a cubic. Using the above method in the case of a Bezier line leads too much more complexity than would using homogeneous coordinates or simpler methods using separate translation and rotation, but provides a good starting point for coding and higher degree versions may be tested by degree promotion.

Further testing may be performed by obtaining a point on the curve for known valid t value and feeding it into the routines, which should result in a zero distance from the curve, with appropriate nonzero results for offsets from this point.

APPLICATION TO BEZIER INTERSECTIONS

When intersecting curves that are representational segments of the same underlying geometry (e.g, intersecting a circle with a rotation of that circle with the same center), there may be no intersection where it would be expected in the underlying geometry approximated by those bezier segments, perhaps occurring elsewhere on the segment. In particular, an end point of one segment may not meet the curve of the other segment at the end point of one or the other. By calculating the distance to the curve from the end point we can detect if it is close enough to generate an intersection. If so, a division may be made at the closest point on the curve and that point and its adjacent control points (one for each of the two adjacent segment created by the division), then to be adjusted to move the division point into coincidence with the original end point.
 jcaron2 Posts: 986, Reputation: 204 Senior Member #8 Feb 7, 2011, 08:50 PM

Nice answer. It seems like a relatively straightforward algorithm, as you said. I'm just curious, is this type of calculation something that's typically done "on the fly" in real time or would you be using such an algorithm to compute an a priori closed-form solution for a given Bezier, as a function of the parameter t?
 LeonardG Posts: 2, Reputation: 2 New Member #9 Feb 8, 2011, 09:05 AM
Comment on jcaron2's post
This is part of a general shape intersection library that I am developing, intended for the Boolean composition of closed paths that are comprised of Bezier segments, currently using Core Graphics (PDF) paths under Quartz in Apple's OSX and iOS. The functions on the paths include Union, Difference, Intersection and Exclusive Or, and these in turn require Bezier segment intersections. A drawing system will in turn call these routines as directed by a designer. Performance is sufficient for real-time interaction, but the primary need is to allow a drawing system operator to compose illustrations through a series of actions on basic shapes. I will probably include the minimum and maximum distances from a point to a path as part of the library. The primary purpose of the code is to resolve certain end-point to path segment near intersections as noted. - Leonard

 Question Tools Search this Question Search this Question: Advanced Search

## Check out some similar questions!

I understand how to find the equation of a tangent and a normal line at a given point by using the first derivative, and I know how to find the distance from x,y to 2,1 using the distance formula, but I don't see how to put it together. The book says: Use the distance formula ^2 = + ^2 and...

Distance from a point and line [ 2 Answers ]

Answer how you got that "root2" on the eqn.explain detail

Point-to-point diagram [ 3 Answers ]

I want to know about the use of point-to-point diagrams in electrical/electronics engineering.

Point to point diagram [ 2 Answers ]