How do you calculate the nearest point on 2 curves?

Question

Given the points of a line and a quadratic bezier curve, how do you calculate their nearest point? .... Similarly, given the points of 2 curves, how do you get the nearest point?

Answer 1

Here is my try. The following algorithms are far from perfect, but they are simple and I believe you should start with this, check whether they work in your situation, and switch to something faster and/or more accurate later.

The idea is the following:

• Sample the Bézier curve, find the nearest point on that sample
• Sample a neighbourhood around the found point, find a new nearest point
• Continue until the point no longer changes much

Algorithm for distance from Bézier curve to line

The Bézier curve is parametrised by a function F(t) using a set of control points and a varying parameter t. The number of generating points is unimportant.

The line is parametrised by two points A and B.

1. Let SAMPLES = 10 for instance

2. Start with t0 = 0 and t1 = 1

3. Let dt = (t1 - t0) / SAMPLES

4. If dt < 1e-10 (or any other accuracy condition you see fit), algorithm is finished and answer is F(t0).

5. Compute a list of SAMPLES + 1 points on the Bézier curve:

   • L[0] = F(t0)
   • L[1] = F(t0 + dt)
   • L[2] = F(t0 + 2 * dt)
   • …
   • L[SAMPLES] = F(t0 + SAMPLES * dt)

6. Find which point in L with index i is closest to the line. Use any point/line distance method you know, for instance the square distance ||AB^L[i]A||² / ||AB||² where ^ denotes cross product and ||…|| is the distance.

7. If i == 0, set i = 1; if i == SAMPLES, set i = SAMPLES - 1

8. Let t1 = t0 + (i + 1) * dt and t0 = t0 + (i - 1) * dt

9. Go back to step 3.

Algorithm for distance from Bézier curve to Bézier curve

This time we have two Bézier curves, parametrised by F(t) and G(t).

1. Let SAMPLES = 10 for instance

2. Start with t0 = 0, t1 = 1, s0 = 0 and s1 = 1

3. Let dt = (t1 - t0) / SAMPLES

4. Let ds = (s1 - s0) / SAMPLES

5. If dt < 1e-10 (or any other accuracy condition you see fit), algorithm is finished and answer is F(t0).

6. IF this is the first run of the loop:

   6.1. Compute a list of SAMPLES + 1 points on F (see above).

   6.2. Compute a list of SAMPLES + 1 points on G.

   6.3. Find which pair of points are closest to each other.

   6.4. Update t0, t1, s0, s1 as seen above.

7. ELSE: alternatively compute a list of points on F OR a list of points on G, then find which point on F is closest to G(s0) and update t0 and t1, OR which point of G is closest to F(t0) and update s0 and s1.

8. Go back to step 3.

Issues

By design, these algorithms will always converge to a local minimum. However, there is no guarantee that they will converge to the best solution. In particular, the Bézier curve algorithm isn't very good at all, and in the case of two curves being close to each other at many places you may unfortunately miss the solution by a long shot.

But as I said, before you start thinking about more robust solutions, you should first experiment with those simple ones.

Answer 2

1) Translate everything to one axis,so instead of needing to calculate the length of one point to, the 'line', the 'line' is, say, the Y-Axis.

Then, uh, given a bezier curve I'd say it's up to the number of control points.

If there are three, (beginning, 'control' and end) I'd do some sort of scan (say each a couple of percent and then refine between the closest ones (with say a 'binary' approach).

More points I'd try out the couple that were closest to the (translated Y-Axis).

I am sure a math-guy can give you the exact solution (in mathematics) but if you want to find the/a solution in a video game you might be better off with a slightly ok solution as the real solution might contain several answers (I'm not even talking about processing power).

Answer 3

Some answers from the Algorithmist blog page, which correctly finds the closest point on the given quadratic bezier curve.

Demo.

Answer 4

For the Bezier curve - straight line case, the most accurate way to find the answer is to do the following:

1. Transform the problem so that the straight line is always horizontal at Y=0. This is done by multiplying all the control points by an appropriate affine matrix. (I assume you are familiar with representing affine transformations of the plane with 3x3 matrices with 3 fixed entries.)
2. Inspect the Y coordinates of the control points. If they don't all have the same sign, there can be an intersection with the line. Compute the roots of the Y part of the Bezier curve. You can use any root finding method for polynomials, there are plenty of them in the literature. For example, google "convex hull marching" - this is a reasonably good method for the polynomials used in Bezier curves. Every root you find is a time value of an intersection with the line, where the distance is zero - your work is done.
3. If all Y coords have the same sign, compute the derivative of the Y part of the Bezier curve. You can ignore the X coordinates of points, since they make no difference - the target line is horizontal. Find the roots of that derivative. These are the time values at which the curve is locally closest to the line.
4. Explicitly evaluate the Bezier curve for all roots you have found in the previous step and report the root which gives the smallest distance from the line. You also need to check the endpoints - they might give a smaller distance than any root.