I've developed a polygon triangulation algorithm which uses a process similar to the "Graham Scan" to remove convex "portions" of a concave polygon. I couldn't find the proper nomenclature for those "portions", and I'd like to name the algorithm after it.
I'm not a mathematician, so I can't provide a formal definition, but it extends the concept of an "Ear" - a triangle formed by a convex vertex and it's neighbours, which contains no other vertex inside it - to a consecutive convex subset of points of the polygon.
The algorithm for finding a "big ear" is:
- Start from a reflex vertex $v(p)$, so that $v(p+1)$ is not reflex
- Iterate forward
- For each vertex $v(p+n), n \ge 1$, check if the angle $[v(p+n+1),v(p),v(p+1)]$ is smaller than $180^\circ$
- If yes, continue
- If no, the "big ear" ends on $v(p+n)$
- Check if there's a vertex inside the "big ear" ending on $v(p+n+1)$
- If yes, the "big ear" ends on $v(p+n)$
- If no, continue
EDIT:
I forgot to list two supplementary rules:
- If $v(p+1)$ is reflex, do $p = p+1$ and start over
- If $n>1$, before any further check, if $v(p+n)$ is reflex close a "big ear" on $v(p+n)$
