distance2curve

Find the closest point on a (n-dimensional) curve to any given point or set of points

Description

I've seen many people ask for a way to find the closest point on a curve from some given point in space. If the curve is a piecewise linear one, this is not too difficult, since this reduces to finding the closest point on a line segment, and then testing each line segment. (With care, you need not test EVERY line segment.)

For a cubic spline however, this becomes more difficult, but still doable in a mathematical sense without an explicit optimization. Not too much more than roots is necessary.

Distance2curve allows you to specify a set of general points in an n-dimensional space as a connected space curve. A spline (or pchip) is then fit in terms of arc length along the curve, and the closest point identified.

• Required Products: MATLAB
• MATLAB release: MATLAB 7.12 (2011a)

[Christophe Lauwerys]

As always, great submission, thanks.

Could one easily extend this algorithm to finding the closest point on a surface from given a point in space? Or from another given curve, surface, ... ?

[John D'Errico]

Is it easy? I suppose the definition of easy depends on the person doing the writing.

I have written a tool that finds the closest point on a general manifold in 2 or 3 dimensions, or for low dimensional manifolds in higher dimensions. So if one wanted to find the closest point on a triangulated surface in 3-d, this would be no problem. It is even reasonably efficient. That tool could also solve for the closest point on a triangulated 2-manifold in a 4 or higher dimensional space. For higher dimensions than tessellated 2 manifolds, this is still eminently doable, but I had to stop somewhere. This tool is part of my simplicialcomplex toolbox, something that never seems to be ready to release to the general public.

However, that code is also limited to piecewise linear manifolds, since I needed to use roots to solve for the cubic case in distance2curve. Of course, roots is not available for more than one variable, so it would get a bit more nasty in higher dimensions.

The other question is how to find the minimum distance between two general curves, or even from a curve to a line. I am planning to write a tool for the minimal distance from a curve to a straight line. The minimum distance between two general space curves (1-manifolds) is somewhat more difficult, because it becomes essentially a nonlinear optimization in two variables.