f



Shortest distance from a point to a sampled surface?

I have a 2-D matrix of sampled values on a regular, uniform grid of x and y. 
The data can be analogied to being vertical height at every point.

I then have an arbitrary point (a,b,c) and I want to know the shortest 
distance from that point to the sampled surface.  The x and y coordinates of 
the point (a,b,c) will coincide with those on the sampled grid (so it's not 
completely arbitrary).

I know I can find the distance to every point on the surface and find a 
minimum, but that doesn't acount for when the shortest distance is to a face 
or edge of the surface rather than a point.  And if possible I'd like to 
find the shortest distance to a smoothly interpolated (cubic spline or 
similar) of the surface.

Are there any fast algorithms for doing this?  I'm working in MATLAB mostly 
if that helps.

It needs to be as fast as possible because in practice I have an entire 
surface of points (a,b,c) and i need to find the shortest disatance for each 
one.  i.e. I have two surfaces and at a whole bunch of points x,y I need to 
find the shortest distance between the two planes.

The planes will be about 200x300 in size mostly.

Any help muchly appreciated.

-- 
Ian Cowley
Bishop's Stortford/Cambridge, UK

www.iancowley.co.uk/contact 


0
me3 (244)
7/26/2005 11:23:54 AM
comp.soft-sys.matlab 210402 articles. 11 followers. lunamoonmoon (258) is leader. Post Follow

8 Replies
454 Views

Similar Articles

[PageSpeed] 31

In article <dc56dq$gtl$1@gemini.csx.cam.ac.uk>,
"Ian Cowley" <me3@privacy.net> writes:
|> 
|> I have a 2-D matrix of sampled values on a regular, uniform grid of x and y. 
|> The data can be analogied to being vertical height at every point.
|> 
|> I then have an arbitrary point (a,b,c) and I want to know the shortest 
|> distance from that point to the sampled surface.  The x and y coordinates of 
|> the point (a,b,c) will coincide with those on the sampled grid (so it's not 
|> completely arbitrary).
|> 
|> I know I can find the distance to every point on the surface and find a 
|> minimum, but that doesn't acount for when the shortest distance is to a face 
|> or edge of the surface rather than a point.  And if possible I'd like to 
|> find the shortest distance to a smoothly interpolated (cubic spline or 
|> similar) of the surface.
|> 
|> Are there any fast algorithms for doing this?  I'm working in MATLAB mostly 
|> if that helps.

No.  You need to specify the problem more precisely before it is
answerable.  There are two aspects:

1) You need to specify the interpolation, because the properties
will affect the search very considerably.  There are several
variants of cubic splines, and most of those will produce a
surface that can extend beyond the extrema of your points.

2) If you have a single point per surface, you will clearly not
do better than a fairly simple search, as the cost of setting up
a data structure will be more than it's worth.  If you have many
of them, the problem is different.

For a single point, start at the closest point on the grid plane
to the point and work outwards, maintaining the closest distance
so far.  When you have reached that distance away on the plane,
you can stop, as no subsequent point can be closer.

Even then, you may be able to optimise that if you can make
assumptions about the properties of the surface.


Regards,
Nick Maclaren.
0
nmm1 (190)
7/26/2005 11:44:52 AM
In message dc57nk$ju3$1@gemini.csx.cam.ac.uk, Nick Maclaren burbled:
> In article <dc56dq$gtl$1@gemini.csx.cam.ac.uk>,
> "Ian Cowley" <me3@privacy.net> writes:
>>>
>>> I have a 2-D matrix of sampled values on a regular, uniform grid of
>>> x and y. The data can be analogied to being vertical height at
>>> every point.
>>>
>>> I then have an arbitrary point (a,b,c) and I want to know the
>>> shortest distance from that point to the sampled surface.  The x
>>> and y coordinates of the point (a,b,c) will coincide with those on
>>> the sampled grid (so it's not completely arbitrary).
>
> No.  You need to specify the problem more precisely before it is
> answerable.  There are two aspects:
>
> 1) You need to specify the interpolation, because the properties
> will affect the search very considerably.  There are several
> variants of cubic splines, and most of those will produce a
> surface that can extend beyond the extrema of your points.

