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

Question

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

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

中

为了优化这个我有：

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

对于大地图，这仍然需要很多时间，所以我可以做其他优化吗？

Answer 1

考虑不计算 A 和 B 的每个像素边界之间的距离，而是假设每 10 个像素边界之间的距离。这将为您提供粗略的解决方案。如果精度不够满足你的目的，你可以通过更多的比较使它更准确。

另一种方法可能是引入新的边界数据结构模型。不是将其存储为每个点，而是 'characteristic' 点

的集合

Answer 2

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

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