將兩個凸的非相交多邊形合併爲一個

Question

我需要將兩個凸的非交叉多邊形合併爲一個連接的凸多邊形，以最小化所產生的面積，如下圖所示：​​我正在尋找一個這樣做的算法。如果有人向我提供相應的python實現，我也將不勝感激。

Answer 1

如果存在具有這樣說，m和n個頂點分別，那麼你的問題可以被認爲是兩個不相交的多邊形：

查找包含所有的M +的面積最小的凸多邊形n分。話雖如此，看看QuickHull Algorithm這裏：http://www.geeksforgeeks.org/quickhull-algorithm-convex-hull/

此外，你也可以檢查出這些算法。

賈維斯的算法：http://www.geeksforgeeks.org/convex-hull-set-1-jarviss-algorithm-or-wrapping/

而且，格雷厄姆的掃描：http://www.geeksforgeeks.org/convex-hull-set-2-graham-scan/

希望這有助於。

P.S.我想你可以在互聯網上的任何地方找到這些算法的python實現。 :)

Answer 2

發現兩組的凸包的工作，但下列方法可能更快，只需要訪問的多邊形頂點順序：

1. 鑑於多邊形P和Q，從每一個挑一個頂點p1和q1。

2. 在Q搜索頂點q2鄰接q1使得從p1-q1到p1-q2旋轉是順時針的（這可以使用easyly矢量叉積進行檢查）。

3. 重複上述步驟直到您到達點Q其中Q中的兩個連續頂點生成並逆時針旋轉。

4. 現在，將從p1行進的過程翻轉到P中的相鄰頂點，使得旋轉逆時針旋轉直到再次找到極值pl。

5. 從2開始重複，直到不再有可能。您現在有兩個點pm和pn，它們是兩個頂點，紅色區域的一邊與上圖中的黑色多邊形相交。

6. 現在再次重複算法，但改變方向，從順時針到逆時針，反之亦然，以便找到紅色區域另一側的頂點。

7. 剩下的唯一工作是從已經找到的兩個紅色區域邊和多邊形中的區段生成最終的多邊形。

Answer 3

對於一個有效的解決方案，你可以按照如下適應單調鏈法（https://en.wikibooks.org/wiki/Algorithm_Implementation/Geometry/Convex_hull/Monotone_chain）：

• 兩個多邊形，找到最左邊和最右邊的網站（在領帶的情況下，使用最高/最低）;

• 這些網站將多邊形分成兩個鏈，這些鏈按X排序;

• 合併兩個上部和兩個下部鏈，並在X上進行比較（這是mergesort的合併）;

• 使用與單調鏈方法（格雷厄姆步行的變體）相同的程序拒絕來自上部和下部鏈的反射位點。

總運行時間將由

• N + M比較管轄尋找極端點;

• n + m合併比較;

• n + m + 2 h LeftOf測試（有符號區域; h是結果的頂點數）。

因此，複雜度爲O（N + M），這是不是最佳的，但很可能是你的目的不夠好（更復雜的O（日誌（N + M）的解決方案，能夠把多邊形沒有重疊，但不值得忙亂對於小多邊形尺寸）。

在該示例中，合併的結果是鏈的只是級聯的，但可能會出現更復雜的情況。

最後的評論：如果你保留所有的polygo ns作爲兩個單調鏈的連接，可以省去上述過程的第一步。