[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 🙂
Best Answer
I think the reason you're not getting any answers is that you asked a rather long question that's almost entirely algorithmic, with little or no mathematical content, and answers can easily be found by searching the Web e.g. for "merging polygons". Here's a post in comp.graphics.algorithms that answers your question in the general case. For your simple case, I'd suggest a), which is much simpler to implement than b) and c). Note, however, that this sort of thing is prone to rounding problems -- if it's possible that one of your points lies exactly on the boundary of the other polygon, that's likely to spell trouble because you won't be able to detect that exactly when intersecting the lines and you somehow have to make sure that different intersection tests are consistent despite rounding, e.g. you have to make sure you don't miss an intersection because both lines emanating from a point on the boundary test as non-intersecting because of rounding.