Re: [Algorithms] Cutting Ears Algorithm

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

On Wed, Jan 28, 2009 at 5:27 AM, Johan Gustafsson
<spi...@gm...> wrote:
> 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?

The problem is that you need to extend your "triangle contains any
other point" test to also include points that are exactly on the edge
from vertex i-1 to i+1.  Of course you will then run into numerical
issues with testing such things in your case above, so you need to use
exact arithmetic, or introduce some evil tolerances.   Or what you
might try is to pick the ear that maximizes the signed distance from
the i-1, i+1 edge to all other vertices.  Since you're guaranteed that
there are always 2 genuinely valid ears, this should always find you a
decent ear to clip.

--bb