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?
4 Answers
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
.
Let
SAMPLES = 10
for instanceStart with
t0 = 0
andt1 = 1
Let
dt = (t1 - t0) / SAMPLES
If
dt < 1e-10
(or any other accuracy condition you see fit), algorithm is finished and answer isF(t0)
.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)
Find which point in
L
with indexi
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.If
i == 0
, seti = 1
; ifi == SAMPLES
, seti = SAMPLES - 1
Let
t1 = t0 + (i + 1) * dt
andt0 = t0 + (i - 1) * dt
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)
.
Let
SAMPLES = 10
for instanceStart with
t0 = 0
,t1 = 1
,s0 = 0
ands1 = 1
Let
dt = (t1 - t0) / SAMPLES
Let
ds = (s1 - s0) / SAMPLES
If
dt < 1e-10
(or any other accuracy condition you see fit), algorithm is finished and answer isF(t0)
.IF this is the first run of the loop:
6.1. Compute a list of
SAMPLES + 1
points onF
(see above).6.2. Compute a list of
SAMPLES + 1
points onG
.6.3. Find which pair of points are closest to each other.
6.4. Update
t0
,t1
,s0
,s1
as seen above.ELSE: alternatively compute a list of points on
F
OR a list of points onG
, then find which point onF
is closest toG(s0)
and updatet0
andt1
, OR which point ofG
is closest toF(t0)
and updates0
ands1
.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).
-
\$\begingroup\$ 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) \$\endgroup\$– ValmondDec 12, 2011 at 21:51
Some answers from the Algorithmist blog page, which correctly finds the closest point on the given quadratic bezier curve.
Demo.
-
-
1\$\begingroup\$ I guess he wanted us to view the demo's source: algorithmist.net/DegrafaClosestToQuad/srcview/index.html \$\endgroup\$– MutohApr 6, 2015 at 4:32
For the Bezier curve - straight line case, the most accurate way to find the answer is to do the following:
- 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.)
- 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.
- 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.
- 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.