delphi - 计算邻域距离

Question

您将使用什么方法来计算距离，该距离表示在给定的 2D map 中从一个区域到另一个区域必须进行的“跳跃”次数？

我们以下面的 map 为例:

_{(来源:free.fr)}

计算的最终结果将是一个像这样的三角形:

  A B C D E F
A 
B 1
C 2 1
D 2 1 1
E . . . .
F 3 2 2 1 .

这意味着从 A 到 D，需要跳转 2 次。
然而，从任意位置到E，是不可能的，因为“间隙”太大，所以该值是“无穷大”，这里为了简化用点表示。

正如您在示例中看到的，多边形可能共享点，但大多数情况下它们只是靠在一起，因此应允许最大间隙以将两个多边形视为相邻。

这显然是一个简化的示例，但在实际情况中，我面临着大约 60000 个多边形，并且只对最大为 4 的跳跃值感兴趣。

作为输入数据，我将多边形顶点作为坐标数组，从中我已经知道如何计算质心。

我最初的方法是在白色背景 Canvas 上“绘制”多边形，每个多边形都有自己的颜色，然后在两个候选多边形质心之间走线。计算我遇到的颜色可以给我跳跃的次数。
然而，这并不真正可靠，因为它没有考虑凹形排列，即人们必须绕着“凹口”行走才能从一个多边形走到另一个多边形，正如从 A 到 F 时可以看到的那样。

我曾尝试寻找有关此主题的引用资料，但找不到任何引用资料，因为我很难弄清楚描述此类问题的正确术语。

我的目标语言是 Delphi XE2，但任何示例都将受到欢迎。

Answer 1

您可以为每个初始多边形创建具有较小偏移的膨胀多边形，然后检查与相邻(膨胀)多边形的交集。偏移对于补偿多边形之间的小间隙很有用。

膨胀和相交问题都可以通过 Clipper library 来解决.
潜在邻居问题的解决方案取决于实际情况 - 例如，简单的方法 - 将平面划分为正方形单元，并检查在同一单元和最近单元中具有顶点的邻居。

每对相交的多边形都会在(未加权、无向)图中给出一条边。你想找到所有长度 <=4 的路径 - 只需执行深度限制 BFS从每个顶点(多边形) - 假设图是稀疏的