Hausdorff凸多邊形之間的距離

Question

我有興趣計算由頂點定義的2個多邊形（特別是幾乎爲矩形的四邊形）之間的Hausdorff距離。它們可能重疊。 （A，B）= \ max（d（A，B），d（B，A））$其中$ d $是Hausdorff半度量 $ d（A，B）= （a，b）$中的A，B，B，D，

如果給定$ A $，$ {A_i} $，$ d（A，B）= \ max {d（A_i，B）} $？的有限不相交覆蓋，其推論是$ d（A，B）= d（A \ setminus B，B）$。

我找到了Atallah 1 (PDF)的論文。我對使用Python感興趣，並願意接受任何預編程的解決方案。

Answer 1

對於凸多邊形，d(A, B)是從頂點A到B中任意點的距離的最大值。因此，如果可以計算從任意點到凸多邊形的距離，則Hausdorff距離不太難計算。

要計算從點到凸多邊形的距離，首先必須測試該點是否位於多邊形內（如果距離爲0），然後如果它沒有找到任何點的最小距離邊界線段。

您的其他查詢的答案是否定的。作爲一個例子，讓A和B都是以原點爲中心的相同的2x2平方。分區A分成4個1x1的正方形。從每個A _我到B的Hausdorff距離是sqrt(2)，而是從A到B的距離爲0。

UPDATE：有關頂點的權利要求不能立即明顯，因此我將繪製一個證明在任何有限數量的維度上都是好的。我試圖證明的結果是，在計算d(A, B)中的兩個多邊形和B凸時，只需找到從頂點A到B的頂點的距離即可。 （B中的最近點可能不是頂點，但A中的最遠點之一必須是頂點。）

由於二者都是有限閉合形狀，所以它們是緊湊的。從緊湊性來看，必須存在p中的A，儘可能遠離B。從緊湊性來看，B中必須存在q的點，該點儘可能接近A。

僅當A和B是相同的多邊形時，此距離爲0，在這種情況下，我們很清楚在頂點A處實現了該距離。因此，不失一般性，我們可以假設從p到q有正距離。

繪製垂直於從p到q的行的q的平面（更高維度，某種超平面）。 B中的任意一點能穿過這架飛機嗎？那麼如果有一個，例如r，那麼從q到r的線段上的每個點必須在B中，因爲B是凸的。但很容易證明，該線段上的點必須比q更接近p，這與q的定義相矛盾。因此B無法穿越這架飛機。

顯然p不能是內部點，因爲如果是，則沿射線繼續從q到p，你會發現在A是從B是有界的背後，矛盾的p定義的平面更遠點。如果p是A的頂點，那麼結果是平凡的。因此，唯一有趣的情況是p位於A的邊界上，但不是頂點。

如果是，那麼p在表面上。如果該表面不平行於我們構造的平面，則沿着該表面行進將很容易，遠離我們所在的面後面的B平面，並且找到距離B遠的點比p更遠。因此該表面必須平行於該平面。由於A是有限的，因此該表面必須在某個頂點終止。這些頂點距離該平面的距離與p相同，因此距離B至少與p差不多。因此，存在至少一個頂點A，儘可能遠離B。

這就是爲什麼它足以找到從多邊形的頂點到另一個多邊形的距離的最大值。

（我離開構造一對多邊形與q不是一個頂點作爲一個有趣的練習留給讀者。）