Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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

share|improve this question
    
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? –  Rahul 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? –  Nsltpm 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. –  Nsltpm 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 :( –  Nsltpm May 1 '11 at 7:03
    
Nobody? I thought that this will be some simple math algorithm :) –  Nsltpm May 1 '11 at 10:38
add comment

1 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.

share|improve this answer
    
Ok, thank you. Sorry for long question, I tried to make it shorter, but I probably didn't explain it well so I had to add more. –  Nsltpm May 2 '11 at 6:30
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.