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?

Do you know the order of the points on the boundary? Is the boundary simple? — David Eisenstat, Sep 27 '13 at 17:32

score 3 · Accepted Answer · answered Sep 27 '13 at 19:09

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.

Thank you for your very helpful input. I would like to add to your answer that gts_remove_hull() achieves exactly what you described as the last step of your procedure (deleting the triangles outside the boundary) — Matthias, Oct 01 '13 at 14:09

score 1 · Answer 2 · answered Dec 06 '16 at 17:12

1

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

answered Dec 06 '16 at 17:12

lhf

70,581
9
108
149

score 0 · Answer 3 · answered Sep 30 '13 at 06:54

0

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

answered Sep 30 '13 at 06:54

abenci

8,422
19
69
134

Triangulating a planar point set with known Boundary

3 Answers3

Linked