Sign in to follow this  
joseMalo

Voronoi/Delaunai in 3D Questions,...

Recommended Posts

Hi all, Some theory questions on computational geometry: How one could define a Voronoi Diagram in 3D? How to derive a Delaunay triangulation(thetraedra) in 3D from a Voronoi diagram in 3D??? Do you know where to find some algorithm for constructing a Voronoi Diagram in 3d from a Delaunai triangulation in 3D? Thanks in advance!!,.. if you don't have the answer,.. any advice of where to find them? /JoseMalo

Share this post


Link to post
Share on other sites
Given a set of points S={P_1,P_2,...P_n} we can define the Voronoi region of P_i as the set of points that are closer to P_i than to any other point in S. This definition can be used in any number of dimensions.

If you draw a segment between P_i and P_j when their Voronoi regions touch each other, you get the sides of a decomposition of the convex hull of S into tetrahedrons. Those are the 3-D equivalent of the Delaunay triangulation.

Really the situation is very similar to 2-D. It will be true that the sphere that contains four vertices of one of the tetrahedrons will not contain any other points in S. It will be true that you can obtain the Delaunay graph by projecting the set onto a 4-D paraboloid, computing the convex hull and projecting back to 3-D.

Share this post


Link to post
Share on other sites
joseMalo,

In my opinion, Jonathan Richard Shewchuk of Carnegie Mellon University provides some of the definitive work in 3D tetrahedralization, including 3D Delaunay and Voronoi diagrams. You can find his myriad of papers and references here:

Jonathan Richard Shewchuk's Home Page @ CMU

As for for a definition of a 3D Voronoi Diagram, as in 2D it is the dual of the Delaunay Tetrahedralization.

Share this post


Link to post
Share on other sites
Thanks for your reply Graham.

Actually I already read his paper on "Triangle: Engineering a
2D Quality Mesh Generator and Delaunay Triangulator",... but
I was looking for something simpler and particularly short
available code.

Exactly what I look for is to find some short source code for improving mesh quality of objects defined with VRML.

Thanks for your reply!!

Regards,

/JoseMalo

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this