Re: [Algorithms] Cutting Ears Algorithm

[Graham R. ARA/S. <gr...@ar...>]

The standard ear-clipping algorithm can be problematic when you have
some vertices that are collinear. You can play with more robust
predicates to test to see if points are on the boundary edge of the ear,
but my suggestion is to change the ear test such that instead of testing
to see if any points lie inside the candidate ear triangle, test to see
if any points lie inside the circumcircle of candidate ear triangle.
This is a Delaunay constraint, and it will yield much better results,
e.g., fewer slivers or degenerate triangles. In your example case, the
circumcircle is much larger than the triangle. All of the collinear
points (except the two end ones) will be inside the circumcircle, and
because of this that first candidate ear will fail. You'll move to the
next point, which will more than likely pass the test and you'll be able
to remove that ear.

But, I wonder if you are thinking about the problem incorrectly? You
mentioned that you have a triangle fan. That's already triangles. Why
are you triangulating it? To triangulate this...I suppose, you would
find the boundary polygon, which is not a triangle fan, then triangulate
the boundary polygon using ear-clipping...

Graham

-----Original Message-----
From: Johan Gustafsson [mailto:spi...@gm...] 
Sent: Tuesday, January 27, 2009 3:27 PM
To: Game Development Algorithms
Subject: [Algorithms] Cutting Ears Algorithm

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?

------------------------------------------------------------------------
------
This SF.net email is sponsored by:
SourcForge Community
SourceForge wants to tell your story.
http://p.sf.net/sfu/sf-spreadtheword
_______________________________________________
GDAlgorithms-list mailing list
GDA...@li...
https://lists.sourceforge.net/lists/listinfo/gdalgorithms-list
Archives:
http://sourceforge.net/mailarchive/forum.php?forum_name=gdalgorithms-lis
t