How to calculate the nearest point of a line and curve? .. or curve and curve?

Question

Given the points of a line and a quadratic bezier curve, how do you calculate their nearest point?

Answer 1

I just wanna give you a few hints, in for the case Q.B.Curve // segment : to get a fast enough computation, i think you should first think about using a kind of 'bounding box' for your algorithm. Say P0 is first point of the Q. B. Curve, P2 the second point, P1 the control point, and P3P4 the segment then :

1. Compute distance from P0, P1, P2 to P3P4
2. if P0 OR P2 is nearest point --> this is the nearest point of the curve from P3P4. end :=).
3. if P1 is nearest point, and Pi (i=0 or 1) the second nearest point, the distance beetween PiPC and P3P4 is an estimate of the distance you seek that might be precise enough, depending on your needs.
4. if you need to be more acurate : compute P1', which is the point on the Q.B.curve the nearest from P1 : you find it applying the BQC formula with t=0.5. --> distance from PiP1' to P3P4 is an even more accurate estimate -but more costly-.
5. Note that if the line defined by P1P1' intersects P3P4, P1' is the closest point of QBC from P3P4.
6. if P1P1' does not intersect P3P4, then you're out of luck, you must go the hard way...

Now if (and when) you need precision :

think about using a divide and conquer algorithm on the parameter of the curve : which is nearest from P3P4 ?? P0P1' or P1'P2 ??? if it is P0P1' --> t is beetween 0 and 0.5 so compute Pm for t=0.25. Now which is nearest from P3P4?? P0Pm or PmP1' ?? if it is PmP1' --> compute Pm2 for t=0.25+0.125=0.375 then which is nearest ? PmPm2 or Pm2P1' ??? etc you will come to accurate solution in no time, like 6 iteration and your precision on t is 0.004 !! you might stop the search when distance beetween two points becomes below a given value. (and not difference beetwen two parameters, since for a little change in parameter, points might be far away) in fact the principle of this algorithm is to approximate the curve with segments more and more precisely each time.

For the curve / curve case i would first 'box' them also to avoid useless computation, so first use segment/segment computation, then (maybe) segment/curve computation, and only if needed curve/curve computation.

For curve/curve, divide and conquer works also, more difficult to explain but you might figure it out. :=)

hope you can find your good balance for speed/accuracy with this :=)

Edit : Think i found for the general case a nice solution :-) You should iterate on the (inner) bounding triangles of each B.Q.C. So we have Triangle T1, points A, B, C having 't' parameter tA, tB, tC. and Triangle T2, points D, E, F, having t parameter tD, tE, tF. Initially we have tA=0 tB=0.5 tC= 1.0 and same for T2 tD=0, tE=0.5, tF=1.0 The idea is to call a procedure recursivly that will split T1 and/or T2 into smaller rectangles until we are ok with the precision reached. The first step is to compute distance from T1 from T2, keeping track of with segments were the nearest on each triangle. First 'trick': if on T1 the segment is AC, then stop recursivity on T1, the nearest point on Curve 1 is either A or C. if on T2 the nearest segment is DF, then stop recursivity on T2, the nearest point on Curve2 is either D or F. If we stopped recursivity for both -> return distance = min (AD, AF, CD, CF). then if we have recursivity on T1, and segment AB is nearest, new T1 becomes : A'=A B= point of Curve one with tB=(tA+tC)/2 = 0.25, C=old B. same goes for T2 : apply recursivityif needed and call same algorithm on new T1 and new T2. Stop algorithm when distance found beetween T1 and T2 minus distance found beetween previous T1 and T2 is below a threshold. the function might look like ComputeDistance(curveParam1, A, C, shouldSplitCurve1, curveParam2, D, F, shouldSplitCurve2, previousDistance) where points store also their t parameters.

note that distance (curve, segment) is just a particular case of this algorithm, and that you should implement distance (triangle, triangle) and distance (segment, triangle) to have it worked. Have fun.

Answer 2

There exist a scientific paper regarding this question from INRIA: Computing the minimum distance between two Bézier curves (PDF here)

Answer 3

