Triangulating a planar point set with known Boundary

Question

I have a planar point set P. I already know what points p in P belong to the boundary B(p). Said boundary may be convex or non convex. Now, I would like to find a triangulation of P with boundary B(p). My questions:

• Is there an Algorithm that achieves this directly? A close candidate would be the Constrained Delaunay Triangulation (CDT). However, I don't think CDT applies here: I could feed all the edges in B(p) as a constraint, such that all the edges would be contained in the triangulation. However, this does not necessarily entail that this will be the boundary of the triangulation. Correct me if I'm wrong here.

• If you now of such an Algorithm, can you point me to a (lightweight) C library that provides an implementation?

• Alternatively: I could of course just triangulate P using the standard Delaunay triangulation from GTS. I would then need to prune all the faces with a vertex outside of B(p). Is this possible with GTS?

Answer 1

I could feed all the edges in B(p) as a constraint, such that all the edges would be contained in the triangulation. However, this does not necessarily entail that this will be the boundary of the triangulation.

You're right that the constrained Delaunay triangulation may fill in the concavities of the boundary. Every triangle, however, is either completely inside or completely outside of the boundary, so it's easy enough to delete the ones outside by traversing the dual of the planar straight-line graph starting from the infinite face, treating the boundary edges as impassable. Jonathan Shewchuk's library Triangle, for example, does this. The license may not be to your liking, but if you already have another library to compute constrained Delaunay triangulations, we're not talking about a lot of additional code.

Answer 2

poly2tri finds a CDT of a planar region given its boundary. It is easy to build and use.

Answer 3

You need first to do Ear Clipping using the boundary points, then transfer the result to Delaunay triangulation and add internal points.