計算兩個任意形狀之間的最小距離

我有兩個任意形狀。現在我想計算兩個形狀之間的最小距離。在這裏，我附着圖像計算兩個任意形狀之間的最小距離

所有的

先畫部分已完成。這些形狀是弧和線的組合。現在，當我要計算這些形狀之間的最小距離時，我正面臨着問題。使用GWT（java）html5畫布繪製這些形狀。

對於計算兩個形狀之間的最小距離我用下面的Java代碼，但我沒有得到任何優化的方式來做到這一點 -

private double calculateMinimumDistance(Coordinate[] coordinates_1, Coordinate[] coordinates_2) { 
    double minDistance = 100000; 
    double currentDistance = 0; 

    for(int i = 0; i < coordinates_1.length; ++i) { 
     for(int j = 0; j < coordinates_2.length; ++j) { 
     currentDistance = coordinates_1[i].distanceTo(coordinates_2[j]); 
     if(currentDistance < minDistance) { 
      minDistance = currentDistance; 
     } 
     } 
    } 

    return minDistance; 
}

coordinates_1包含形狀-1的點的集合。
coordinates_2包含形狀2的點的集合。

是否有任何優化的方式來計算兩個形狀之間的距離？這種形狀可以是任何地方和任何類型的形狀。

代替計算兩個設定點之間的最小距離，我們可以通過計算線之間的距離線或線電弧或電弧電弧做它在最優化的方式。通過這種方式，我們可以通過優化的方式計算出最小距離。

來源

2015-09-18 Shiladittya Chakraborty

準備你的數學，然後用Java編寫 –

你必須首先做出一些假設，比如你的程序將在什麼基礎上計算距離，例如。他們的位置，最重要的是你如何在程序中表現這些形狀。 – itwasntme

關於如何開始的第一個想法：定義你的形狀。 Java代碼中的形狀如何表示？如果你不能告訴Java代碼你的形狀，你會如何期待它做任何事情？ – Andreas

該想法是將形狀表示爲頂點列表。然後找到任意形狀之間的最小距離，我會實現基本算法來找出兩個凸形之間的距離。然後將任意形狀分成不相交的一組凸形，計算不同對之間的所有距離並獲得最小距離。

要計算兩個凸形之間的距離，只需遍歷頂點對的所有組合，就可以計算距離並取最小值。當然，這種方法將需要n^2操作，所以你可能需要優化它。您可以使用一些簡化的形狀：例如，將每個形狀表示爲8-10個基本點形狀，然後在每個形狀上找到最接近另一個形狀的邊，然後搜索邊的點內部。

來源

2015-09-18 08:33:58 Nyavro

將兩種形狀考慮爲平面上兩組不同的點。然後測量從第一組中的每個點到第二組中的每個點的距離。

爲此使用嵌套for循環，並使用座標幾何的距離公式測量距離。

只存儲最短距離，如果你想兩個點重合的距離。

來源

2015-09-18 09:31:14 CoderBrain

我遵循這個步驟，但由於多邊形包含很多點，所以它的執行速度很慢。那麼有沒有優化的方法來做到這一點？ –

您可以創建二維數組，也可以存儲點的圖像的哪一半。例如左半邊或右半邊。然後，您可以只比較第一張圖像右側的左側和右側圖像的左側。 – CoderBrain

我已經創建了一個2D二維數組，用於存儲兩個多邊形的所有點。但問題是如何取多邊形的一半點，因爲多邊形可以在任何地方。那麼如何得到這組點的恰好最接近的一半呢？ –

對於輪廓A和輪廓B中的每個點，使用距離公式計算斜邊：hypot = sqrt（xA-xB）^ 2 +（yA-yB）^ 2）...我正在解決同樣的問題問題爲一組N個輪廓，所以我會在完成時分享我的代碼。

來源

2015-09-24 20:32:15

我已經使用這個公式計算了兩個座標之間的距離。基本上我用兩個循環找到兩個多邊形之間的最小距離，但由於兩個多邊形有很多點，所以工作很慢。 –

出現同樣的問題：可行的臨時解決方案可能是使用對象的幾何中心。假設物體的長度「物體之間的距離，估計應該保持良好。 –

你有一些示例代碼嗎？ –

計算兩個任意形狀之間的最小距離

回答

相關問題