Re: [Algorithms] Cutting Ears Algorithm

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

Thanks for the feedback and even though I think the algorithm will work 
for my current
needs I would like to get some information on certain subjects you have 
all brought to the
table. First I'd like to define my problem and the reason why I'm 
triangulating (even shapes that
are already triangles fans)

I'm working on an editor that works in 2D space where the user creates 
shapes (simple polygons)
and inorder to render the created polygons I triangulate the shapes and 
send them off as triangle lists
to the renderer. Performance is not a primary concern since the number 
of vertices and shapes are
relatively low. Since the user input can indeed be already defined 
triangles, like the trianglefan previously
mentioned the algorithm will still process it.

At the moment the editor seems to run just fine but I get scared when I 
hear words like sliver since I dont
even know what a sliver is (english is not my 1st language), if someone 
could explain what a sliver is and
how one could occur or methods to avoid it please amuse me. Further you 
guys mention degenerate triangles,
I presume the algorithm can only cause a degenerate triangle to occur if 
the user inputs 3 colinear vertices or
the point in triangle test fails to include border cases (my triangle 
fan example).  The first case is simple to avoid
but the second case might be harder to avoid because of numerical 
stabilities during the point in triangle test.
Have I understood it correctly that exchanging the point in triangle to 
use a Delanuay constraint will solve this problem?
I'm having a hard time visualising this.