查找像素和像素組之間最小距離的算法

Question

我需要算法（最好在C++中，雖然僞代碼也可以），以在與一個特定像素具有最小距離的像素組中找到一組。

距離被定義爲組的每個像素到特定像素的距離的總和，而每個距離等於| x | + | y |座標。

如果它不夠清楚，我會盡力澄清你

謝謝

Answer 1

更新

此溶液計算的幾何（歐幾里德）的第一距離草案當questian稱爲Manhattan distances

這使得簡單優化。

1. 對於每組像素，選擇一個像素作爲主像素。哪一個並不重要。

2. 對於組中的每個其他像素，計算主像素的偏移量（x和y）。與曼哈頓距離不同，請保留此偏移的符號。

3. 將所有偏移量（包括x和y偏移量）合計爲一個數字，稱爲total_offsets。

4. 當您需要與指定像素的距離時，計算主像素的（曼哈頓）距離。將其乘以像素的數量並添加total_offsets以獲得曼哈頓總距離。

步驟1-3只需要對每組進行一次，然後根據需要執行步驟4。

例如

Area A consists of 4 pixels: (8, 8), (8, 9), (9, 8) and (9, 9). 

    Declare (8, 9) as primary pixel. Offsets are 
     (8, 9) --> (8, 8) = (0, -1) 
     (8, 9) --> (9, 8) = (1, -1) 
     (8, 9) --> (9, 9) = (1, 0) 
    total_offset = 0 + -1 + 1 + -1 + 1 + 0 
       = 0 
    num_pixels = 4 

To compute Manhattan distance from pixel (2, 4) 

    distance to primary pixel 
    (2, 4) --> (8, 9) = (6, 5) 
        = 11 
    dist * num_pixels + total_offsets = 11 * 4 + 0 
            = 44 

要檢查這一點，我們可以計算它的很長的路要走：

 (2, 4) --> (8, 8) = (6, 4) 
     (2, 4) --> (8, 9) = (6, 5) 
     (2, 4) --> (9, 8) = (7, 4) 
     (2, 4) --> (9, 9) = (7, 5) 

    distance = 6 + 4 + 6 + 5 + 7 + 4 + 7 + 5 
      = 44 

Answer 2

這聽起來像你已經知道如何計算距離。

對你來說for循環太慢了嗎？你的循環是N^2嗎？

如果是這樣，你可以看看使用BSP或Quadtree。我看到的唯一問題是您正在嘗試進行接近測試，其中大部分都是爲碰撞測試而設計的。它可能仍然可以讓你更快地消除一組組。

某些肯定會起作用的東西（儘管它在降低計算次數方面的有效性很大程度上取決於你的羣體的分佈情況）是簡單地將世界分成均勻間隔，稀疏的網格。如果一個組落入網格的多個部分，只需將其添加到兩個網格條目。在運行比較時，選擇最近的網格條目，並僅對該網格條目中的組運行點到組的算法。

Answer 3

以下是一個簡化示例。你需要一個函數「int distance（Point p1，Point p2）」來計算距離（使用任何算法）。

Point pxTest = ... // the single pixel to use for distance checking 
List<Point> pxGroup = ... // the group of pixels to check 

Point pxMin = null; // the pixel with the minimum distance 
int iMin = int.MAX; // the minimum distance so far 

foreach(Point pxOther in pxGroup) 
    if(iMin > distance(pxTest, pxOther)) 
    { 
     iMin = distance(pxTest, pxOther); // this could be cached in the line before as well to save this call 
     pxMin = pxOther; 
    } 

// now pxMin will include the closest point, iMin the distance