The goal is to be able to triangulate planar polygons (with holes) for WebGL applications.
While reading Chapter9 of DeBerg Computational Geometry they use a method of engulfing all points inside a super triangle and then pulling a point one by one from a list and adding it into the triangulation while "legalizing" edges as they go.
Question1: I suspect this method does not take into account constraints or holes, because it treats the input vertices as a point cloud and would be difficult to retrofit into a constrained, or conforming triangulation. Is that correct ?
Question2: I understand "Delaunay" is simply the idea of applying the circumcircle test to each triangle in a triangulation and as such ANY trianhulation method can become Delaunay if the test is applied to it. Is that correct ?
Question3: There are various algorithms over the years dealing with triangulation such as from Chew, Ruppert, Schewchuk, Klein, Yung, etc
I understand the general conceptual steps involve:
- A base triangulation (by any method)
- Edge flipping to make it Delaunay
- A refinement step adding Steiner points and/or circumcenters
These approaches aim at making the triangulation faster (typically O nLogn), but often at the expense of complex data structures and logistics.
In you experience what would be the preferred conforming Delaunay triangulation algorithm (and steps) that can handle arbitrary polygons that in practice is simple to implement even at the expense of some performance ?
Could you provide some detail (or a reference) on how such algorithm is implemented (from start Triangulation step) to finish (refinement step) ?
