I can decompose a simple concave polygon to convex one, but can''t found the algrithom for decompose a complex(with holes,self-intersect) concave polygon to convex... Who can introduce me some articles or algrithoms about this problem?

long story short- there are plenty of clipping libraries out there, why write your own?

GPC- best one, but GPL
LGPL replacement for GPC but is ''work in progress''
comparison of various libs

if you''re looking into algorithms and stuff, check out the GPC page-links/references section.

-eldee
;another space monkey;
[ Forced Evolution Studios ]

Do NOT let Dr. Mario touch your genitals. He is not a real doctor!

what are GPC? I can''t find it...

quote:Original post by initial_y
what are GPC? I can't find it...

Just follow eldee's link...

BTW: GPC is not under the GPL, but some kind of proprietary license. The author just stated, that it is free for non-commercial use. You can actually use it commercially, but you'll have to negotiate with the author - no idea what he might ask for. Perhaps just some credits, perhaps lots of cash, probably depends on the size of the project. Anyway, GPC is an excellent clipping library - the best I've come across so far.

If you want to decompose a concave poly into convex pieces, then why not using a simple triangulation algorithm. It will decompose any concave polygon into triangles (that are convex by definition). Here is a nice simple and stable triangulator with source.


[edited by - Yann L on November 9, 2002 1:17:54 PM]

just thought i''d mention that i found another-
it''s called GTS and it''s an LGPL library that does a whole lot of
stuff. apparently it''s really fast, but i havent had a chance to
check it out yet.
take a look

-eldee
;another space monkey;
[ Forced Evolution Studios ]

Do NOT let Dr. Mario touch your genitals. He is not a real doctor!