CGAL users discussion list

[<>]

Hi,
 
Thank you for your reply.
 
I could do what you describe, however once I know the vertices of the voronoi cells (that is, the center of the circle/sphere of the facet/cell), and which vertex of the triangulation they belong to, I also need to know in what order they appear.
 
In other words, I don't know how to order an unordered set of voronoi cell vertices so that when they are connected the edges between them do not cross. I don't know of a simple and above all fast way to get an ordering like this (in 3d). That is why I used the halfedge data structure from the polyhedron: given a vertex, it allows you to access the neighbouring vertices, in order. This means extra work computing repeatedly computing centers that have alreay been computed, but it was fast enough. I need this ordering to compute the surface area: I divide the polygon into triangles, and then I compute the spherical surface area of these triangles.
 
I am not sure it is possible to determine the correct order using just the triangulation data structure?
 
Or perhaps you know of a way to get a correct order out of an unordered set of voronoi cell vertices?
 
Writing this out, I'm asking myself whether a voronoi cell is always convex? Because if that's not always the case, my current method (of dividing the cell into triangles) could produce the wrong result.
 

> Date: Thu, 20 Nov 2008 09:17:23 +0100
> From:
> To:
> Subject: Re: [cgal-discuss] Delaunay, convex hull, Voronoi, kernels
>
> Why not the following.
>
> compute the 3D Voronoi of your points.
> (you can also add the center of the sphere, it will probably make the
> computation
> faster and do not change the triangulation of the sphere provided that the
> center is inside the convex hull)
>
>
> for each edge from the infinite vertex
> (I think there will be an iterator in next release
> a work around in your case is to iterate on all edges asking if they are
> finite)
>
> for each cell incident to that edge (there is a circulator ) (this
> loop describe a Voronoi cell on the sphere)
> compute the Voronoi vertex on the sphere
> end for
> end for
>
> --
> You are currently subscribed to cgal-discuss.
> To unsubscribe or access the archives, go to
> https://lists-sop.inria.fr/wws/info/cgal-discuss

---

Alle fun stuff van Messenger nu verzameld op één coole site! Windows Live Messenger