寻找非退化梯形的全局最短路径
xDD*_*xDD 6 algorithm graph path-finding
我正在寻找一种有效的算法,该算法在具有多边形障碍物的二维空间中找到两点之间的全局最短路径.
源数据是非简并垂直梯形的形式,由最多10 ^ 4个梯形组成(非简并意味着每个梯形的下侧和上侧各自具有至多2个相邻的梯形).
在梯形本身上运行最短路径算法然后使用漏斗算法并不能保证找到全局最短路径.
计算角顶点的可见性图可能会起作用,但我怀疑这可能会占用太多内存,因为对算法的要求是它可以在具有多个(最多700个)的服务器上频繁使用(大约每秒100次) )在内存中映射,但如果您认为这不是问题,请随时纠正我!
为了可视化数据的样子,我上传了一张小地图的三角测量,你可以点击图像将其作为SVG查看.
.