Shortest Distance between a Point and a Numerical 2D Curve

Question

I have a 2D Curve. I have all the numerical values for the line within a certain range. I do not have an equation for this line.

At several points in this 2D space I want to calculate the shortest distance from a point, P, to this non-linear line for which I have the values.

How can I do this? Any suggestion will be very much appreciated.

Sketch attached.

Answer 1

If your line is short enough (less than $10^6$ points), you really can just do this by brute force: calculate the distance from $\vec{p}$ to each point in your discretized line, and take the minimum of these distances. This shouldn't be hard even on a basic desktop.

Since you only have a discrete collection of points, this really is as good as you can do. Anything fancier would have to assume something more about your curve.

Answer 2

With just a "point cloud", about which you know nothing, there's nothing you can do besides checking each point. But with a curve like that, you might be able to do something. For example, let's say your curve is continuous and has a parametrization $f(t)$. Then what you have is really $\{ f(t_n) \}_{n=1}^N$ for some unknown values $t_n$. If we consider $f$ is a parametrization by arclength, then one way to approximate the $t_n$ is to start at the endpoint with $t_1=0$ and then have $t_k = t_{k-1} + \| f(t_k)-f(t_{k-1}) \|$ for $k=2,\dots,N$. There are better ways of doing this, but going forward, let us just say that we have the $t_n$ from some procedure which only involves processing the curve.

Now let $x$ be your point off the curve. Then $g(t) = \| x - f(t) \|^2$ is as smooth as $f$ is. Let's assume $g$ is twice differentiable. (This cannot be checked without knowing more about where the problem came from.)

Now consider attempting to find the minimum of $g$ with Newton's method. We can't use Newton's method as it is ordinarily defined, because we can't evaluate $g$ at arbitrary $t$. We also can't write the first or second derivative of $g$ for the same reason.

But we do have discrete approximations. For the first derivative we can use the usual forward or backward difference. For the second derivative the best thing to do is based on Taylor expanding $g(t_{n+1})$ and $g(t_{n-1})$ about $t_n$. Then you can get the appropriate weights for the best approximation of $g''(t_n)$ using only $g(t_{n+1}),g(t_n),g(t_{n-1})$.

The other problem that we will encounter is that Newton's method will want to send us to points where we cannot evaluate $g$. But this is easy enough to fix (at least mathematically): just find the closest $t_n$ to the $t$ that Newton's method is giving you. The ability to do this efficiently will be an important contribution to the choice of an appropriate data structure for this problem. Given a nice enough data structure, this can be done in $\log(N)$ time using a binary search.

Another problem with this approach based on parametrization is that the up-front expense of finding the $t_n$ is actually the same amount of work as it would be to brute force one case of the problem. This approach only saves any time if you need to find the closest point on the curve to many different points, because in this case we can re-use the work that was done to find the $t_n$.

Yet another problem with almost any approach other than full brute force is that $g$ may fail to be convex. In this case, as usual for non-convex optimization, you have to worry about the possibility that your algorithm is detecting a local minimum rather than the global one.

Answer 3

I will solve this problem by using optimization and the algorithm called "Divide and conquer", I am a native French speaking, I am not so sure if that is how we called the method in English but in French is "Diviser pour mieux régner". This will work well with your problem, as your 2D Curve is a finite sample. Let say tab(N1,N2)=2D Curve N1 and N2 are the dimension of the curve. let call lhs (left hand side of tab) the head of tab and rhs (right hand side of tab) the tail of tab

BEGIN

c = False

while(c=False):

if distance(p,lhs)$>$distance(p,rhs) then:

 tab := tab[N1/2,N2/2] to tab[tail1,tail2]

else

 if distance(p,lhs)$<$distance(p,rhs) then

     tab := tab[head1,head2] to tab[N1/2,N2/2]

   else 
      sortest distance = distance(p,tab[N1/2,N2/2])
      c = True

END

head1 and head2 are the head of tab; remember to refresh these in the while loop. Sorry I just discribed this, for real implementation you need to consider lhs maybe as tab[head1,head2] and rhs as tab[tail,tail];

initialise head1=0; head2=0;tail1=N1;tail2=N2 and refresh them in the while loop after each decision. This method will work even if your 2D list is large.