Constructing the Data Structure:
First of all, to make things simpler, we enclose the whole triangulation in a large enough triangle in such a way that none of its edges intersect the others.
This will represent the outter face (labeled here as "O"):
We take the obtained graph and we process it in the following way:
- We find an independent set of vertices with degree less than or equal to 8 inside the hull:
- We remove them from the graph, obtaining independent holes:
- We retriangulate these holes (by following the same rule for labels as before):
- We repeat the above steps until we are left with 3 vertices (the large triangle).