Re: [Algorithms] Algorithm to return point to surface of concave volume

[Yaser Z. <y...@ya...>]

On 2/3/2010 14:24, Andreas Brinck wrote:
> Hi,
> 
> I have a point inside a concave volume, does anyone know of an algorithm
> to find the shortest vector from the point to the surface of the volume?
> The volume in this case is defined as the union of a number of
> overlapping capsules (lines with radius).
> 

I'm not an expert here, but couldn't you just find the shortest distance
to each of the capsules in isolation and then wouldn't your answer be
the minimum of these distances?

Also, I'm sure there are ways to speed this up if you have to repeat
this query many times under changing circumstances (e.g. organizing the
capsules as the leaves of a complete tree structure and letting the
parent of each group of leaves contain the shortest distance of the
children to the point. Also, nodes can have "dirty" flags which you set
whenever the capsules below them in the tree change. This way, you can
recompute the shortest distance in the dirty branches of the tree.)

However, I'm sure there is a simpler and faster solution out there.

-Yaser Zhian

-- 
May the Source be with you.