# How do you calculate the nearest point on 2 curves?

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?

-
I believe this question is a good start. – Sam Hocevar Dec 12 '11 at 16:13
+1 interesting question! – iamcreasy Dec 12 '11 at 22:23

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.

-

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).

-
 ps. 2 curves, don't even think about it (you might get anything (at least as may as..) according to the number of control points) – Valmond Dec 12 '11 at 21:51

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

Demo.

-