移動兩個多邊形的距離因此他們觸摸邊緣

Polygon

我需要知道的最小距離在一個軸線移動的參考多邊形（以紅色顯示）（只是Y），使得將正好接觸其他多邊形。如果它在多邊形內部，它將需要向外移動。

我試圖查看一個多邊形中的所有線和另一個多邊形中的所有點，將點投影到線上，並獲得點y與投影點y之間的差異，然後找到最小距離。但是，這具有如下問題：如果多邊形重疊並且一個多邊形中的最遠線和另一個多邊形中的最遠點具有最小距離，則會導致多邊形重疊的結果。

編輯：通過投影線上的點，我的意思是找到線上具有與原始點相同的x值的點上的y值。如果x值位於該行之外，則跳過此步驟。

來源

2015-10-16 Jacob Parker

我建議添加標籤'geometry'和'computational-geometry'來吸引更多的讀者（不能自己做，編輯需要超過10個字符，grrr！） – kebs

那麼，你有兩個答案，而不是一個單一的評論或從你的讚賞？你真的有興趣嗎？你找到另一種解決方案嗎？如果是這樣，請捐助，你也可以回答你自己的問題。 – kebs

我不確定我是否正確理解了您的建議（什麼是「投射點到線上」？）。

無論如何，我會嘗試這（僞代碼）：

for pA: points of polygon A: 
    for sB: segments of polygon B 
     compute distance along y-axis d(pA,sB) and store in table 
Find minimum distance in table: d1 
Proceed as above by reversing A and B: d2 
final d = min(d1,d2)

但不幸的是，這可能是不好的，如果你的多邊形是凹的，這似乎是這樣。

來源

2015-10-16 09:09:15 kebs

補充說明 –

您需要在兩個多邊形的每個頂點繪製垂直線並確定其與多邊形的交點（線/多邊形交點由不相交間隔組成）。

在給定的垂直方向上，計算多邊形的最高端點與其他最低端點之間的差值。答案是所有垂直線之間的最小差異（可以是負數）。

要有效地執行計算，可以使用scanline原則：從左到右排列所有頂點並保持「活動列表」，該列表是與當前垂直相交的邊緣列表。當你從一個頂點移動到另一個頂點時，你將更新這個列表。

對於尺寸爲N和M的兩個多邊形，排序將花費O(N+M)Log(N+M));那麼掃描將花費約O((N+M)K)，其中K是垂直與多邊形的交點的平均數量，通常是2到4之間的小數。

來源

2015-10-16 11:51:52

移動兩個多邊形的距離因此他們觸摸邊緣

回答

相關問題