我正在寻找一种高效算法,用于在具有多边形障碍物的二维空间中找到两点之间的全局最短路径。源数据以非退化垂直梯形剖分的形式存在,最多包括10^4个梯形(非退化意味着每个梯形的下侧和上侧最多各有2个相邻梯形)。在梯形剖分上运行最短路径算法,然后使用漏斗算法不能保证找到全局最短路径。计算角点顶点的可视图可能有效,但我怀疑这可能会使用太多内存,因为该算法的要求是它可以频繁地使用(每秒约100次),并且在具有多个(最多700个)地图的服务器上使用,但如果您认为这不是问题,请随便指正!为了让您了解数据的外观,我上传了一个小地图的三角剖分可视化,您可以单击图像查看它作为SVG。 .
如果您创建了一个图形,其中:1)顶点是梯形的所有顶点以及源点和目标点。2)如果这些顶点中的任意两个在彼此之间具有视线,并且边缘权重等于两个顶点之间的距离,则它们之间存在边缘。那么该问题似乎完全类似于图形问题中两点之间的最短距离,其有许多众所周知的解决方法(例如Dijkstra's Algorithm)。