Efficient algorithm for generating a triangle mesh from a concave polygon

Question

I am working on a project that involves generating meshes of triangles from potentially concave polygons. I am far more interested in a performant solution than an optimal solution. Most of what I've come across involves using OpenGL (not an option) or focuses on optimally or approximately optimally decomposing into convex polygons, with O(n³) or O(n⁴). Ear clipping seems like the most straightforward solution and is supposed to be O(n²):

for /* ever */ {
    for each(vertex) {
        candidate := Triangle{previousVertex, currentVertex, nextVertex}
        if !candidate.IsInterior() || candidate.ContainsAnyOtherVertex() {
            continue
        }

        result.Push(candidate)
        vertex = vertex.Except(currentVertex)
    }

    if len(vertex) == 3 {
        result.Push(Triangle(vertex))
        break
    }
}

I don't see how this can be O(n²). As I see it, this will have to involve three nested loops, each proportional to N: the two explicit loops above, and candidate.ContainsAnyOtherVertex(). Am I missing something? Is there some way to detect whether the candidate triangle contains any of the other remaining vertices that does not involve iterating over all the remaining vertices?

Alternatively, is there a different algorithm I should use? I'd be fine with one that decomposes into convex polygons, but A) I don't care if the solution is optimal, and B) I am not interested in reading through CGAL's source code or academic literature.

Answer 1

Ear clipping is O(n²) if you do it this way:

• First, for each vertex with an angle < 180 degrees, count the number of vertexes inside its angle. (O(n²))
• You can clip + remove any such vertex with 0 count. You will do this O(n) times. When you remove a vetex:
  • First remove it from the counts of any triangles that it's in (O(n)); and
  • Count the other vertexes in the at-most-2 new triangles you form by clipping (also O(n)).