3D中兩個凸多邊形之間的距離

我在3D中有兩個凸多邊形。他們都在不同的平面上，所以他們是一對面孔。3D中兩個凸多邊形之間的距離

什麼來計算這兩個多邊形之間的最近距離的最簡單的方法？

編輯：具有在第1多邊形的端點以及在第二多邊形另一個另一端點最短的線的長度。我正在尋找的距離是這條最短的線的長度。

來源

2011-02-24 Dmi

您是否正在尋找他們的兩個最接近的邊緣之間的距離的質心之間的距離，還是？ – 2011-02-25 00:00:43

兩個最近的邊緣。 – Dmi 2011-02-25 00:05:27

那麼不是兩個最近點之間的距離呢？你如何定義「最近邊緣」，並給出一個合適的定義，你如何定義兩個最近邊緣之間的距離？ – Troubadour 2011-02-25 00:20:13

這是線性約束和二次目標函數的簡單優化有限。有許多可以使用的算法，例如梯度下降。

來源

2011-02-25 02:15:44

您能否請進一步解釋 - 二次函數是什麼？ – 2011-02-25 02:28:11

目標是「最小化（x2 - x1）** 2 +（y2 - y1）** 2 +（z1 - z1）** 2」。給出最小距離的點也給出最小距離的平方。 – 2011-02-25 02:38:44

啊，對於每個邊，約束條件是「x1，y1，z1位於這樣的平面上」，「x1，y1，z1位於平面的這一半上」。輝煌！只要你能用一個等式*（我相信你可以，但說實話，我沒有任何想法）在三維空間中劃分一個平面，這會起作用，而且會更容易和比我的方法更容易出錯。 +1！ – 2011-02-25 13:22:32

-3

環路通過所述第一對象的所有頂點，然後在循環中，通過所述第二對象的所有頂點循環。在最內層的循環中，比較兩個當前頂點之間的距離並存儲最小距離。我一直這樣做，只要你沒有一個可笑的大網眼，它幾乎是瞬間的。

來源

2011-02-25 00:06:56 Davido

頂點可能不排隊。例如，這兩個多邊形可以以直角相互接觸，其中一個第二個多邊形的頂點接觸中間的第一個多邊形。 – Dmi 2011-02-25 00:10:20

它不清楚你試過了什麼。

This看起來可能對部分本身。

那麼你所要做的就是檢查所有的邊緣對。我希望在嘗試優化之前先實現這一點。

有可能是在考慮從一個質心的載體是在那個方向某種意義上其他，只考慮邊緣的優化。

來源

2011-02-25 00:54:38 Keith

這和Davido的回答不一樣。 – 2011-02-25 01:27:25

@BlueRaja，@Dmi。好的，錯過了指出的情況。它仍然看起來像一個相對愚蠢的算法應該工作。計算原始（表面，邊緣，頂點）對之間的距離還是確定需要計算哪些基元對的問題？或者確定即使檢查所有原始對符合要求？ – Keith 2011-02-25 01:57:44

這樣很好，除了一個多邊形可以以直角「接觸」其中一個多邊形的中心。在這種情況下，第二多邊形將具有接觸第一多邊形的平面的邊或頂點，但仍然與第一多邊形的邊緣相距一定距離。 – Dmi 2011-02-25 02:10:46

那麼，只有幾種可能性;兩個多邊形之間的最短線路可以是：

之間的兩個頂點
邊緣和頂點
兩個邊緣（想像垂直平面內的兩個多邊形）
頂點之間之間關係與多邊形的內部
或者多邊形相交

案例1-3的全部都通過將每個邊+頂點對視爲線段來處理，並列舉distance between all line-segment pairs。

情況4，找到distance between each vertex and the other polygon's plane。檢查以確保該線（從頂點到平面上的最近點）位於另一個多邊形內部;如果不是，那麼最短的路線到另一多邊形將在其周邊，這是已經在情況1或2
照顧（請確保爲做這種檢查既多邊形）

對於情況5，至少一個線段必須與另一個多邊形的區域相交 - 如果它們在它們的周界相交，我們將在1-3情況下捕獲它，並且如果頂點與該區域相交，則我們將具有在案例4中發現它。因此，只需檢查intersection of each edge with the other polygon's plane並查看交點是否在另一個多邊形內。
（請確保爲兩個多邊形做此項檢查）

採取所有這些發現的最小距離，我們就大功告成了。

來源

2011-02-25 02:14:01

這看起來很簡單，我會試試看。 – Dmi 2011-02-25 03:30:59

我想你忘了提及2個多邊形平行的情況。它包含在1-4中，所以沒有問題，但是在進行投影等數學運算時應該牢記這一點。由於搜索交叉點而不考慮並行情況往往會導致令人討厭的錯誤。例如，5的檢查需要觀察（每個邊與另一個多邊形平面的交點）。 – Alink 2011-02-25 06:27:28

@Alink：正確，我沒有提到它，因爲它包含在1-4中，但這是值得擔心的。其他多邊形案例中的邊緣/內部是另一個案例：它包含在案例3-4中，但仍然需要注意（至少用於測試）。 – 2011-02-25 13:10:39

大多數人都提出了這個線程是「走一個多邊形的所有點/邊，並比較各點其他的/邊緣」。如果你所做的只是比較兩個相當簡單的多邊形，並且你不太關心如何快速做到這一點，那麼這可能會正常工作。

但是，如果你想有一個相當簡單和更好的方法。如Ben Voigt所建議的那樣，使用二次優化方法（即Quadratic Programming）。基本上，您的多邊形是您的一組線性約束，即您的解決方案點必須位於多邊形的每個邊的內側（這是一個不等式約束）。而你的優化成本函數就是歐幾里得距離，即標準公式中的Q就是單位矩陣。一旦出現這樣的問題，你可以使用一個解決這個問題的庫（這裏有許多這樣的問題），或者你可以從一本書中學習它，併爲它編譯你自己的代碼（這是一個相當簡單的編碼算法）。

如果你想這樣做，例如，如果是簡單的多邊形到多邊形測試是邁向更復雜的三維形狀的第一步（如由多邊形的固體）真正的方法。那麼，你應該很可能只是使用已經做到這一點的軟件包。 Here是一組碰撞檢測庫，其中許多輸出穿透深度或等效最小距離。

來源

2011-02-25 03:14:47

謝謝，這看起來像一個有趣的話題。我不會走向更復雜的形狀，只是尋找3D面的簡單距離對。 – Dmi 2011-02-25 03:28:47

3D中兩個凸多邊形之間的距離

回答

相關問題