c++ - 寻找像素和像素组之间最小距离的算法

Question

我需要算法(最好是在 c++ 中，尽管伪代码也可以)在到某个特定像素的距离最短的像素组中找到一组。

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

如果还不够清楚，我会尽力向你解释

谢谢

Answer 1

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

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

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

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