Intersect polygon with rectangle and create lines (section cut)

Question

I need an algorithm to intersect a (potentially non-convex) polygon with a rectangle. The rectangle will be parallel to the xy-plane, but the polygon could be any orientation.

Furthermore, I don't just need a true/false result, but also the exact points where the polygon intersects the rectangle, so that I can draw lines where the polygon overlaps the rectangle. For non-convex polygons, this could result in two or more lines of intersection.

This would be for a section-cut module that can slice a set of polygons and create a 2D "cut" where the shapes intersect the "plane," specified by a z-value.

I'm developing in Java, so if Java3(2)D has any built-in methods to help, that would be ideal.

Any help/pointers in the right direction would be greatly appreciated!

Here's a picture... I want the red line as a result of the intersection:

Answer 1

This should find all the intersecting segments, for any arbitrary polygon.

Consider the polygon as an ordered collection of edges AB,BC,CD,etc, where the 'direction' from each edge's first point to its second point is 'clockwise'. That is, if we're looking at point A, point B is the next point when moving clockwise.

The method is to find an edge of the polygon that crosses the plane and then find the next segment, moving clockwise, that crosses back to the original side of the plane. The two points where these segments intersect the plane form the endpoints for an intersecting segment. This is repeated until all the polygon's edges have been checked.

Be advised not all segments are necessarily within the polygon if it is concave.

   let P be any point on the polygon.

   TOP:
   while (P has not been checked)

       mark P as having been checked.

       let f be the point following P, clockwise.

       if (P and f are on opposite sides of the plane) then

          Continuing from f clockwise, find the next point Y that is on
              the same side of the plane as P.
          Let z be the point counter-clockwise from Y.
              (note - Sometimes z and f are the same point.)

          let S1 be the point where P,f intersects the plane
          let S2 be the point where Y,z intersects the plane

          if (segment (S1,S2) is inside the polygon)
              add (S1,S2) to a 'valid' list.
              let P = Y
          else
              let P = f
          endif    
       else
          let P = f
       endif
   endwhile       

This algorithm is worth what you paid for it. :-)