[Algorithms] Cutting Ears Algorithm

[Johan G. <spi...@gm...>]

I have implemented the cutting ears algorithm for polygon triangulation 
but have
run into a problem. The algorithm will cycle thru all vertices of the 
polygon and
determine if the given vertex makes an ear (triangle that does not 
contain any other
point), if a vertex is determined to be an ear a triangle will be 
created and the
vertex is removed from the search space. The problem is when a vertex 
that is
an ear is shared between other vertices that cannot become an ear by 
themselves,
consider a triangle fan where the first vertex fans out to 4 other 
vertices on a
straight line, the first vertex will be considered an ear and create the 
first triangle but
the algorithm will remove it from the search space and the remaining 4 
vertices
cannot make another ear causing a valid simple polygon to fail the 
triangulation.

My questions are, is the algorithm uncapable of handling this scenario 
or have I
simply implemented it incorrectly?

Any idea how I would go about modifiying the algorithm to handle this case?