Algorithm for the reduction of a Triangulation

Question

I've computed a triangulation of a region, which boundaries are described by a polygon. But the triangulation is computed for the convex hull, bigger than the region.

Some of the triangles in the resulting set must be discarded. Dou you know about an algorithm for this operation?

Answer 1

I would combine this (triangulation of the convex hull) with another algorithm which would check if a given point is inside the polygon or not. Then, for each resulting triangle, I would check if it's median point is inside the polygon.

Answer 2

If you can use a 3rd party library, you can use CGAL and the following example will do what you want (including the triangulation).

Answer 3

You can try alpha shapes. Its delaunay triangulation without edges exceeding alpha.