Computing distance from a point to a triangulation in 3D with Matlab

2
votes

I have a 3D point cloud that I've transformed into a Delaunay triangulation using Matlab's function DelaunayTri. Now I have a test point in 3D and want to compute, in Matlab, the smallest distance between this point and the triangulation.

So far, I've thought of using the nearestNeighbor(...) member function of the DelaunayTri class in Matlab to find the point in the triangulation closest to my test point and then computing the distance between them. That is something but it is not what I really want.

The closest point on the triangulation to my test point is, in general, not a vertex of the triangulation but somewhere on the face of a triangle. How can I find this point?

Thank you!!!

2
matlabgeometrytriangulationdelaunay
So basically what you're asking is how to find the closest point to the surface of a tetrahedron given the coordinates of an internal point and the coordinates of the 4 vertices? – Dan
@Viruss mca: please use code formatting only for code. – S.L. Barth
@Dan: Yes, I think that's right. I have to admit that I'm not sure how to find the 4 vertices in the structure that Matlab returns. However my test point is not within the tetrahedron but outside it. – Patrick Bangert
@Patrick Looks like they seriously revamped their delaunay methods since last I used them. Check out the pointLocation method. I think you will also find FaceNormal pretty useful because the shortest distance from your point to each face will be normal to that face – Dan
@Dan: Thank you for that. With pointLocation I can find the tetrahedron if I know an internal point. Is it true that the point returned by nearestNeighbor is a point on the correct tetrahedron? Supposing I have the right tetrahedron, how do I get the triangles to use FaceNormal ? – Patrick Bangert

2 Answers

0
votes

I've written codes for these things, but they are not on the File Exchange. I can be convinced to give them out by direct mail though.

It is relatively easy to find the distance to a convex hull, but not trivial. A delaunay tessellation is bounded by the convex hull anyway. So you can convert that tessellation into the convex hull easily enough, or just use the convex hull. Note that a convex hull is often a terribly poor approximation for many purposes, especially if you are using this for color mapping, which is perhaps the most common thing I see this used for. In that case, an alpha shape is a far better choice. Alpha shapes also will have a triangulated boundary surface, though in general it will not be convex.

So, to find the nearest point on a convex triangulation:

  1. Convert to the convex boundary surface, i.e., the convex hull. This reduces to finding those triangles which are not shared between pairs of tetrahedra. Internal facets will always appear exactly twice in the list of all facets. This trick also works for non-convex tessellations of course, so for alpha shapes.

  2. Compute a bounding circumcircle for each triangular surface facet. This allows you to know when to stop checking facets.

  3. Get the distances to each point on the surface. Sort each facet by the distance to the nearest point in that facet. Start by looking at the nearest facet in that list.

  4. Compute the distance to the apparently nearest facet found in step 3. A simple solution is found by least distance programming (LDP), which can be converted to a constrained linear least squares. Lawson & Hanson have an algorithm for this.

Repeat step 4 until the current best distance found is less than the distance, comparing it to any of the circumcircles from step 2. This loop will be quite short really, at least for a convex hull. For a more general non-convex hull from an alpha shape, it may take more time.

You can also reduce the search space a bit by excluding the facets from your search that point AWAY from the point in question. Use those facet normals for this test.

0
votes

I wrote the tool point2trimesh for this problem. It's kind of a "brute force" solution which works also for non-convex surfaces.