Sign in to follow this  
Aldoric

Merge multiple 2D polygons algorithm

Recommended Posts

Aldoric    122
Hello! I need an algorithm to merge multiple 2-dimensional polygons together to one. The source polygons can even overlap themself. Its also possible that a second polygon is completly inside another polygon. The target polygon should be clear and have no overlapping edges anymore. This illustration shows what I mean where the red lines are the polygon edges. http://img196.imageshack.us/i/polygonz.png/ Any tipps or links? I didn't find anything, yet. Maybe I just don't know what to search for. Thanks in advance.

Share this post


Link to post
Share on other sites
OrangyTang    1298
Quote:
Original post by Aldoric
Any tipps or links? I didn't find anything, yet. Maybe I just don't know what to search for.

It sounds like you're after 'constructive solid geometry' or CSG. What language are you working in? I know a couple of libraries which do this for java but off the top of my head none C++ right now.

Share this post


Link to post
Share on other sites
Aldoric    122
Thank you! Due to your tipp I found out how to search for the algorithm. A search for "boolean union polygon" was the correct solution :)

I found this algorithm PDF file - It's german - but maybe someone is interested:
http://es.cs.uni-kl.de/publications/datarsg/Bran03.pdf

Also there is a GPC libary that offeres the solution in C code.

Thank you :)

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this