将多边形与矩形相交并创建线（剖面切割）

Question

我需要一种算法来将（可能是非凸的）多边形与矩形相交。矩形将平行于 xy 平面，但多边形可以是任何方向。

此外，我不仅需要真/假结果，还需要多边形与矩形相交的确切点，以便我可以在多边形与矩形重叠的位置绘制线条。对于非凸多边形，这可能会导致两条或多条相交线。

这将用于剖面切割模块，该模块可以对一组多边形进行切片并在形状与由 z 值指定的“平面”相交处创建 2D“切割”。

我正在使用 Java 进行开发，因此如果 Java3(2)D 有任何内置方法可以提供帮助，那将是理想的选择。

任何正确方向的帮助/指示将不胜感激！

这是一张图片...我想要红线作为相交的结果：

Answer 1

这应该找到任意多边形的所有相交线段。

将多边形视为边 AB、BC、CD 等的有序集合，其中从每条边的第一个点到第二个点的“方向”是“顺时针”。也就是说，如果我们看 A 点，顺时针移动时，B 点就是下一个点。

该方法是找到穿过平面的多边形的一条边，然后找到下一条线段，顺时针移动，穿过回到平面的原始一侧。这些线段与平面相交的两个点形成相交线段的端点。重复此操作，直到检查完所有多边形的边为止。

请注意，如果多边形是凹的，则并非所有线段都必须位于该多边形内。

   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       

此算法值得您为此付出的代价。 :-)