# Algorithm for joining two polygons based on set of 2D points

[Thanks for votes, I fixed the images now]

I am working on system, that does some fuzzy logic. I don't have any special types, everything is done with simple math. The last problem I am facing is joining of individual fuzzy results. Each fuzzy result is a fuzzy set, which is in my case represented as a 4-point polygon. The final result is then using a 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).

As I wrote at the beginning.. I am not using any special constructs for my operations. All fuzzy sets (polygons) are just defined by 4 points with x and y coordinates. So I start with something like:

set one = [A,B,C,D];
set two = [E,F,G,H];


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

set 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), because final result is centroid of that union and I already have algorithm to calculate centroid based on set of input points.

So far, I have found mentions about convex-hull algorithm, but I am afraid that it wouldn't generate correct result. I am afraid that it would generate following polygon:

EDIT:

Ok, I didn't realize that one upvote won't be enough.. nevermind. I'll just use links.

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 :)

• It's not clear what you are trying to do. Can you explain more precisely what you want the result to be? What are the inputs and outputs in your example image?
– user856
May 1 '11 at 5:44
• @Rahul Narain: I am looking for a way, how to programatically find a union of two polygons. The provided image might be confusing, because it seems like I already have it, but at image, there are actually two polygons layered, so it seems like one. My input is: 2 arrays of Point objects [A,B,C,D] and [E,F,G,H]. I need an algorithm, that will understand, that those two arrays represents coordinates of a polygon. And then the algorithm will be able to find a union of those two polygons, so the result will be one polygon (union of those two). Does it help? May 1 '11 at 5:51
• If someone could upvote me, I would try to edit my question and add new images that could help explaining it. May 1 '11 at 6:00
• @Rahul Narain: You are probably only one following this :) I have edited my question. Sorry for splitted links (there is a space after http:// ), but it's hard to post anything without 10 points :( May 1 '11 at 7:03
• Nobody? I thought that this will be some simple math algorithm :) May 1 '11 at 10:38