Finding the closest distance between a point a curve for multiple Points (n>1000)

Question

I am trying to compute the closest distance between a point a curve (polynom of 2rd degree) :

$$f(x)=a*x^2+b*x+c$$

$a,b,c$ are established. So if we denote that D(x) is an distance from $(x,f(x))$ to $(p,q)$ so we get:

$$ D(x)= \sqrt {(x-q)^2+(f(x)-p)^2}$$

To get the minimum of $D(x)$ we take the derivate of $D(x)'=0$ and the only way when $D(x)'$ becomes zero is when the numerator becomes $0$. So i get:

$$2(x-q)+2(f(x)-p)*f'(x)=0$$

But to solve this equation for multiple points takes much computation time I need a faster solution. Is there a approximation or algorithm to speed up the compution for a big set($n>5000$) of points?

Answer 1

I would try the following:

Your equation $$ 2(x-p)+2(f(x)-q)*f'(x)=0 $$

Is actually an equation of degree three. Write it out and you will get something like

$$a^2x^3+px^2+...$$

and so on.

Do a for loop over all points:

for p and q in points:
    solve(a^2*x^3 + q*x^2 + ..., x)

Solve is a matlab command and doing this 5000 times should not take more than a second. Tell me if it works and if you have any questions.

Answer 2

HINT

At first find the point at which parabola tangent slope (differentiate) is perpendicular to line connecting the points considered.

Answer 3

If you only want a fairly rough answer, you could approximate the function by a series of straight lines or a series of circular arcs. The point is that measuring distance to straight lines and circular arcs is a lot faster/easier than the original problem.

However ...
If you want good accuracy, then you will have to use a large number of lines or arcs, which might make the computations slower than the original one.

If you really want blazing speed, do the computations in parallel. The calculations are all completely independent of one another so the problem is a so-called "embarrassingly parallel" one.

Answer 4

An option is to solve the problem for points on a regular grid with desired density. Then telling the cell where a query point belongs is a simple matter, and this gives you a good approximation.

The approximation can be improved by interpolation, for instance bilinear. And you can also refine by Newton if necessary.

---

For a quick initialization of the grid data, you can bypass the resolution of the equation and work in reverse: starting from the equation of the parabola, you can establish the equation of equidistant curves (https://en.wikipedia.org/wiki/Parallel_curve), easy to obtain in parametric form. Then, by varying the distance and curve parameter, you can generate as many points as you like and assign the distance value to the nearby grid nodes.

To implement this approach, adjusting the point density is a little challenging, though.