CGAL users discussion list

["Sebastien Loriot (GeometryFactory)" <>]

Eggersdorfer Maximilian wrote:
> Dear All,
>  
> I have the following problem and wonder if there is a quick and easy method:
>  
> I have several spheres (from 10 up to 10000) which can overlap strongly and also have different sizes. I found the method of Liang, Edelsbrunner, Fu, Sudhakar & Subramaniam (1998), Proteins, 33, 1-17 with direct inclusion-exclusion using alpha shapes.
>  
> Do you think this is an appropriate method to quickly calculate the volume (and surface area) of the overlapping spheres. I need to recalculate it frequently in my simulation as the arrangement changes.
>  
> Thank you for your help!
> max
>  
> ______________________________________________________
> Max Eggersdorfer
> Particle Technology Laboratory, ETH Zürich
>
>  
Dear Max,

We have implemented another method that uses the decomposition of the 
volume using the underlying power diagram. Using this method, you can 
get the volume of each ball restricted to its power cell and also the 
volume of the union of balls. The implementation is robust and the 
volumes computed are accompanied with an error bound.

It can be accessed here : http://cgal.inria.fr/abs/Vorlume
The web site is currently down due to a power outage at INRIA.
The associated tech report is here : http://hal.inria.fr/inria-00409374/en.

S.