Re: [Algorithms] Cutting Ears Algorithm

[Simon F. <sim...@po...>]

Bill Baxter wrote:
> 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

> 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.

I just wanted register my vote for using exact maths. I initially tried
using epsilons in my triangulation code (which handled
self-intersections) but it did not turn out well. I rewrote it using
exact mathematics and it was much cleaner.

Cheers
Simon