cca@pur-phy (Charles C. Allen) (02/01/88)
The following is not really a graphics problem, but I'm hoping to get some pointers on where to look for discussions of this sort of thing. Some concentric not-quite-regular polyhedra (2-d polygons extruded in the third dimension) have a bunch of space points on the planes. The space points could be stored using integers, using a grid about 10^6 x 10^6 x 10^4. The goal is to find lines formed by the space points. Are there techniques for dealing with things like this using only integer math? Actually, that would be ideal, but algorithms using real math would be appreciated also. I'm looking for books that discuss various ways of representing planes and lines (and their intersections) in 3-d, with regard to efficiency, overflows, etc. I'm working on a PhD in physics, so math background isn't a problem. The original problem comes from reconstructing tracks of charged particles in a cylindrical drift chamber. Charlie Allen cca@newton.physics.purdue.edu
varol@cwi.nl (Varol Akman) (02/01/88)
In article <982@pur-phy> cca@pur-phy (Charles C. Allen) writes: > [material deleted] >Some concentric not-quite-regular polyhedra (2-d polygons extruded in >the third dimension) have a bunch of space points on the planes. The >space points could be stored using integers, using a grid about 10^6 x >10^6 x 10^4. The goal is to find lines formed by the space points. > [material deleted] >I'm working on a PhD in physics, so math background isn't a problem. >The original problem comes from reconstructing tracks of charged >particles in a cylindrical drift chamber. > It seems to me that this is a computational geometry problem. There are currently two excellent texts on this subject. Preparata&Shamos, Computational Geometry, Springer-Verlag. Edelsbrunner, Combinatorial Geometry, Springer-Verlag. The titles are approximate -- don't have the books handy now. If you describe your problem in detail (I'm sorry but I couldn't really understand it) some people reading this newsgroup (possibly including myself) might be able to help. --V. Akman, CWI, Amsterdam