CGAL users discussion list

[Damian Sheehy <>]

Hi Gil,

 

You have to write your own function to classify interior/exterior triangles, and it's very straightforward.

 

1)  Start at a triangle attached to the infinite vertex and mark it as outside.

2) Visit each neighbouring triangle that does not have a classification. If you cross a constrained edge in getting to the neighbor flip the in/out classification and assign it to the neighbour.

3) Repeat until all triangles have been classified.

 

(In step 1 you could find all triangles attached to the infinite vertex and classify them as outside in one swoop)

 

This algorithm assumes your constraints defined closed boundaries that respect the Jordan curve theorem.

 

It's always tempting to use recursion to implement a seed-fill algorithm like this. If you do, it will "blow the stack"  for a large mesh; e.g. your L-shape filled with a million elements ought to do the trick.

 

Best regards,

 

Damian

 

On Fri, Jul 10, 2009 at 12:38 PM, Gil Hoffer <> wrote:

Hi,

I'm working on some academic project, and I'd like to generate a 2D triangular mesh using the CGAL meshing package (with Constrained Delaunay Triangulation).
Unfortunately, when trying to create the mesh for a non-convex area, I get triangles which are outside the area I want to mesh (see attached image as example).
Is there a way to tell the meshing procedure not to do that?

thank you!

Gil