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?
For the Bezier curve - straight line case, the most accurate way to find the answer is to do the following:
Some answers from the Algorithmist blog page, which correctly finds the closest point on the given quadratic bezier curve.
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:
Algorithm for distance from Bézier curve to line
The Bézier curve is parametrised by a function
The line is parametrised by two points
Algorithm for distance from Bézier curve to Bézier curve
This time we have two Bézier curves, parametrised by
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).