行距2D中的兩個凸多邊形等距

給定2D空間中的兩個凸多邊形，將如何構建線段，該線段在線條上的任意點與距離其最近點的距離相等凸多邊形？行距2D中的兩個凸多邊形等距

我正在尋找實現Voronoi圖的凸多邊形而不是點，但我不確定如何開始計算只有兩個多邊形的線。所以我想我會一步一步從這裏開始。

編輯爲了讓問題更清楚些，我想平分飛機（或其子集）。

假設我們在左邊有多邊形A，右邊有多邊形B.會有一些二等分線將飛機劃分爲左側點和右側點。線上的每個點與多邊形的距離相等。線的每一點離多邊形A比多邊形B更近。該線右邊的每個點最接近多邊形B.

下面是一個由Matlab腳本生成的圖像，我寫了一個近似值的蠻力：

approximate bisecting line

的問題，我相信，是不是在檢查空間的兩個多邊形「之間」那樣簡單，因爲行必須在兩個形狀之間直接延伸到的區域。理想情況下，我希望找到一種可以推廣到兩種以上形狀的解決方案，對我而言，這似乎使問題複雜化得更多。這裏有一個如何，可能看起來（顯然很粗糙）近似：

more complicated example

來源

2011-11-15 Eric G

好吧，繼續在一段時間我想看看在自己的多邊形最近點一步。比方說，一個在一個是最接近點乙和b在乙是最接近點一個。您知道AB的中間點位於期望的區段中。

a有什麼可能性？它可以是頂點A或者它可以是一側的一個點。同樣適用於b。「等距段」會發生什麼？如何在每種情況下構建它們？由於這些段與多邊形的邊等距，所以它們必須是包含相應邊的線的line that bissects the angle的一部分。

來源

2011-11-15 18:34:09 madth3

但是，我們如何確定離多邊形更遠的平分線的點（而不是在正常使用單詞之間）？很容易挑選一個隨機點並計算它到每個多邊形的最小距離並查看它們是否相同。但是由於這需要檢查每個點，所以我對一種算法方法感興趣，這種算法不需要簡單地選擇一個點並檢查它是否滿足標準。（我已經更新了我的問題，希望這是我要問的更清楚一點） –

我不是故意使用隨機點並檢查關閉點。我也編輯了我的答案，看看是否更清楚。在初始點之後還添加了一個想法。 – madth3

我是否正確理解你，但假設你想要有效地平分2個凸多邊形之間空間的線？如果是這樣，那麼...

發現，加入2個多邊形線（P1 & P2）
- 找到每個多邊形中心（P1。中心& P2.centre）通過計算平均X和Y座標。
- 發現每個那是最接近對方的中心多邊形頂點（P1.vc & P2.vc）
因爲P1.vc & P2.vc現在定義的連線P1 P2 &
- 找到P1.vc &的中點（MP）P2.vc

二等分線=線接合P1.vc的垂直& P2.vc穿過mp

來源

2011-11-15 19:11:57

部分，是的。但是，不是將兩個多邊形之間的空間平分，而是將整個平面（R^2）劃分爲兩個凸多邊形之間的空間。因此，您可以查看平面中的任何點，並根據所在的線的哪一側知道它最接近哪個多邊形。 –

行距2D中的兩個凸多邊形等距

回答

相關問題