1

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

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

这适用于可以对一组多边形进行切片并创建二维“切割”的截面切割模块，其中形状与由 z 值指定的“平面”相交。

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

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

这是一张图片......我想要红线作为交叉点的结果： 替代文字

4

1 回答 1

0

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

将多边形视为边 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

该算法物有所值。:-)

于 2010-10-17T04:18:16.100 回答