查找像素和像素组之间最小距离的算法

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