Re: Algorithm to return point to surface of concave volume

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.

------------------------------------------------------------------------------
The Planet: dedicated and managed hosting, cloud storage, colocation
Stay online with enterprise data centers and the best network in the business
Choose flexible plans and management services without long-term contracts
Personal 24x7 support from experience hosting pros just a phone call away.
http://p.sf.net/sfu/theplanet-com

_______________________________________________
GDAlgorithms-list mailing list
[email protected]
https://lists.sourceforge.net/lists/listinfo/gdalgorithms-list
Archives:
http://sourceforge.net/mailarchive/forum.php?forum_name=gdalgorithms-list

-----BEGIN PGP SIGNATURE-----
Version: GnuPG v1.4.10 (MingW32)
Comment: Using GnuPG with Mozilla - http://enigmail.mozdev.org/

iEYEARECAAYFAktrY5QACgkQMjUkP+sBox4kUwCfaYl+S6q4hU1XZmFzbD6stwp6
4r0An060T690IDciuGupqpTDtOEJs8dt
=RMdH
-----END PGP SIGNATURE-----