Delaunay and Voronoi in 3D

[Brad Barber]

At 09:57 AM 11/29/01, Balint MIKLOS wrote:
>I would like to implement in Java an algorith to generate the Delaunay
>triangulation and the Voronoi cells for a set of points in 3D. I have read
>about an incremental agorithm, with the incircle test (for 2D), and the
>creation of the supertriangle at initialization. I suppose this algortihm can
>be adopted for 3D, with insphere test, and so on.

Yes, that is correct.

>  I have read as well about
>data structures used, wich can be quadtree for 2D, and octree, N-tree for 3D,
>but I don't know what these are exactly, and how are they used. All I know is
>that, these trees make a distribution of the space.
>
>Please help me, with a detaicled algorithm description, and how the data
>structures should be used.

A good, detailed introduction is Joseph O'Rourke's Computational Geometry
in C. Cambridge University Press.

>Since this computational geometry domain seems very
>interesting to me, I would like to ask, where I can start to study it. I have
>read Fukuda's FAQ about polyhedron and polytope structures and understood
>things, but if you could give me a detailed, and more explained book, or 
>paper,
>it would be great.

There are several code samples on the web for Voronoi diagrams.
You may find the Qhull 1.0 source useful (www.geom.umn.edu/locate/qhull).

I hope your project goes well.

                                                 --Brad

>I'm student at Technical Univerisity in Cluj-Napoca (2nd year), and couldn't
>find anything in our library. I couldn't get help from any professor at our
>university.
>
>Thank you in advance for your help!
>Balint Miklos
>
>
>______________________________________________________________________
>Do you want a free e-mail for life ? Get it at http://www.email.ro/
>
>
>-------------
>The compgeom mailing lists: see
>http://netlib.bell-labs.com/netlib/compgeom/readme.html
>or send mail to compgeom-request at research.bell-labs.com with the line:
>send readme
>Now archived at http://www.uiuc.edu/~sariel/CG/compgeom/maillist.html.


-------------
The compgeom mailing lists: see
http://netlib.bell-labs.com/netlib/compgeom/readme.html
or send mail to compgeom-request at research.bell-labs.com with the line:
send readme
Now archived at http://www.uiuc.edu/~sariel/CG/compgeom/maillist.html.