Triangulating a partially triangulated mesh (2D)

Referring to the above exhibits, this is the scenario I am working with:

• starting with a planar graph (in my case, a 2D mesh) with a given triangulation, based on a certain criterion, the graph nodes are labeled as RED and BLACK. (A)
• a subgraph containing all the RED nodes (with edges between only the directly connected neighbours) is formed (note: although this figure shows a tree forming, it may well happen that the subgraph contain loops) (B)

Problem: I need to quickly build a triangulation around the subgraph (e.g. as shown in figure C), but under the constraint that I have to keep the already present edges in the final result.

Question: Is there a fast way of achieving this given a partially triangulated mesh? Ideally, the complexity should be in the O(n) class.

Some side-remarks:

• it would be nice for the triangulation algorithm to take into account a certain vertex priority when adding edges (e.g. it should always try to build a "1-ring" structure around the most important nodes first - I can implement iteratively such a routine, but it's O(n^2) ).
• it would also be nice to reflect somehow the "hop distance" when adding edges: add edges first between the nodes that were "closer" to each other given the start topology.

Nevertheless, disregarding the remarks, is there an already known scenario similar to this one where a triangulation is built upon a partially given set of triangles/edges?

• I'm guessing new edges wouldn't be created if they overlap existing edges? Else there would be an edge between the right-most and bottom-most nodes. But, what about creating an edge where a triangle already exists? Like if 2-5-3 already existed, could we place 2-4-3? (As in, do the we need a triangle for every set, or can one take the place of two) Aug 2, 2013 at 13:31
• New edges must not overlap existing ones since this would violate the basic requirements of a valid triangulation. If 2-5-3 already existed, then we would not be able to create 2-4-3 since it introduces an invalid overlapping/folding. Valid triangulations are the only restrictions. The algorithm should stop only if it becomes impossible to create a new triangle and it must not alter existing topology in any way. I will borrow your edited pic for future references if you don't mind :). Aug 2, 2013 at 13:55
• Sure thing, makes it easier to talk about. OK I'll be thinking about this, but I'm sure someone will beat me to an answer. In the meantime, here's a somewhat related question. Aug 2, 2013 at 13:58
• I've read the related problem; that algorithm is likely to build a triangle strip, rather than a more complex triangulation (i.e. it will most certainly not build consistent/exhaustive 1-ring neighbourhoods for most vertices in the set). Aug 2, 2013 at 14:30
• I have an idea that may help you. I won't take in count that you need speed, just the solution, you can manage to get it faster later (I suppose). First, try to get a convex set of vertices, running a modification to the convex hull algorithm you can get 4 sets (for this example) {1,2,3}, {2,3,4,5}, {1,3,4}, {1,4,5,6} and then, you can run the algorithm to triangulate convex polygons. Now, thinking while posting this comment, you can separate the graph into 3 sets of closed polygons and triangulate each one with a triangulation algorithm. Aug 11, 2013 at 13:06