Product of 2 polygons.

This may sound wierd but I would like some code to add together two polygons giving one polygon as the result. Each polygon is made of array data points. The format is
array[x,y,x2,y2.....]

I'm not very good at making agorithems, I thought it might first check for line intersections, then divide the line into two lines, these would be saved as temp vars. If either of the two lines resides within a polygon delete the line segment. Then the data of lines is saved into a temp var list and returned. THis might not work and I have no idea how to impliment it.


I have something very innovative planned for this.

Something like this should be quite easy to realize using ScanLine algorithms as it will notify you when you reach a point "within".
It will also tell you the intersection point when it reaches it.

Using those data should enable you to easily drop the "within vertices" for the edge ones.

*I'm sure there are more efficient methods after all. But using Scanline is quite efficient and at least easy to understand what it does ^^*

You can also do this by creating BSP trees for each of your polygons lines.

From those trees you can send each line down the other's tree - splitting it where is intersects and keeping/throwing away the portions outside/inside.

Then you put all lines left into a new polygon by matching up joining ends and finally reduce the lines by joining those which are inline.

There may be more efficient methods like Dreamora says, I expect there is a more efficient scanline method, but I personally have done this with BSP without much fuss. (C++ I'm afraid and the code doesn't belong to me)

Hmm, BSP is a good idea I think.
http://www.3dtechdev.com/tutorials/illegalgeometry/illegalgeometrytut.html
Put these 2 polygons together as 1 polygon, build a BSP tree of it and remove illegal geometry.

cu olli

Great link!

Thanks for all your help guys. :)