Given an irregular polygon's vertex list, how to create internal triangles to build a flat 3D mesh efficiently?
computational-geometry, geometry, polygons, unity-game-engine
Solution
You could make use of a constrained Delaunay triangulation (which is not trivial to implement!). Good library implementations are available within Triangle and CGAL, providing efficient `O(n*log(n))` implementations.
If the vertex set is small, the ear-clipping algorithm is also a possibility, although it wont necessarily give you a Delaunay triangulation (it will typically produce sub-optimal triangles) and runs in `O(n^2)`. It is pretty easy to implement yourself though.
Since the input vertices exist on a flat plane in 3d space, you could obtain a 2d problem by projecting onto the plane, computing the triangulation in 2d and then applying the same mesh topology to your 3d vertex set.
Problem
I'm using Unity, but the solution should be generic. I will get user input from mouse clicks, which define the vertex list of a closed irregular polygon. That vertices will define the outer edges of a flat 3D mesh. To procedurally generate a mesh in Unity, I have to specify all the vertices and how they are connected to form triangles. So, for convex polygons it's trivial, I'd just make triangles with vertices 1,2,3 then 1,3,4 etc. forming something like a Peacock tail. But for concave polygons it's not so simple. Is there an efficient algorithm to find the internal triangles?