Discover MakerZone

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

Learn more

Discover what MATLAB® can do for your career.

Opportunities for recent engineering grads.

Apply Today

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:04:55

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