Skip to Content.
Sympa Menu

cgal-discuss - [cgal-discuss] Delaunay, convex hull, Voronoi, kernels

Subject: CGAL users discussion list

List archive

[cgal-discuss] Delaunay, convex hull, Voronoi, kernels


Chronological Thread 
  • From: <>
  • To: <>
  • Subject: [cgal-discuss] Delaunay, convex hull, Voronoi, kernels
  • Date: Wed, 19 Nov 2008 18:33:35 +0000
  • Importance: Normal

Hi,
 
I have the following problem:
 
From a set of points on a sphere, I need to get the convex hull (which automatically yields a Delaunay triangulation in this degenerate case).
 
For this convex hull, I need to calculate the Voronoi diagram (on the surface of the sphere).
 
Now, I have been able to do both these things, but I used CGAL::convex_hull_3(...) and CGAL::assign(polyhedron, ch_object). CGAL::convex_hull_3(...) however takes about 270ms for 100 points, which is far, far too slow for what I need it. Furthermore, it is not dynamic (insertions/deletions). The points on the sphere will change over time and so the hull would have to be recomputed each time a single point changes.
 
I have also used CGAL::Delaunay_triangulation_3 (although I am better off using Triangulation_hierarchy_3 because it is faster for larger data sets?), which is very speedy (20ms for initial construction of 256 points and les than 1ms for deletion). My problem however is that my algorithm for creating the Voronoi diagram expects a CGAL::Polyhedron with no interior edges.
 
So my question is this then: is there a way to either compute the convex hull in a much faster way than CGAL::convex_hull_3(...) in CGAL (qhull seems to take only a few 2ms for 256 points) or: is there a way to distinguish between interior edges and egdes that are on the hull with the output of CGAL::Delaunay_triangulation_3.
 
My Voronoi algorithm works as follows:
- for each vertex (each point on the convex hull):
- find the neighbouring vertices
- compute the circumcenter between 3 vertices in either clockwise or counter clockwise order
- and these circumcenters, in order, to a list
- the list now contains the vertices of the voronoi cell
 
It may not be the best algorithm (many circumcenters will be computed twice), but it produces correct results for what I need it and seems to be fast enough. The problem of course, is that I do not know a way to determine the neighbouring vertices of a vertex when I use the Delaunay triangulation: there are edges running through the volume, connecting to "false" neighbouring vertices. I should have a way to consider only vertices that are connected by edges that lie on the convex hull of the volume.
 
Also, what is the fastest kernel available? Is it CGAL::Exact_predicates_inexact_constructions_kernel?
 
Thank you.


De nieuwe Hotmail maakt je leven nog makkelijker Wees er als eerste bij.



Archive powered by MHonArc 2.6.16.

Top of Page