MATLAB and Simulink resources for Arduino, LEGO, and Raspberry Pi

### Discover what MATLAB® can do for your career.

Opportunities for recent engineering grads.

# Thread Subject: Fast distance computation between polygonal objects in 3d

 Subject: Fast distance computation between polygonal objects in 3d From: Johannes Korsawe Date: 11 Dec, 2007 09:05:06 Message: 1 of 1 Hi community, i am working on the following problem: I have a line in 3d (say 101 points = 100 line segments, represented by list, size(list=[nl 3]. The length of each line segment is nearly the same.) and a meshed polygonal body in 3d (i.e. a list of points p, size(p)=[np 3] and an index set of triangles t, size(t)=[nt 3]). Here the sizes/lengths of triangles resp. edges may differ a lot. I need to compute the minimal distance from the line to the mesh surface. I took the following three parts of the problems into my considerations: I) Minimal distance from the points list to the points p. I have a very fast c Routine which i can call to do this. II) Minimal distance from the points list to the interior of the triangles t. I also have a fast MATLAB solution for this task. III) Minimal distance from the edges of the triangles in t to the edges (eq. line segments) of the points list. Now, the third task is the hardest (in terms of runtime) for me. If the number of edges and the number of line segments is not too much, it works pretty well. But the runtime grows a lot if the number of edges (from triangle list t) grows. This is due to the fact that i need to calculate the distance from each line segment to each edge in the polygon. I was not able to think of reductions in the amount of needed comparisons. My question is twofold: I) Does anyone know of a fast c implementation of this problem (i would nearly do this by myself, but i am not so sure if the result will be much faster than MATLAB)? II) I might have overseen possibilities to reduce the problem size. I would be happy if i could reduce the problem to compare only a part of all edges of the polygon to the line segments. But i can always think of "special cases", where any reduction would result in "throwing away" the real minimum. I have read in literature about a preprocessing of the polygonal structure, which results in a hierarchical tree structuring into geometrical subsets, which may allow for a "log n"-search algorithm. But i am too lazy to really implement this in MATLAB (and i am too honest to conceal this). Has anyone done this or something like this before in MATLAB or knows something about simplifications or anything? Thanking for your help, Johannes Korsawe

## Tags for this Thread

### What are tags?

A tag is like a keyword or category label associated with each thread. Tags make it easier for you to find threads of interest.

Anyone can tag a thread. Tags are public and visible to everyone.

Contact us