Blogs

Stuart’s MATLAB Videos

Watch and Learn

This is machine translation

Translated by Microsoft
Mouseover text to see original. Click the button below to return to the Original version of the page.

Set up: Finding closest point on a surface 4

Posted by Doug Hull,

This video sets up the plan for how to find the closest point on a surface to a given point. This is a numerical approximation that avoids the inevitable complexities of solving the problem exactly with computational geometry techniques.

Category: 
Format: Video,
Level: Basic,
Topic: Practical example

You can follow any comments to this entry through the RSS 2.0 feed. You can skip to the end and leave a comment. Pinging is currently not allowed.

4 CommentsOldest to Newest

dhull replied on : 1 of 4
@Matt, Thanks for the kind words and the link. The next installment will show the actual code used. I think for this problem, the implementation was much easier than figuring out what to implement.
Matt Whitaker replied on : 2 of 4
Hi Doug, This calculation is a very common one in medical physics for radiation therapy quality assurance. We have an expected dose distribution in [X,Y,Dose] space from a treatment planning system and a measured dose distribution in the same space. There is a 'gamma' metric that is derived from calculating the minimum distance from all the points(in practice pixels) on one surface to the other surface. The distance is normalized to dose difference and distance to agreement tolerances but the basic calculation is as you describe. There have been a number of numerical solutions in the fields similar to what you describe in your video. For an elegant computational geometry solution see: Geometric interpretation of the gamma dose distribution comparison technique: Interpolation-free calculation Med. Phys. Volume 35, Issue 3, pp. 879-887 (March 2008) This has a really nice recursive algorithm that solves minimum distance to a 3 point 'simplex' whether that point falls in the surface , on the edges, or at the vertices. Anyways thanks for the video on a subject that is relevant to my daily work. Matt W.
Joao replied on : 3 of 4
I believe an elegant and precise solution for this problem that is easily done in MATLAB would be to use a Linear Programming model to minimize the distance from the external point to the affine space of all the vertices (v_{1} ... v_{j}) of the 3D shape (only works for a convex space). Using the linearized 1-norm, a model would be: min{a} Z = sum_{i} (z_{i}) s.t.: sum (a_{j}) = 1 ; a_{j} >=0 z_{i} >= [sum_{i,j}(a_{j}*v_{j,i}) - P_{i}] z_{i} >= -[sum_{i,j}(a_{j}*v_{j,i}) - P_{i}] where 1<= j <= no of vertices; 1<=i<=3 It has the disadvantage (advantage?) that it will find the closest point to the affine space of the surface. Thus if the point is inside the space enclosed by the surface, it will be the solution. Non-convex spaces would have to be broken into convex subspaces before applying the algorithm.
Daniel Frisch replied on : 4 of 4
I uploaded a function that finds the nearest point on non-convex hulls without approximations: https://www.mathworks.com/matlabcentral/fileexchange/52882-point2trimesh------distance%C2%A0between-point-and-triangulated-surface