我想在图中找到最近的边。考虑以下示例:
图 1:黄色: 顶点，黑色: 边，蓝色: 查询点
一般信息: 该图包含大约 1000 万个顶点 和大约 1500 万个边。每个顶点都有坐标。边由两个相邻的顶点定义。
最简单的解决方案: 我可以简单地计算从查询点到图中所有其他边的距离，但这会非常慢。
思路与难点: 我的想法是使用一些空间索引来加速查询。我已经实现了一个 kd-tree 来找到最近的顶点。但如图 1 所示，入射到最近顶点的边不一定最接近查询点。我会得到边缘 3-4 而不是更近的边缘 7-8。
问题: 是否有一种算法可以找到图中最近的边？
最佳答案
一个非常简单的解决方案(但可能不是复杂度最低的解决方案)是使用 quad tree基于边界框的所有边缘。然后，您只需提取离查询点最近的边集并迭代它们以找到最近的边。
四叉树返回的提取边集应该比原来的 1500 万条边小很多倍，因此迭代的成本要低得多。
四叉树是一种比 R 树更简单的数据结构。它相当普遍，在许多环境中应该很容易获得。例如，在 Java 中 JTS Topology Suite有一个结构 QuadTree 可以很容易地包装来执行这个任务。
关于algorithm - 在图中找到最近的边，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/19892564/