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.