我想在图中找到最近的边。考虑以下示例：
图 1： 黄色：顶点，黑色：边，蓝色：查询点
一般信息： 该图包含大约1000 万个顶点和大约1500 万条边。每个顶点都有坐标。边由两个相邻的顶点定义。
最简单的解决方案： 我可以简单地计算从查询点到图中所有其他边的距离，但这会非常慢。
思路和难点： 我的思路是使用一些空间索引来加速查询。我已经实现了一个 kd-tree 来找到最近的顶点。但如图 1 所示，入射到最近顶点的边不一定是离查询点最近的。我会得到边缘3-4而不是更近的边缘7-8。
问题： 有没有一种算法可以在图中找到最近的边？
一个非常简单的解决方案（但可能不是复杂度最低的解决方案）是根据边界框对所有边缘使用四叉树。然后，您只需提取最接近查询点的边集并遍历它们以找到最近的边。
四叉树返回的提取边集应该比原来的 1500 万条边小很多，因此迭代的成本要低得多。
四叉树是比 R 树更简单的数据结构。它相当普遍，应该在许多环境中都可以使用。例如，在 Java 中，JTS Topology Suite有一个结构QuadTree，可以很容易地封装以执行此任务。
有一些空间查询结构适用于点以外的其他类型的数据。最通用的是“R-tree”结构（及其许多变体），它允许您存储线段的边界矩形。然后，您可以从查询点向外搜索，检查边界矩形中的线段，并在最近的剩余矩形比目前遇到的最近线更远时停止。当有许多长线段重叠时，这可能会导致性能不佳，但是对于您似乎在这里的 PSLG，这不应该发生。
另一种选择是使用线段来定义 BSP 树，并从您的点向外扫描以找到所有“可见”线。如果您的观点可以看到许多边缘，这反过来又会出现问题。
没有证明：
你从一个受约束的 Delaunay Triangulation开始，这是一个考虑到现有边的三角剖分。例如CGAL或Triangle可以做到这一点。对于每个查询点，您确定它属于哪个三角形。然后你只需要检查接触那个三角形角落的边缘。
我认为这在大多数情况下应该有效，但肯定有一些极端情况会失败，例如当有许多顶点根本没有任何边时，所以至少你必须删除那些空顶点。
您可以计算 voronoi 图并在每个 voronoi 单元上运行查询。您可以细分 voronoi 图以获得更好的结果。您可以结合公制和 voronoi 图：http ://www.cc.gatech.edu/~phlosoft/voronoi/
您可以在长边中插入额外的顶点以获得基于最近顶点的近似值..