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 ;)
Tarwin Stroh-Spijer
on Feb 25th, 2009
@ 3:17 am:
Wow, awesome stuff. The code I put together was a Java conversion. I kind of understand the idea behind it, but my Math’s so bad I could not have written it myself, so I can’t really understand the code properly either!
So super congrads on the code. Are you releasing it?
nicoptere
on Feb 25th, 2009
@ 2:55 pm:
hi,
thanks for passing by :)
I’ve added a link to the zip file, enjoy.
Controul > A quick note on line and segment intersection (as3)
on May 9th, 2009
@ 8:17 pm:
[...] like posting a small optimisation that accelerates the constraint checks at the end, which, as Nicolas Barradeau, pointed out, do need some [...]
an approach to triangulating polygons with holes | sakri rosenstrom blog
on Jun 12th, 2009
@ 1:09 pm:
[...] Katopz pointed me to this snippet which triangulates polygons. I’ve also seen an approach to ear cutting by [...]
makc3d
on Jun 16th, 2010
@ 4:07 pm:
oh look, I have finally found where these hits are coming from :) ga was reporting URLs up to “?”.
any way, right now I think the best implementation was by someone at box2d forums where they had an option to keep convex parts not tesselated.