三維平面多邊形之間的交集

如何查找兩個（或多個）三維平面多邊形之間的交集（對於最簡單的情況它們都是凸面）？尋求能夠提供相交線的算法，如果有的話。注意爲無限平面平面情況提出的方法沒有用。三維平面多邊形之間的交集

來源

2011-06-01 Developer

它們總是共面的嗎？如果不是交點可能是點，線或者什麼都沒有 – 2011-06-01 01:50:57

如果您指的是每個多邊形的頂點，那麼它們是共面的。然而，多邊形是3D的，並且可能不在同一個平面上，也就是說，相交可能是一個點或一條線或無效。 – Developer 2012-04-29 01:22:30

有兩種情況：

兩個多邊形位於相同平面上。

查找第一個多邊形的所有內部點。

任意取第一個多邊形，循環遍歷第二個多邊形的所有頂點，並確定它們是位於第一個多邊形的內部還是外部。對於凸多邊形，這樣做很容易：請參閱here。

查找2個多邊形

之間的交叉點要查找的交叉點取多邊形和環中的一個的每個邊緣通過其他多邊形的所有邊以發現它們相交的任何地方。這可以通過使用intersection of 2 lines的公式找到。

相交區域是由頂點在內部點和相交點形成的多邊形。

2個多邊形位於不同的平面上。

找到第二個多邊形與第一個多邊形的交點。您可以通過考慮第二個多邊形的每個邊，並找到邊和第一個多邊形的平面之間的交點。這可以使用公式爲line and a plane之間的交集找到。

檢查您發現的交點是位於第一個多邊形的內部還是外部。

來源

2011-06-01 02:00:20

我試過這個算法，兩個多邊形的一個躺在不同的平面上。儘管我有一些困難來有效地實現所討論的數學（鏈接）的代碼，但最終它的工作，這只是很重要。我已經嘗試過使用CGAL，但是因爲編譯等方面的嚴重困難而感到非常失望。我使用的方法總結爲首先對多邊形進行三角化（這裏出現一些困難！），然後找到交點。 – Developer 2011-06-10 10:23:57

對於兩個多邊形是共面的情況下，那麼在這裏是至少對於該特定情況下的解決方案：

http://www.iro.umontreal.ca/~plante/compGeom/algorithm.html

它甚至有一個很好的小程序示出的算法。

來源

2011-06-01 02:04:33 Hyperboreus

該算法僅適用於2D。問題是要求3D多邊形。 – 2011-06-01 02:07:41

是的。如果這兩個多邊形是共面的，這個算法就可以工作。但是，這不是在問題陳述中給出的。問題是每個單獨的多邊形都是平坦的。它並不是說它們都必須躺在同一架飛機上。 – 2011-06-01 02:09:42

這是一種方法。通過將一個多邊形旋轉到XY平面，可以將3D問題簡化爲2D問題（主要是），而且通常不會出現太多的性能問題。

旋轉第一多邊形的點，使得其位於在X-Y平面內。
旋轉第二個多邊形的點的方向和數量與第一個相同。
檢查第二個多邊形中的每一行，看看它是否以及在哪裏截取X-Y平面。對於凸多邊形，這應該發生兩次，在點A和B.
找到AB線與第一個多邊形的邊的所有交點。如果第一個多邊形是凸的，則應該有0,1或2個交點。
案例：零交點：AB線或者完全位於第一個多邊形的內部或外部。如果在裏面，AB是飛機的相交線。如果在外面，沒有交集。
案例：一個交點C點：A或B位於第一個平面內。該平面的相交線是內點（A或B）至C.
案例：兩個相交點：平面的相交線是AB
將相交線旋轉回原始位置，相反在步驟1中完成旋轉。

作爲練習，讀者可以將此方法擴展到非凸多邊形。 :)（其實很簡單）

檢查點是否在二維多邊形內的一種方法是從該點向上的線與該多邊形的所有邊交點。 0或2：外部。 1：裏面。（這也適用於在外部和內部使用偶數和奇數的非凸多邊形。）

來源

2011-06-01 02:29:07 xpda

我不知道如何將3D平面投影到所需的（例如xy）平面上。任何幫助？正如我從網上找到的，這個問題也不容易，因爲它看起來！ – Developer 2011-06-10 10:27:45

三維平面多邊形之間的交集

回答

相關問題