OK, we'll ignore interpolation for now, I should get good enough answers 
without.
Assuming then that I can take each square (in the x,y plane) and divide it 
into two triangles, I'm looking for an algorithm that'll give me the 
shortest distance from an arbitrary point in to a triangle in 3D.  I've 
found algorithms for distance from a point to an infinite planes, but I 
can't find out the more specific point-to-triangle.

So, can anyone point me in the direction of a point-to-triangle distance 
algorithm?

-- 
Ian Cowley
Bishop's Stortford/Cambridge, UK

www.iancowley.co.uk/contact 


0
me3 (244)
7/26/2005 12:46:21 PM
In article <dc5b8d$rm5$1@gemini.csx.cam.ac.uk>,
"Ian Cowley" <me3@privacy.net> writes:
|> 
|> OK, we'll ignore interpolation for now, I should get good enough answers 
|> without.
|> Assuming then that I can take each square (in the x,y plane) and divide it 
|> into two triangles, I'm looking for an algorithm that'll give me the 
|> shortest distance from an arbitrary point in to a triangle in 3D.  I've 
|> found algorithms for distance from a point to an infinite planes, but I 
|> can't find out the more specific point-to-triangle.

That's linear interpolation :-)

|> So, can anyone point me in the direction of a point-to-triangle distance 
|> algorithm?

You work out the nearest point on the plane, check if it is within
the triangle, and use it if so.  If not, you find where the point
is relative to the sides and do the similar task for the nearest
side.  If the nearest point on that side is within the side, use
it if so.  If not, use the distance to the nearest point.

It isn't hard, can be optimised tolerably well by ensuring that
your calculations deliver information in a form that can be used
for both the distance and the selection, but is messy and it is
a hell of a long time since I did it.  Sorry I can't help more.


Regards,
Nick Maclaren.
0
nmm1 (190)
7/26/2005 12:54:06 PM
Ian Cowley wrote:
> In message dc57nk$ju3$1@gemini.csx.cam.ac.uk, Nick Maclaren burbled:
> > In article <dc56dq$gtl$1@gemini.csx.cam.ac.uk>,
> > "Ian Cowley" <me3@privacy.net> writes:
> >>>
> >>> I have a 2-D matrix of sampled values on a regular, uniform grid of
> >>> x and y. The data can be analogied to being vertical height at
> >>> every point.
> >>>
> >>> I then have an arbitrary point (a,b,c) and I want to know the
> >>> shortest distance from that point to the sampled surface.  The x
> >>> and y coordinates of the point (a,b,c) will coincide with those on
> >>> the sampled grid (so it's not completely arbitrary).
> >
> > No.  You need to specify the problem more precisely before it is
> > answerable.  There are two aspects:
> >
> > 1) You need to specify the interpolation, because the properties
> > will affect the search very considerably.  There are several
> > variants of cubic splines, and most of those will produce a
> > surface that can extend beyond the extrema of your points.
>
> OK, we'll ignore interpolation for now, I should get good enough answers
> without.
> Assuming then that I can take each square (in the x,y plane) and divide it
> into two triangles, I'm looking for an algorithm that'll give me the
> shortest distance from an arbitrary point in to a triangle in 3D.  I've
> found algorithms for distance from a point to an infinite planes, but I
> can't find out the more specific point-to-triangle.
>
> So, can anyone point me in the direction of a point-to-triangle distance
> algorithm?

A (non-degenerate) triangle determines a plane, so you can find the
distance from your point to that plane. Then find the projection of
your point onto that plane. If that projection is in the triangle, you
are done. Otherwse, find the shortest distance to the perimeter of the
triangle by any method you like (I suggest parametrizing the sides, and
finding the minimum of each edge. This is a simple problem)

