在图中查找最近的边
use*_*412 16 algorithm geometry computational-geometry graph-algorithm
我想在图中找到最近的边.请考虑以下示例:
图1: 黄色:顶点,黑色:边缘,蓝色:查询点
一般信息: 该图包含大约1000万个顶点和大约1500万个边.每个顶点都有坐标.边缘由两个相邻顶点定义.
最简单的解决方案: 我可以简单地计算从查询点到图中每个其他边缘的距离,但这将非常慢.
想法和困难: 我的想法是使用一些空间索引来加速查询.我已经实现了一个kd树来找到最近的顶点.但是如图1所示,入射到最近顶点的边缘不一定最接近查询点.我会得到边缘3-4而不是更近的边缘7-8.
问题: 是否有算法在图中找到最近的边？
您可以计算 voronoi 图并对每个 voronoi 单元格运行查询。您可以对 voronoi 图进行细分以获得更好的结果。您可以结合度量和 voronoi 图： http: //www.cc.gatech.edu/~phlosoft/voronoi/
- PSLG 段的 Voronoi 图非常难以计算，会导致各种数值精度问题。它也不是一种适合高效点位置查询的结构，因此仍然需要额外的空间剔除结构。我同意这是“正确的解决方案”，但它不太可能是最实用的解决方案。 (2认同)