Re: [Algorithms] Cutting Ears Algorithm

[Jon W. <jw...@gm...>]

Johan Gustafsson wrote:
> 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?
>   

The algorithm works fine. I don't understand why you think that the 
remaining 4 vertices couldn't make triangles that make ears? Even if 
it's concave, it will have at least 2 ears, unless it's also 
self-intersecting and/or flips winding.

Sincerely,

jw