CGAL users discussion list

[Mariette Yvinec <>]

It seems that what you want looks like
the  triangulation used in the crust  reconstruction algorithm of Nina Amenta and co,
and can be obtained like that
1) compute a first Delaunay triangulation of your input points
2) compute a second Delaunay triangulation with your input point
   + their  Voronoi centers (i. e.  adding the circumcenters of the first Delaunay triangulation).

In 2d the Voronoi centers are all close to the medial axis
and if your points form a good sample of your boundary,
you will get an approximation of the boundary in the second Delaunay triangulation
and the domain will be triangulate as you want...


Amir Vaxman wrote:

I would like a triangulation of a domain, with inner points, such that every
edge is adjacent to one inner point and one original point. That way, the
inner points have minimal graph distance of one edge exactly to the
boundary. That type of triangulation makes the inner points a sort of a
spine, resembling the medial axis. I don't want to use straight skeletons
because of the high running time.

Amir.

-----Original Message-----
From: Andreas Fabri [] 
Sent: Thursday, April 02, 2009 10:32 AM
To: 
Subject: Re: [cgal-discuss] Meshing a 2D domain

Hi Amir,

I guess part of the problem to answer you is what you mean with distance
and k-edges.  Also do you want something that approximates this somehow,
or do you need that if from the boundary you go to the straight skeleton
(along which trajectory by the way), you traverse exactly k edges.

Maybe you have to create k offsets with the Straight skeleton package,
and then you just make a conforming triangulation of the offset polygons.

Or you might have a look at the Meshing demo.  In the 'Tools' menu,
you find 'Make Lipschitz Delaunay Mesh'. It has a size criterion based
on the distance to the boundary.  It is only in the demo and not a
documented meshing criterion.

hope this helps,

andreas (today without moustache)


Amir Vaxman wrote:
  

Hello,

 

Anyone has a close-by answer for this?

 

Thanks,

Amir.

 

*From:* Amir Vaxman []
*Sent:* Sunday, March 29, 2009 3:18 PM
*To:* 
*Subject:* [cgal-discuss] Meshing a 2D domain

 

Hello,

 

Is there a possibility within CGAL to mesh a 2D with the restriction 
that every inner point is at most "k" (for some constant "k") edges far 
from the boundary? E.g., regular constraint triangulation is bounded by 
"0" and straight skeleton (or medial axis) triangulation is at most "1".

 

Amir.

    

-- 
Mariette Yvinec
Geometrica project team
INRIA  Sophia-Antipolis