Polygon adding algorithm

Question

I want to do the following: I have some faces in the 3D space as polygons. I have a projection direction and a projection plane. I have a convex clipping polygon in the projection plane. I wnat to get a polygon representing the shaddow of all the faces clipped on the plane.

What I do till now: I calculate the projections of the faces as polygons in the projection plane.

I could use the Sutherland–Hodgman algorithm to clip all the singe projected polygons to clip to the desired area.

Now my question: How can I combine the projected (maybe clipped) polygons together? Do I have to use algorithms like Margalit/Knott?

The algorithm should be quite efficient because it has to run quite often. So what algorithm do you suppose?

Is it maybe possible to modify the algorithm of Sutherland–Hodgman to solve the merging problem?

Is there any possibility that the faces are the faces of a convex polyhedron? If so, then calculate the convex hull of the projections of the vertices. Then clip that polygon. — btilly
Yes, the faces are from polyhedrons. A single polyhedron could be restricted to be convex. But the overall union of all faces won't be in any sense convex. — Christian Wolf

jjrv jjrv · Accepted Answer · 2012-03-24T18:19:24

I'm currently implementing this algorithm (union of n concave polygons) using Bentley–Ottmann to find all edge intersections and meanwhile keeping track of the polygon nesting level on both sides of edge segments (how many overlapping polygons each side of the line is touching). Edges that have a nesting level of 0 on one side are output to the result polygon. It's fairly tricky to get done right. An existing solution with a different algorithm design can be found at:

http://sourceforge.net/projects/polyclipping/

Polygon adding algorithm

1 Answers