与矩形相交的多边形并创建线条（部分切割）

我需要一种算法来与矩形相交（可能是非凸的）多边形。矩形将平行于xy平面，但多边形可以是任何方向。此外，我不只是需要一个真/假结果，而且需要多边形与矩形相交的确切点，以便我可以绘制多边形与矩形重叠的线。对于非凸多边形，这可能导致两条或多条相交线。与矩形相交的多边形并创建线条（部分切割）

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

我正在开发Java，所以如果Java3（2）D有任何内置的方法来帮助，那将是理想的。

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

这里有一个图片...我想红线作为交点的结果： alt text

来源

2010-10-17 Tony R

对于交叉多边形的每个线段并连接点有点微不足道的事情，你有什么反对吗？ – 2010-10-17 01:44:22

这就是我想象的解决方案。 Java3D能否与一个多边形相交的线段并返回交点？我必须小心非凸多边形相交两次，但我认为我可以处理，如果我只能得到交点... – 2010-10-17 01:53:47

我不知道Java3D，快速搜索显示这个：http： //code.j3d.org/using/geom_intersect.html – 2010-10-17 04:22:48

这应该找到所有的相交的部分，对于任意多边形。

将多边形看作边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-17 04:18:16

与矩形相交的多边形并创建线条（部分切割）

回答

相关问题