Algorithm for completing a partial triangulation (Constrained Triangulation)

5
votes

Given a set of points in a plane and an incomplete triangulation of the convex hull of the points (only some edges are given), I'm looking for an algorithm to complete the triangulation (the initial given edges should remain fixed). You can assume that it's possible to complete the partial triangulation but it'd be great if you could also suggest an algorithm for checking that too.

UPDATE" You're given a convex hull of a set of points R^2, which is basically a polygon with some points inside it. We want to triangulate the set of points which is a straightforward matter on itself, but you're also given some edges that any triangulation that you come up with should use those edges."

2
algorithmgeometrycomputational-geometrytriangulation
How can you perform triangulation with just 1 edge? Isn't that an infinite space? – Lasse V. Karlsen
The wording of the "update" sounds a bit like a homework assignment, is it? – Damon
No it's not, I need the algorithm to initialize a grid for further computation. – user972432
It's almost like this – user972432
What is difference between your question and constrained triangulation (link you posted)? – Ante

2 Answers

4
votes

Perhaps this is a naive answer, but can't you just use a constrained delaunay triangulation? Add the known edges as constraints.

CGAL has a nice implementation. The tool triangle has similar features and is easier to get started with, but has (perhaps) a little less flexibility.

0
votes

I found out that the book "Computational Geometry: An Introduction" has a detailed treatment of the subject though it doesn't give a ready to implement pseudo-code.

The easiest algorithm is a greedy one which enumerates all the possible edges and then add them one by one avoiding intersection with previously added ages. There is a long discussion in the book about how to reduce the running time to O(n^2 log n).

Then there is a O(n log n) algorithm which first regularizes the convex hull with the given edges and then individually triangulates each monotone polygon.