Subject: CGAL users discussion list
List archive
Re: [cgal-discuss] Using Delaunay_d to find some d-dimensional Voronoi information?
Chronological Thread
- From: Ben Haller <>
- To:
- Subject: Re: [cgal-discuss] Using Delaunay_d to find some d-dimensional Voronoi information?
- Date: Wed, 21 Jul 2010 12:13:27 +0200
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
- [cgal-discuss] Using Delaunay_d to find some d-dimensional Voronoi information?, Ben Haller, 07/21/2010
- Re: [cgal-discuss] Using Delaunay_d to find some d-dimensional Voronoi information?, Sebastien Loriot (GeometryFactory), 07/21/2010
- Re: [cgal-discuss] Using Delaunay_d to find some d-dimensional Voronoi information?, Ben Haller, 07/21/2010
- Re: [cgal-discuss] Using Delaunay_d to find some d-dimensional Voronoi information?, Sebastien Loriot (GeometryFactory), 07/21/2010
Archive powered by MHonArc 2.6.16.