[SciPy-User] SciPy for Computational Geometry

David Baddeley david_baddeley@yahoo.com...
Tue Nov 1 16:04:27 CDT 2011

How about using OpenGL to render the problem, giving each sphere a different colour. You can then grab the rendered image (or potentially images from different camera angles) and count the number of discrete colours you have. It's probably not the most elegant of solutions, and would only be approximate (due to the pixelation), but python has good OpenGL bindings and it ought to be fast to compute. 

It would probably also be pretty easy to code something up from scratch which did this, along these lines:

- generate an 2D array which is going to contain the index of the nearest sphere for any given angle (theta, phi) (initialised to zero)
- create a similar array which holds the distance to the nearest sphere in for each of the pixels above (analagous to a zBuffer in normal 3D rendering) and initialise this to a very large number
- iterate over your spheres and draw a circle in your index and z buffer arrays where you change the index and z value if (and only if) the new z value is going to be smaller than the one currently in the z buffer (mapping the sphere to a circle in theta, phi space should be pretty simple).

Again this is only going to be approximate (due to the pixelation).


From: Lorenzo Isella <lorenzo.isella@gmail.com>
To: scipy-user@scipy.org
Sent: Tuesday, 1 November 2011 10:14 AM
Subject: [SciPy-User] SciPy for Computational Geometry

Dear All,
This is admittedly a bit off topic, but I wonder if anybody on the list 
is familiar with this problem (which should belong to computational 
geometry) and is able to point me to an implementation (possibly relying 
on scipy).
Imagine that you are sitting at the origin (0,0,0) of a 3D coordinate 
system and that you are looking at a set of (non-overlapping) spheres 
(all the spheres are identical and with radius R=1).
You ask yourself how many spheres you can see overall.
The result is in general a (positive) real number as one sphere may 
partially eclipse another sphere for an observer in the origin (e.g. if 
one sphere is located at (0,0,5) and the other (0,0.3,10)).
Does anybody know an algorithm to calculate this quantity efficiently?
I have in mind (for now at least) configurations of less that 100 
spheres, so hopefully this should not be too demanding.
I had a look at


but I am not 100% sure that this is the way to go.
Any suggestion is appreciated.
Many thanks

SciPy-User mailing list
-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://mail.scipy.org/pipermail/scipy-user/attachments/20111101/d242bffc/attachment.html 

More information about the SciPy-User mailing list