[edit: I tried to rewrite my question a bit, because it seems that no one understands what I want ... and I thought that this is a tough algorithm just for me :)]
The problem I am facing is combining individual polygons. Each of them is a four-point polygon. The end result is a union / union of two polygons.
The following image shows one version of the possible result (the results may vary because this black filled part may be different for each result).
I start with something like:
Polygon one = [A,B,C,D];
And I need an algorithm to calculate the union of these two sets, so I get the result as:
Polygon total = [I,J,K,L,M,N]; // = new points
I don’t need to visualize it (even when I do it ..), I just need a set of points defining a new polygon (the union of the two), because my final result will be the centroid of this combined polygon.
I already have a centroid calculation algorithm based on a set of input points. But first I need to get the right points.
So far, I have found mentions of the convex hull algorithm, but I'm afraid that it will generate the following polygon (which is wrong):
EDIT:
So differently, how to look at this problem: I have a program that can work with objects that are represented by 4 points. Each point has two attributes (x coordinate, y coordinate).
Then the program can draw lines between these points. These lines will look like a square, rectangle or polygon. This result depends on the given coordinates, but I know that I will always use points that will generate polygons. Once the points are connected, the program can fill in this connected area. After that you can see the following image:
http://i51.tinypic.com/28037ee.png
BUT: The program does not know that he just created a polygon. He only knows that he has 4 points from me, he tied them and filled them.
Then I have a second object (= polygon), which is determined by a different set of points (different coordinates). The program again does not know that it creates a filled polygon. He just did some operations with four given points. The result in this case is another polygon:
http://i53.tinypic.com/qnog9w.png
Now we just draw two displayed polygons. And we gave them such coordinates that they overlap each other. The result looks like this (considering only the filled area):
My program just draws two polygons. Good. You can see only one polygon on the screen (because there are two overlays: they look like one part) and I need to calculate the centroid of this ONE part .
I already have an algorithm that will take many points (representing the points that make up the polygon) and count the centroid of these points. But now I can’t use the algorithm, because I can’t give it the necessary points, because I don’t know them.
Here are the points I want as a result: http://i51.tinypic.com/1z19vtj.png
So, my algorithm should start from points A, B, C, D, E, F, G, H, and as a result, it should give me points I, J, K, L, M, N.
Summary: I need to calculate the centroid of a polygon, which is the result of combining / merging two separate polygons that overlap.
And I thought that union of two polygons would be enough to explain :)