Intersection between 3D flat polygons

How to find intersections between two (or more) 3D planar polygons (for the simplest case they are all convex)开发者_StackOverflow? Seeking algorithms able to provide the intersection line if there is any. Note the methods proposed for infinite Plane-Plane cases are not useful.

There are 2 cases:

Both polygons lie on the same plane.

Find all internal points to the first polygon.

Arbitrarily take the first polygon, loop through all the vertices of the 2nd polygon and determine whether they lie inside or outside the first polygon. Doing this is easy for convex polygons: see here.

Find the intersection points between the 2 polygons

To find the intersection points take each edge of one of the polygons and loop through all the edges of the other polygon to find if they intersect anywhere. this can be found by using the formula for the intersection of 2 lines.

The intersected region is the polygon formed with vertices at the internal points and the intersected points.

The 2 polygons lie on different planes.

Find the intersection of the 2nd polygon with the plane of the first one. You can do this by considering each edge of the 2nd polygon, and finding the intersection between the edge and the plane of the first polygon. This can be found using the formula for the intersection between a line and a plane.

Check whether the intersection points you found lie inside or outside of the first polygon.

Here is one way. By rotating one polygon to the XY plane, you reduce the 3D problem to a 2D problem (mostly), and it is normally not too much of a performance issue.

1. Rotate the points of first polygon so that it lies on the X-Y plane.
2. Rotate the points of the second polygon the same direction and amount as the first.
3. Check each line in the second polygon and see whether and where it intercepts the X-Y plane. With a convex polygon, this should happen twice, at points A and B.
4. Find all the intersections of line AB with the edges of the first polygon. There should be 0, 1, or 2 intersections if the first polygon is convex.
5. Case: Zero Intersections: the line AB is either completely inside or out the first polygon. If inside, AB is the intersecting line of the planes. If outside, there is no intersection.
6. Case: One intersection, point C: Either A or B is inside the first plane. That intersecting line of the planes is that inside point (A or B) to C.
7. Case: Two intersections: The intersecting line of the planes is AB
8. Rotate the intersecting line back to its original position, the reverse of the rotation done in step 1.

It is left as an exercise to the reader to extend this method to non-convex polygons. :) (It's actually pretty easy.)

One way to check to see if a point is inside a 2D polygon is to get the intersections of a line from that point upward with all the edges of the polygon. 0 or 2: outside. 1: inside. (This also works for a non-convex polygon using even and odd for outside and inside.)

For the case that both polygons are co-planar, then here is at least a solution for this particular case:

http://www.iro.umontreal.ca/~plante/compGeom/algorithm.html

It even has a nice applet showing the algorithm.