相关疑难解决方法(0)

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

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

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

最简单的解决方案: 我可以简单地计算从查询点到图中每个其他边缘的距离,但这将非常慢.

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

问题: 是否有算法在图中找到最近的边？

我正在尝试scipy.spatial对Qhull的Delaunay三角测量的实现.

是否有可能以保留输入顶点定义的边的方式生成三角剖分？(编辑:即受约束的Delaunay三角剖分.)可以使用Python 的三角形包.

例如,在下图中,有几个三角形(蓝色)忽略由顶点定义的边缘(红色)的位置.有没有办法强制执行这些边缘,使它们在所有情况下都是三角测量结果的一部分？