Accessible surface area of spheres
in [General Programming]
|
Prev: Draft paper submission deadline is extended: SETP-10, Orlando, USA
Next: Journal of Computer Science 2010
From: Vish on 15 Feb 2010 13:19 Hi All, I am writing code to calculate the accessible surface area of a union of spheres. Accessible surface area is the part of the sphere which does not intersect with any other sphere. I have a file which contains the center coordinates and the radius for each sphere. The way I am doing it is as follows: 1. map the sphere centers into a hash table. The max diameter of a sphere = 4 units. So the way I have hashed them is basically taking the coordinates and mapping them onto a grid. The grid consists of 4*4*4 squares. 2. consider one sphere at a time. generate random points (uniformly distributed) on the surface of that sphere. 3. check the surrounding 26 squares from the grid to see if any of the spheres (in those 26 squares) contain the points on the current sphere. This way we get to know the number of points which are exclusively on the current sphere. Note: I also check if there are other spheres in the current square. So in total, I am testing spheres in 27 squares. 4. Then we can calculate the surface area of the current sphere as follows: [2*pi*radius* (# of points exclusively on this sphere) ] / (total points generated) The problem I am facing is in step 3. Can someone help me to figure out a way to check as less spheres as possible? For step 3, I am having to consider one point at a time, and then get the spheres from the 27 squares, and do a linear scan. Need some way to speed this up. Thanks, Vish
From: Daniel Pitts on 16 Feb 2010 19:32 X-Posted to comp.programming and comp.graphics.algorithms. FU to c.g.a. Vish, I think you're question may get better attention on CGA. On 2/15/2010 10:19 AM, Vish wrote: > Hi All, > > I am writing code to calculate the accessible surface area of a union > of spheres. Accessible surface area is the part of the sphere which > does not intersect with any other sphere. I have a file which contains > the center coordinates and the radius for each sphere. The way I am > doing it is as follows: > > 1. map the sphere centers into a hash table. The max diameter of a > sphere = 4 units. So the way I have hashed them is basically taking > the coordinates and mapping them onto a grid. The grid consists of > 4*4*4 squares. > > 2. consider one sphere at a time. generate random points (uniformly > distributed) on the surface of that sphere. > > 3. check the surrounding 26 squares from the grid to see if any of the > spheres (in those 26 squares) contain the points on the current > sphere. This way we get to know the number of points which are > exclusively on the current sphere. Note: I also check if there are > other spheres in the current square. So in total, I am testing spheres > in 27 squares. > > 4. Then we can calculate the surface area of the current sphere as > follows: > [2*pi*radius* (# of points exclusively on this sphere) ] / (total > points generated) > > The problem I am facing is in step 3. Can someone help me to figure > out a way to check as less spheres as possible? For step 3, I am > having to consider one point at a time, and then get the spheres from > the 27 squares, and do a linear scan. Need some way to speed this up. > > Thanks, > Vish -- Daniel Pitts' Tech Blog: <http://virtualinfinity.net/wordpress/>
From: Gene on 20 Feb 2010 11:21
On Feb 15, 1:19 pm, Vish <vahu...(a)gmail.com> wrote: > Hi All, > > I am writing code to calculate the accessible surface area of a union > of spheres. Accessible surface area is the part of the sphere which > does not intersect with any other sphere. I have a file which contains > the center coordinates and the radius for each sphere. The way I am > doing it is as follows: > > 1. map the sphere centers into a hash table. The max diameter of a > sphere = 4 units. So the way I have hashed them is basically taking > the coordinates and mapping them onto a grid. The grid consists of > 4*4*4 squares. > > 2. consider one sphere at a time. generate random points (uniformly > distributed) on the surface of that sphere. > > 3. check the surrounding 26 squares from the grid to see if any of the > spheres (in those 26 squares) contain the points on the current > sphere. This way we get to know the number of points which are > exclusively on the current sphere. Note: I also check if there are > other spheres in the current square. So in total, I am testing spheres > in 27 squares. > > 4. Then we can calculate the surface area of the current sphere as > follows: > [2*pi*radius* (# of points exclusively on this sphere) ] / (total > points generated) > > The problem I am facing is in step 3. Can someone help me to figure > out a way to check as less spheres as possible? For step 3, I am > having to consider one point at a time, and then get the spheres from > the 27 squares, and do a linear scan. Need some way to speed this up. > I'm sure this problem has been studied, but off hand I'd try making the hash grid finer in resolution. Consider an octree. Then store in each "square" (I think you mean cube) two lists. One list has the spheres completely containing the cube. The other has all partially containing. In order to test a point P on Sphere S, use Let Lc = hash(P).completelyContaining Let Lp = hash(P).partiallyContaining if Lc has at least one element other than S, return not_accessible Test all elements in Lp other than S. Return not_accessible if you find one containing P. return accessible |