CGAL users discussion list

[Efi Fogel <>]

Hi Wesley,

This might not be a direct answer to your question either, but seems 
very related.

We have extended the CGAL Arrangement_2 package to handle arrangements 
on any parametric surface of 2 parameters, for example spheres. The work 
is still in progress, but there are already many things that work 
properly. The documentation is not done yet either, but we believe that 
the next public release of CGAL will include this new extension.

Essentially, the (new) extended arrangement is determined by 2 traits 
classes, namely the geometry traits and the topology traits. The 
geometry traits, as in the current implementation, determines the type 
of geometric curves that induce the arrangement. The topology, among the 
other, determine the surface.

We have another package called Envelope_3, which computes envelopes of 
3d surfaces. It is based on the Arrangement_2 package, and the resulting 
envelope, sometimes called the Minimization (or Maximization) Diagram,  
is obtained as an arrangement instance. With the extended arrangement 
package we can compute envelopes of 3d surfaces on a parametric surface, 
for example, on a sphere.

It is well known that Voronoi diagrams can be computed using envelopes, 
so combine the above, and you get Voronoi diagrams on a parametric 
surfaces, for example on a sphere.

We have already implemented a few traits classes that enable 
arrangements on surfaces that are not planar. For example, we have 
developed a geometry traits class that handles arcs of great circles 
embedded on a sphere and a companion topology traits class to handle 
arrangements of these arcs.

A standard Voronoi diagram of points on a sphere consists of arcs of 
great circles. We are not far from being able to compute standard 
Voronoi diagrams on spheres.

The ability to compute non standard Voronoi diagrams on spheres or any 
other parametric surface for that matter reduces to developing 
appropriate geometry and topology traits classes. The Arrangement 
package comes with other features, such as efficient point location and 
ray shooting, which you also get for free, not to mention the 
zone-construction and sweep-line paradigm, which are inherently part of 
the package.


 wrote:
> Hi Wesley,
>
> This is not an answer to your question, but a related remark.
> We are working on extensions of 3D triangulations to the torus 
> (periodic space in the 3 dimensions) as well as other spaces.
> This should be integrated in future CGAL releases.
>
> In fact we reuse the same CGAL kernel, but we modify the design of the 
> 3D triangulation package. A first research report explaining the main 
> ideas of this new design is available from there:
> http://www-sop.inria.fr/geometrica/team/Monique.Teillaud/other-geometries/ 
>
>
> Best,
>     Monique Teillaud
>
> Wesley Smith wrote:
> > Given the kighly parametric design of CGAL, I was wondering how
> > trivial/nontrivial it would be to reparametrize the 2D cartesian
> > kernal as a toroidal space in both dimensions.  The best possible
> > answer would be that I would only have to change the equality measure
> > of Point_2, but somehow I doubt it's that simple.  My ultimate goal is
> > to implement 2D geometry constructions such as voronoi on the surface
> > of a sphere where the 2 axes are angles for lattitude and longitude.
> > Any thoughts from people who have worked in the various kernels as to
> > the difficulty and steps required?
> >
> > thanks,
> > wes


--
  ____  _        ____             _
 /_____/_) o    /__________  __  //
(____ (   (    (    (_/ (_/-(-'_(/
                        _/