[SciPy-User] SciPy for Computational Geometry

[David Baddeley]

Actually I've just thought of how to find a more exact solution  which avoids pixelation (using shapely [http://pypi.python.org/pypi/Shapely] which is a decent package for 2D computational geometry in python):

- map all your spheres to circles on theta, phi with an associated distance
- sort by distance (closest first)
- take the closest circle as a mask
- iterate over the other circles doing the following:
- check if they are contained in the mask (in which case they won't appear in the output and can be discarded)
- if not contained in mask, increment the number of visible spheres and update the mask to be the union of the previous mask and the current circle


________________________________
From: David Baddeley <david_baddeley at yahoo.com.au>
To: SciPy Users List <scipy-user at scipy.org>
Sent: Wednesday, 2 November 2011 10:04 AM
Subject: Re: [SciPy-User] SciPy for Computational Geometry


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).

cheers,
David


________________________________
From: Lorenzo Isella <lorenzo.isella at gmail.com>
To: scipy-user at 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

http://www.qhull.org/

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

Lorenzo
_______________________________________________
SciPy-User mailing list
SciPy-User at scipy.org
http://mail.scipy.org/mailman/listinfo/scipy-user



_______________________________________________
SciPy-User mailing list
SciPy-User at scipy.org
http://mail.scipy.org/mailman/listinfo/scipy-user
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://mail.scipy.org/pipermail/scipy-user/attachments/20111101/f664d9ee/attachment.html>