algorithm - 优化计算两个边界之间的距离

Question

我有一张位图世界地图，其中每个国家都以独特的颜色绘制。加载 map 后，我已将每个国家/地区的所有边界像素存储在一个数组中。

接下来我计算两个县(A 和 B)之间的距离。为此，我遍历 A 的边界数组中的每个像素并计算它与 B 的边界数组中的每个像素之间的距离。找到最短距离后，我将其存储在查找表中。

为了优化这个我有:

• 预先过滤掉所有直接邻居
• 当试图找到两个像素之间的最短距离时，我只比较平方距离(只有当我找到最接近的像素时，我才使用平方根计算实际距离)。
• 存储距离时，我为 A->B 和 B->A 都存储它，这样 B 将只计算 C 到 Z 的距离，C 只计算 D 到 Z 的距离，等等。

对于大 map ，这仍然需要相当多的时间，那么我可以做任何其他优化吗？

Answer 1

将边界像素数据存储在四叉树或其他利用实际几何结构的层次结构中(可能在三角树中)。您将计算包含边界像素的 log2(N)*log2(N)/2 个区域的最小/最大距离范围，而不是计算 N*N/2 像素的真实距离，排除大量不可能的候选对象，然后细化到下一个级别。

在样本 A 中，有 12 个方 block 要与样本 B 的 4 个候选方 block 进行比较，可能导致 4*5 个下一级候选方 block (所有 B 方 block 和 A 中的 5 个最近区域)。