1

我需要算法（最好在 c++ 中，虽然伪代码也可以）来在与一个特定像素具有最小距离的像素组中找到一组。

距离定义为组中每个像素到特定像素的距离之和，而每个距离等于 |x|+|y| 坐标。

如果它不够清楚，我会尝试澄清你

谢谢

4

3 回答 3

3

听起来您已经知道如何计算距离。

for循环对你来说太慢了吗？你的循环会是 N^2 吗？

如果是这样，您可能会考虑使用BSP或Quadtree。我看到的唯一麻烦是您正在尝试进行接近测试，而这些测试主要是为碰撞测试而设计的。它可能仍然允许您更快地消除组集。

肯定会起作用的东西（尽管它在降低计算数量方面的有效性高度依赖于组的分布）是将世界简单地分割成一个均匀分布的、人口稀少的网格。如果一个组属于网格的多个部分，只需将其添加到两个网格条目中。当您运行比较时，您选择最近的网格条目，并且仅在该网格条目中的组上运行您的点对组算法。

于 2011-03-25T21:16:26.390 回答
2

更新

当提问者提到曼哈顿距离时，该解决方案的初稿计算了几何（欧几里得）距离

这使得优化更简单。

  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
于 2011-03-25T22:44:38.330 回答
1

下面是一个简化的例子。您需要一个函数“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
于 2011-03-25T21:18:31.070 回答