我正在寻找一种有效的算法，在具有多边形障碍物的二维空间中找到两点之间的全局最短路径 .
源数据是非简并垂直梯形的形式，由最多10 ^ 4个梯形组成（非简并意味着每个梯形的下侧和上侧各有至多2个相邻的梯形） .
在梯形本身上运行最短路径算法然后使用漏斗算法并不能保证找到全局最短路径 .
计算角顶点的可见性图可能会起作用，但我怀疑这可能会占用太多内存，因为对算法的要求是它可以在具有多个（最多700个）的服务器上频繁使用（大约每秒100次） ）在内存中映射，但如果您认为这不是问题，请随时纠正我！
为了可视化数据的样子，我上传了一个小 Map 的三角测量，您可以单击该图像将其视为SVG .
.
1 回答
如果您使用创建图表
1）除了源点和目的点之外，梯形的所有顶点处的顶点 .
2）如果它们是相对于彼此的视线并且边缘权重等于2个顶点之间的距离，则这些顶点中的任何两个之间的边缘 .
那么这个问题看起来就像是图形问题中2点之间的最短距离，它有许多众所周知的解决方案（Dijkstra's Algorithm等）