與矩形相交的多邊形並創建線條（部分切割）

我需要一種算法來與矩形相交（可能是非凸的）多邊形。矩形將平行於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

與矩形相交的多邊形並創建線條（部分切割）

回答

相關問題