Re: [Algorithms] Cutting Ears Algorithm

[Bill B. <wb...@gm...>]

On Wed, Jan 28, 2009 at 7:56 AM, Jon Watte <jw...@gm...> wrote:
> 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.
>

In the situation he's describing he's left with just 4 collinear
vertices because of his initial choice of ear to snip.

--bb