0
qurqirishd (17)
7/26/2005 1:14:30 PM
In article <dc5b8d$rm5$1@gemini.csx.cam.ac.uk>,
 "Ian Cowley" <me3@privacy.net> wrote:

> In message dc57nk$ju3$1@gemini.csx.cam.ac.uk, Nick Maclaren burbled:
> > In article <dc56dq$gtl$1@gemini.csx.cam.ac.uk>,
> > "Ian Cowley" <me3@privacy.net> writes:
> >>>
> >>> I have a 2-D matrix of sampled values on a regular, uniform grid of
> >>> x and y. The data can be analogied to being vertical height at
> >>> every point.
> >>>
> >>> I then have an arbitrary point (a,b,c) and I want to know the
> >>> shortest distance from that point to the sampled surface.  The x
> >>> and y coordinates of the point (a,b,c) will coincide with those on
> >>> the sampled grid (so it's not completely arbitrary).
> >
> > No.  You need to specify the problem more precisely before it is
> > answerable.  There are two aspects:
> >
> > 1) You need to specify the interpolation, because the properties
> > will affect the search very considerably.  There are several
> > variants of cubic splines, and most of those will produce a
> > surface that can extend beyond the extrema of your points.
> 
> OK, we'll ignore interpolation for now, I should get good enough answers 
> without.
> Assuming then that I can take each square (in the x,y plane) and divide it 
> into two triangles, I'm looking for an algorithm that'll give me the 
> shortest distance from an arbitrary point in to a triangle in 3D.  I've 
> found algorithms for distance from a point to an infinite planes, but I 
> can't find out the more specific point-to-triangle.
> 
> So, can anyone point me in the direction of a point-to-triangle distance 
> algorithm?

I can tell you what I used.

Given a point x0, and a triangulation in a 3d space:

0. Compute the "in-plane" circumspheres for each triangle.
You would only do this once for many points, so its not
that bad, and its fast anyway. A circumsphere is the sphere
that contains each point on its circumference. In this case,
it will have the additional feature that the centrer of the
sphere must lie in the plane of the triangle. It can be
done by solving a linear system of equations.

I. Find the closest vertex on the triangulation to x0.
Compute that distance.

2. Find the distances from x0 to each circumcenter. Use
these distances with the radii of the corresponding spheres
to compare to the closest point we found so far. This
allows you to eliminate most of the triangles. (Note that
all points on a triangle must lie inside its circumsphere.)

3. For those few triangles which remain, use algorithm
LDP to find the closest point to x0.

What is LDP? Its from a book by Lawson & Hanson, "Solving
Least Squares Problems". LDP finds the closest point to
the origin of the set of points which satisfies a set of
convex inequalities. (LDP stands for Least Distance
Programming.) You can describe a triangle as such a set.
One inequality is defined by the normal to the plane of
the triangle, the rest by the 3 sides of the triangle.

Lawson and Hanson also show how to convert the LDP problem
into a non-negative least squares problem, as is solved
in matlab by lsqnonneg (nnls for older versions of matlab.)

HTH,
John D'Errico


-- 
The best material model of a cat is another, or
preferably the same, cat.
A. Rosenblueth, Philosophy of Science, 1945
0
woodchips (7943)
7/26/2005 3:42:53 PM
In article <dc56dq$gtl$1@gemini.csx.cam.ac.uk>,
Ian Cowley <me3@privacy.net> wrote:

>I have a 2-D matrix of sampled values on a regular, uniform grid of x and y. 
>The data can be analogied to being vertical height at every point.
>
>I then have an arbitrary point (a,b,c) and I want to know the shortest 
>distance from that point to the sampled surface. 

Just to add to the things you want to think about: if your height data read:

   x y z=f(x,y)
   ------------
   0 0   0
   0 1   1
   1 0   1
   1 1   0

