在多邊形內隨機放置多邊形

Question

我有兩個多邊形定義爲一系列2D浮點值。它們不保證是凹面或凸面的。他們不交叉自己。他們不能旋轉。我想根據它的大小隨機放置一個。主要問題是效率。我必須在幾秒鐘內完成約200次。

我一直在尋找這個好幾天了，而且沒有任何明顯的進展。任何線索將不勝感激。

Answer 1

^{免責聲明：如果你想收拾多個多邊形一個更大的多邊形內部的話，我認爲，this problem is NP hard所以這是不可能的高效和精確算法可以被開發來解決這個問題。多邊形可以在一個平面上連續平移和旋轉，這意味着佈局可能是無限的，這使得問題的解空間也是無限的。如果您只是試圖找出較小的多邊形是否可以放入較大的多邊形中，那麼我缺少一個有效的答案，但正如您所問 - 「任何線索都會被讚賞」 - 這裏是一個。}

---

讓更大多邊形是B和（要被插入的一個）較小的多邊形是S. B具有總B點和S具有總共s指向。

---

下面的圖像示出了邊界框和最小邊界矩形。我們用這個來獲得快速失敗過濾器（非常簡單的想法......在下一段定義）。下面顯示的方框（a）計算速度更快，而方框（b）對於過濾更精確。畫出這個盒子，可以爲您的情況提供更好的投資回報。雖然在下圖中它們都是橢圓而不是多邊形，但你明白了。

http://portal.ku.edu.tr/~cbasdogan/Tutorials/imageU21.JPG

^{（圖像摘自：http://portal.ku.edu.tr/~cbasdogan/Tutorials/imageU21.JPG）}

癥結：如果B的任何線與S的任何線相交，或者如果S的所有線是外側乙，B不能取S in。

快速失效過濾器：獲取B和S的邊界矩形。如果無法將S的邊界矩形放置在B的邊界矩形內，則不能將多邊形S放置在多邊形B內。這樣，如果沒有B封閉S的機會。下圖說明了三種情況。

^{（圖像摘自：http://www.cs.berkeley.edu/~ug/slide/pipeline/assignments/as4/figures/boundcull.gif）}

---

預處理：確定線的形成B.存儲它們在一個HashMap<<Point, Point>, Line>用於步驟方程這將在稍後完成。您可以通過斜坡米和攔截ç和你的線的端點唯一定義線將成爲HashMap中的鍵（<Point, Point>）。

---

的算法：

對於已經經過上述過濾器每S：

1. 閱讀S的點，並確定形成S-
2. 對於每一個線的線的S，看看它是否與B的任何一行相交（它們都存儲在HashMap alr中） eady）
3. 如果沒有交點，S在B裏面，你所要做的就是畫線而不用擔心交點。

在最壞的情況下，該算法的複雜性將是O（BS）用於繪製每個多邊形。

---

^†_{這一步是寫蠻力保持算法中容易理解。否則，這裏可能會提供更快的結果的關鍵優化。您可以過濾B的行。如果B行的終點位於S的最左側的點的左側或S的最右側的右側，則不需要考慮B的一條線與S的交點S或小於S.這可以節省很多計算。}

Answer 2

如果這裏的其他答案是有用的，這是它的附錄。它顯示了另一種方法來查看較小的多邊形是否在較大的多邊形內。

要測試多邊形包容，可以看看是否包含多邊形的所有邊。爲了測試所有邊緣，測試是否包含了每條邊的所有點。

1. 緻密通過將已有的頂點之間的頂點的小多邊形。下圖顯示了一條線的緻密化。
2. 現在對於緻密的多邊形，測試它的點是否都位於外部多邊形內。這個測試可以通過在兩側畫出從發出點到無窮遠點的線，然後計算該線與多邊形相交的次數。
3. 如果所有點都在內，那麼多邊形在內。

---

_{First Image source。}

^{Second Image source。}