polygon union without holes

问题:

Im looking for some fairly easy (I know polygon union is NOT an easy operation but maybe someone could point me in the right direction with a relativly easy one) algorithm on merging two intersecting polygons. Polygons could be concave without holes and also output polygon should not have holes in it. Polygons are represented in counter-clockwise manner. What I mean is presented on a picture. As you can see even if there is a hole in union of polygons I dont need it in the output. Input polygons are for sure without holes. I think without holes it should be easier to do but still I dont have an idea.

回答1:

1. Remove all the vertices of the polygons which lie inside the other polygon: http://paulbourke.net/geometry/insidepoly/
2. Pick a starting point that is guaranteed to be in the union polygon (one of the extremes would work)
3. Trace through the polygon's edges in counter-clockwise fashion. These are points in your union. Trace until you hit an intersection (note that an edge may intersect with more than one edge of the other polygon).
4. Find the first intersection (if there are more than one). This is a point in your Union.
5. Go back to step 3 with the other polygon. The next point should be the point that makes the greatest angle with the previous edge.

回答2:

You can proceed as below:

first add to your set of points all the points of intersection of your polygons.

then I would proceed like graham scan algorithm but with one more constraint.

Instead of selecting the point that make the highest angle with the previous line (have a look at graham scan to see what I mean (*)), chose the one with th highest angle that was part of one of the previous polygon.

you will get an envellope (not convex) that will describe your shape.

Note:

it's similar to finding the convex hull of your points.

For example graham scan algorithm will help you find the convex hull of the set of points in O(N*ln(N)) where N is the number of points.

look up for convex hull algorithms, and you can find some ideas.

Hope it helps.

remarques:

(*)from wikipedia:

The first step in this algorithm is to find the point with the lowest y-coordinate. If the lowest y-coordinate exists in more than one point in the set, the point with the lowest x-coordinate out of the candidates should be chosen. Call this point P. This step takes O(n), where n is the number of points in question.

Next, the set of points must be sorted in increasing order of the angle they and the point P make with the x-axis. Any general-purpose sorting algorithm is appropriate for this, for example heapsort (which is O(n log n)). In order to speed up the calculations, it is not necessary to calculate the actual angle these points make with the x-axis; instead, it suffices to calculate the cosine of this angle: it is a monotonically decreasing function in the domain in question (which is 0 to 180 degrees, due to the first step) and may be calculated with simple arithmetic.

In the convex hull algorithm you chose the point of the angle that makes the largest angle with the previous side.

To "stick" with your previous polygon, just add the constraint that you must select a side that previously existed.

and you take off the constraint of haveing angle less than 180°

hope i'm clear

回答3:

I don't have a full answer but I'm about to embark on a similar problem. I think there are two step which are fairly important. First would be to find a point on some polygon which lies on the outside edge. Second would be to make a list of bounding boxes for all the vertices and see which of these overlap. This means when you iterate through vertices, you don't have to do tests for all of them, only those which you know have a chance of intersecting (bounding box problems are lightweight).

Since you now have an outside point, you can now iterate through connected points until you detect an intersection. If you know which side is inside and which outside (you may need to do some work on the first vertex to know this), you know which way to go on the intersection. Then it's merely a matter of switching polygons.

This gets a little more interesting if you want to maintain that hole (which I do) in which case, I would probably make sure I had used up all my intersecting bounding boxes. You also didn't specify what should happen if your polygons don't intersect at all. But that's either going to be leave them alone (which could potentially be a problem if you're expecting one polygon out) or return an error.