I once wrote a tool to do a similar task. Bezier splines are typically parametric cubic polynomials. To compute the square of the distance between a cubic segment and a line, this is just the square of the distance between two polynomial functions, itself just another polynomial function! Note that I said the square of the distance, not the square root.

Essentially, for any point on a cubic segment, one could compute the square of the distance from that point to the line. This will be a 6th order polynomial. Can we minimize that square of the distance? Yes. The minimum must occur where the derivative of that polynomial is zero. So differentiate, getting a 5th order polynomial. Use your favorite root finding tool that generates all of the roots numerically. Jenkins & Traub, whatever. Choose the correct solution from that set of roots, excluding any solutions that are complex, and only picking a solution if it lies inside the cubic segment in question. Make sure you exclude the points that correspond to local maxima of the distance.

All of this can be efficiently done, and no iterative optimizer besides a polynomial root finder need be used, thus one does not require the use of optimization tools that require starting values, finding only a solution near that starting value.

For example, in the 3-d figure I show a curve generated by a set of points in 3-d (in red), then I took another set of points that lay in a circle outside, I computed the closest point on the inner curve from each, drawing a line down to that curve. These points of minimum distance were generated by the scheme outlined above.

Answer 4

1.Simple bad method - by iteration go by point from first curve and go by point from second curve and get minimum 2.Determine math function of distance between curves and calc limit of this function like:

|Fcur1(t)-Fcur2(t)| ->0

Fs is vector.

I think we can calculate the derivative of this for determine extremums and get nearest and farest points

I think about this some time later, and post full response.

Answer 5

Formulate your problem in terms of standard analysis: You have got a quantity to minimize (distance), so you formulate an equation for this quantity and find the points where the first derivatives are zero. Parameterize with a single parameter by using the curve's parameter p, which is between 0 for the first point and 1 for the last point.

In the line case, the equation is fairly simple: Get the x/y coordinates from the spline's equation and compute the distance to the given line via vector equations (scalar product with the line's normal).

In the curve's case, the analytical solution could get pretty complicated. You might want to use a numerical minimization technique such as Nelder-Mead or, since you have a 1D continuous problem, simple bisection.

Answer 6

In the case of a Bézier curve and a line

There are three candidates for the closest point to the line:

1. The place on the Bézier curve segment that is parallel to the line (if such a place exists),
2. One end of the curve segment,
3. The other end of the curve segment.

Test all three; the shortest distance wins.

In the case of two Bézier curves

Depends if you want the exact analytical result, or if an optimised numerical result is good enough.

Analytical result

Given two Bézier curves A(t) and B(s), you can derive equations for their local orientation A'(t) and B'(s). The point pairs for which A'(t) = B'(s) are candidates, i.e. the (t, s) for which the curves are locally parallel. I haven't checked, but I assume that A'(t) - B'(s) = 0 can be solved analytically. If your curves are anything like those you show in your example, there should be either only one solution or no solution to that equation, but there could be two (or infinitely many in the case where the curves identical but translated -- in which case you can ignore this because the winner will always be one of the curve segment endpoints).

In an approach similar to the curve-line case outline above, test each of these point pairs, plus the curve segment endpoints. The shortest distance wins.

Numerical result

Let's say the points on the two Bézier curves are defined as A(t) and B(s). You want to minimize the distance d( t, s) = |A(t) - B(s)|. It's a simple two-parameter optimization problem: find the s and t that minimize d( t, s) with the constraints 0 ≤ t ≤ 1 and 0 ≤ s ≤ 1.

Since d = SQRT( ( xA - xB)² + (yA - yB)²), you can also just minimize the function f( t, s) = [d( t, s)]² to save a square root calculation.

There are numerous ready-made methods for such optimization problems. Pick and choose.

---

Note that in both cases above, anything higher-order than quadratic Bézier curves can giver you more than one local minimum, so this is something to watch out for. From the examples you give, it looks like your curves have no inflexion points, so this concern may not apply in your case.

Answer 7

The point where there normals match is their nearest point. I mean u draw a line orthogonal to the line. .if that line is orthogonal to the curve as well then the point of intersection is the nearest point