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.