How to merge two polygons (arrays of objects) programatically?

Question

[edit: I tried to rewrote my question a bit because it seems, that nobody understands what I want... and I thought, that it is a hard algorithm only for me :) ]

Problem I am facing is joining of individual polygons. Each is a 4-point polygon. The final result is then a merge / union of two polygons.

Following image shows one version of possible result (results may vary, because that black filled part can be different for each result).

I start with something like:

Polygon one = [A,B,C,D];  // (A/B/C/D) might look like : new Point {x = 10, y = 15} 
Polygon two = [E,F,G,H];

And I need an algorithm for calculating union of these two sets, so I will get result like:

Polygon total = [I,J,K,L,M,N]; // = new points

I don't have to visualize it (even when I do..), I just need the set of points defining new polygon (union of those two), because my final result will be a centroid of that merged polygon.
I already have algorithm to calculate centroid based on set of input points. But I need to get the right points first.

So far, I have found mentions about convex-hull algorithm, but I am afraid that it would generate following polygon (which is wrong):

EDIT:

So different way, how to look at this problem: I have a program, that is able to work with objects, that are represented by 4 points. Each point has two attributes (x coordinate, y coordinate).
Then the program is able to draw lines between these points. These lines will then look like a square, rectangle or polygon.. this result depends on given coordinates, but I know, that I will be always using points, that will generate polygons. Once the points are connected, the program is able to fill this connected area. Once this is drawn, you can see following image:

BUT: The program doesn't know, that he just made a polygon. He only knows, that he got 4 points from me, he connected them and filled them.

Then I have second object (=polygon), which is defined by another set of points (different coordinates). Program again doesn't know that he's creating a filled polygon.. he just did some operations with 4 given points. Result in this case is another polygon:

Now, we just draw two polygons at display.. and we gave them such coordinates, that they overlap each other. The result looks like this (considering only the filled area):

My program just draw two polygons. Fine. You can see at your screen only one polygon (because there are two overlaping = they look like one piece) and I need to count the centroid of that ONE piece.

I already have an algorithm, that will accept a set of points (representing a points forming polygon) and counting a centroid from these points. But I can't use the algorithm now, because I can't give him the needed points, because I do not know them.

Here are the points, that I want as a result:

So my algorithm should start with points A,B,C,D,E,F,G,H and he should give me points I,J,K,L,M,N as a result.

Summary: I need to count a centroid of polygon which is result of union/merge of two individual polygons, that are overlapping.

And I thought, that union of two polygons would be enough to explain :)

Answer 1

Here http://www.codeproject.com/KB/recipes/Wykobi.aspx is a collection of Computational Geometry algorithms. At least you can start from there.