CGAL users discussion list

["Amir Vaxman" <>]

I don’t think I follow: I don’t have a sampled domain I am looking to reconstruct or approximate, my domain is, say, a simple polygon. The triangulation needs be with its original vertices, and inner vertices only, as a subdivision of the interior.

 

Amir.

 

From: Mariette Yvinec [mailto:]
Sent: Thursday, April 02, 2009 11:01 AM
To:
Subject: Re: [cgal-discuss] Meshing a 2D domain

 

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