algorithm - 在图中找到最近的边

Question

我想在图中找到最近的边。考虑以下示例:

图 1:黄色: 顶点，黑色: 边，蓝色: 查询点

一般信息:该图包含大约 1000 万个顶点 和大约 1500 万个边。每个顶点都有坐标。边由两个相邻的顶点定义。

最简单的解决方案:我可以简单地计算从查询点到图中所有其他边的距离，但这会非常慢。

思路与难点:我的想法是使用一些空间索引来加速查询。我已经实现了一个 kd-tree 来找到最近的顶点。但如图 1 所示，入射到最近顶点的边不一定最接近查询点。我会得到边缘 3-4 而不是更近的边缘 7-8。

问题:是否有一种算法可以找到图中最近的边？

Answer 1

一个非常简单的解决方案(但可能不是复杂度最低的解决方案)是使用 quad tree基于边界框的所有边缘。然后，您只需提取离查询点最近的边集并迭代它们以找到最近的边。

四叉树返回的提取边集应该比原来的 1500 万条边小很多倍，因此迭代的成本要低得多。

四叉树是一种比 R 树更简单的数据结构。它相当普遍，在许多环境中应该很容易获得。例如，在 Java 中 JTS Topology Suite有一个结构 QuadTree 可以很容易地包装来执行这个任务。