CGAL users discussion list

[Ben Haller <>]

On Jul 21, 2010, at 11:41 AM, Sebastien Loriot (GeometryFactory) wrote:

> Ben Haller wrote:
> 
>>  Hi!  I'm currently using CGAL's Delaunay_d to do d-dimensional 
>> triangulations, with some success.  I realize that CGAL does not provide a 
>> d-dimensional Voronoi package, but I'm hoping it is possible to extract 
>> just enough information from Delaunay_d to be able to do a computation I'd 
>> like to do.  Specifically, if vertices v1 and v2 are connected in the 
>> Delaunay triangulation, they have a (d-1)-dimensional Voronoi facet 
>> between them, and I would like to be able to find the centroid of that 
>> facet.  If I've got all this stuff straight in my head, the vertices of 
>> the facet are the centers of the hyperspheres bounding the simplices that 
>> contain both v1 and v2.  I can get the set of simplices that contain both 
>> v1 and v2 from Delaunay_d.  There seems to be no API available to get the 
>> bounding hypersphere of a simplex, unfortunately; I get the impression 
>> that the Delaunay_d object has that information, but it does not expose it 
>> in the API.  If I could get the hypersphere centers,
>> then the centroid of a set of n-dimensional points is computed easily 
>> enough.  In a perfect world, I'd really like to get the centroids of 
>> *clipped* Voronoi facets, such that facets of infinite extent are clipped 
>> to the unit hypercube before the centroid is computed, but I haven't the 
>> slightest idea how I'd go about that.  That's really what I'd like, 
>> though, so that the infinite-extent facets don't blow up my algorithm; the 
>> centroid of the clipped facet is actually exactly what I want, for my 
>> application.
>>  Anyhow, my grasp of both d-dimensional geometry and the CGAL APIs is not 
>> really up to solving this problem, but I'm hoping somebody else on the 
>> list has already tackled it, or can point me in the right direction.  
>> Thanks!
>> 
>> Ben Haller
>> McGill University
> 
> Have a look here
> 
> http://www.cgal.org/Manual/latest/doc_html/cgal_manual/Kernel_d_ref/Class_Sphere_d.html#Function_Sphere_d6Kernel9_operator+6const_Vector_d6Kernel9__v9_;
> 
> The constructor should do what you want.

  Yes, that looks perfect.  That leaves the clipping problem, for the facets 
of finite extent.  If I've got the set of points that define the vertices of 
the Voronoi facet, how would I correctly clip that n-dimensional polygon to 
the unit hypercube?  I suppose I'd first have to really make them into a 
polygon, and then clip that?  The problem is just one of knowing which order 
to read the set of points in; if I know the correct order of the points to 
follow the edge of the facet around, then I have a polygon, not just a point 
cloud, and I think I know how to clip that polygon to the unit hypercube (if, 
indeed, CGAL does not already offer a function to do it).  I guess getting 
the convex hull of the points could give me the correct "reading order" for 
the points to make the polygon, but it seems like overkill; there must be a 
better way (?).

  I am also realizing that the facets of infinite extent, at the edges of the 
diagram, fall between the cracks of my proposed algorithm above.  I'm not 
sure exactly how they work, but I think they are infinite in extent because 
there are too few simplex-bounding-hypersphere-centers to fully define the 
hyperplane in d-dimensional space that the facet occupies.  Or something like 
that.  :->  I'm not sure what to do about that; somehow again I need to 
construct a clipped polygon for the facet's intersection with the unit 
hypercube, but how to do that when the vertices of the polygon are not even 
fully defined?

  This is feeling beyond my capabilities, if not (possibly) as a programmer, 
then certainly as a geometer :->.  Has anybody built a Voronoi_d package on 
top of the Delaunay_d package?  Back when my problem was 2D, I was using the 
deldir package in R, and it was doing all of this (including the clipping to 
the unit square) beautifully.  I'm just hoping to get equivalent 
functionality in d-dimensional space.  If no such package exists, may I cast 
my vote for a Voronoi_d package to be added to CGAL in the future?

  Thanks for the quick responses Sebastien!

Ben Haller
McGill University