Dark Bit Factory & Gravity

PROGRAMMING => General coding questions => Topic started by: relsoft on October 20, 2012

Title: Anyone knows how to convert a non-convex poly to 2 or more convex ones?
Post by: relsoft on October 20, 2012

Thanks!

It doesn't have to be fast ;*)

Title: Re: Anyone knows how to convert a non-convex poly to 2 or more convex ones?
Post by: hellfire on October 20, 2012

Check Ear clipping (http://en.wikipedia.org/wiki/Polygon_triangulation#Ear_clipping_method) and Seidel's algorithm (http://www.cs.unc.edu/~dm/CODE/GEM/chapter.html).
The complexity varies depending on whether you need to support holes and/or intersecting edges.
If you're using OpenGL you might want to have a look at the glu tesselation implementation (http://www.flipcode.com/archives/Polygon_Tessellation_In_OpenGL.shtml), too.

Title: Re: Anyone knows how to convert a non-convex poly to 2 or more convex ones?
Post by: relsoft on October 22, 2012

Thanks buddy, reading up on ear-clipping. ;*)