this is an algorithm to triangulate concave shapes. the result is not quite as pretty as a Delaunay triangulation but it does a nice job.

UPDATE have you ever felt like you were the smartest person on earth and suddenly you wake up brutally ?
this is what happened today : http://makc.coverthesky.com/FlashFX/ffx.php?id=18
this simply cancels this article and throws its content to rubbish where it belongs.

this one might come in handy for physics simulations whatever
it’s an algorithm that triangulates a concave simple polygon.
what is a concave simple polygon?
basically a non-self-intersecting one.
this means that it CANNOT TRIANGULATE ANY SHAPE. Yet it’s quite sharp and fast enough for what it’s intened to do: pre-processing

there was already a nice port here : http://blog.touchmypixel.com/archives/17 unfortunately, first I found it too late, second I was not clever enough to understand clearly what was happening :/ (shame on me)
So I did my own brew based on what I could understand from that document:
http://cgm.cs.mcgill.ca/~godfried/teaching/cg-projects/97/Ian/introduction.html
a good thing about my version is that it determines the direction of the poly before starting the triangulation which means that you can draw in both directions (very often you have to start drawing CCW).
I’ve also added a self-intersection test. if ever you’re not sure wether the shape will be self interscting or not. you should pass the cut()’s method’s additional parameter to true (defalult is false so beware).
like:

var triangles:Array = EarCutting.cut( points, TRUE );

It will prevent the script from freezing everything yet as it checks all possible intersections between segments, it really is expensive ( for the horse’s shape’s check it’s something like 5 times the process time )

Otherwise there’s not much to say.
check out the demo to understand what this whole shit means.

onclick, first you’ll see teh shape to be triangulated, then the triangle set.

eidt: the source files can be grabbed here
and by the way:
the segment intersection function comes from Keith Hair’s blog (pretty nice job :) ): http://keith-hair.net/blog/2008/08/04/find-intersection-point-of-two-lines-in-as3/
I think something can be done to accelerate the ‘as_seg’ section though ;)

Tags: algorithm, cutting, ear, geometry, polygon, triangles, triangulation