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.
Answer
- Remove all the vertices of the polygons which lie inside the other polygon: http://paulbourke.net/geometry/insidepoly/
- Pick a starting point that is guaranteed to be in the union polygon (one of the extremes would work)
- 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).
- Find the first intersection (if there are more than one). This is a point in your Union.
- 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.