then you can put a polyhedral surface to these data which looks like a
valley between  (0,0) and (1,1), with two hills on the sides, or which
looks like a mountain ridge between (0,1) and (1,0), with two valleys
off to the sides. 

Lesson learned: that the sampling data do not specify a unique surface
in the same way that a 1-D array of sampled values specifies a unique
piecewise-linear curve. This can, obviously, affect decisions about
where on "the surface" is the nearest point to any given  (x,y,z) in R^3.

dave
0
rusin (29)
7/26/2005 8:20:41 PM
In article <dc5bpe$sre$1@gemini.csx.cam.ac.uk>, nmm1@cus.cam.ac.uk 
says...
> |> So, can anyone point me in the direction of a point-to-triangle distance 
> |> algorithm?
> 
> You work out the nearest point on the plane, check if it is within
> the triangle, and use it if so.  If not, you find where the point
> is relative to the sides and do the similar task for the nearest
> side.  If the nearest point on that side is within the side, use
> it if so.  If not, use the distance to the nearest point.

That'll work, but it's not very efficient.  The most efficient
method considers the Voronoi feature regions defined by the
triangle: 3 vertex regions, 3 edge regions, and 1 triangle
interior.  You classify the query point to the first 6
regions, and if it is found residing in one of them, you
project the query point onto the feature (the vertex or
edge).  The projection is the closest point on the triangle
to the query point (which trivially gives the distance).
If the query point is not in one of the first 6 regions,
the projection onto the triangle plane is the nearest point.

If Q is the query point and ABC is the triangle, you can test
if Q is in the Voronoi region of, say, A by testing if
Dot(Q - A, B - A) < 0 and Dot(Q - A, C - A) < 0.  The
other regions are tested in a similarly simple fashion.
You can find all the tests in my SIGGRAPH'04 slides on
GJK as available here:

http://realtimecollisiondetection.net/pubs/

The math for the edge Voronoi regions can be simplified
using the Lagrange identity so that the 6 dot products
for testing the vertex Voronoi regions are being reused.

It doesn't get faster than that.

-- 
Christer Ericson
http://realtimecollisiondetection.net/
0
7/27/2005 5:56:18 AM
In article <MPG.1d50c1dce7942e10989822@news.verizon.net>,
Christer Ericson  <christer_ericson@NOTplayTHISstationBIT.sony.com> wrote:
>In article <dc5bpe$sre$1@gemini.csx.cam.ac.uk>, nmm1@cus.cam.ac.uk 
>says...
>> |> So, can anyone point me in the direction of a point-to-triangle distance 
>> |> algorithm?
>> 
>> You work out the nearest point on the plane, check if it is within
>> the triangle, and use it if so.  If not, you find where the point
>> is relative to the sides and do the similar task for the nearest
>> side.  If the nearest point on that side is within the side, use
>> it if so.  If not, use the distance to the nearest point.
>
>That'll work, but it's not very efficient.  The most efficient
>method considers the Voronoi feature regions defined by the
>triangle: 3 vertex regions, 3 edge regions, and 1 triangle
>interior.  You classify the query point to the first 6
>regions, and if it is found residing in one of them, you
>project the query point onto the feature (the vertex or
>edge).  The projection is the closest point on the triangle
>to the query point (which trivially gives the distance).
>If the query point is not in one of the first 6 regions,
>the projection onto the triangle plane is the nearest point.

I was simplifying.  If you optimise the operation I suggested, you
end up with doing approximately the same calculation in a slightly
different order.  My experience is that all ways of doing this are
a pain, because a lot of the performance comes from not recalculating
things - and adding data structures to manage that costs too much.

>The math for the edge Voronoi regions can be simplified
>using the Lagrange identity so that the 6 dot products
>for testing the vertex Voronoi regions are being reused.
>
>It doesn't get faster than that.

Only by a small constant factor, which depends on the detail of the
coding and not the mathematics.


Regards,
Nick Maclaren.
0
nmm1 (190)
7/27/2005 9:22:18 AM
Reply: