在非退化梯形划分中寻找全局最短路径

Question

在非退化梯形划分中寻找全局最短路径

6

我正在寻找一种高效算法，用于在具有多边形障碍物的二维空间中找到两点之间的全局最短路径。源数据以非退化垂直梯形剖分的形式存在，最多包括10^4个梯形（非退化意味着每个梯形的下侧和上侧最多各有2个相邻梯形）。在梯形剖分上运行最短路径算法，然后使用漏斗算法不能保证找到全局最短路径。计算角点顶点的可视图可能有效，但我怀疑这可能会使用太多内存，因为该算法的要求是它可以频繁地使用（每秒约100次），并且在具有多个（最多700个）地图的服务器上使用，但如果您认为这不是问题，请随便指正！为了让您了解数据的外观，我上传了一个小地图的三角剖分可视化，您可以单击图像查看它作为SVG。

.

- xDD

最短路径由直线段组成，从边界点到边界点（除非起点和终点不是边界点的情况下）。因此，所有边界点的可见图应该给出最短路径。 - Andre Holzner

是的，我在问题中考虑了这一点，但我觉得这将需要相当大量的内存。 - xDD

我开始明白了...使用10^4个梯形，大约有210^4个点（每个点可以用16位整数表示，即2个字节），最坏情况下会导致410^8条边，这意味着仅一个700张地图就需要800兆字节的存储空间... - Andre Holzner

另一方面，能见度图上存在一些永远不会被使用的边，例如从某些区域的一个边界到另一个相对的边界（需要更好地定义...）。 - Andre Holzner

1个回答

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Himadri Choudhury · Accepted Answer

如果您创建了一个图形，其中：

1）顶点是梯形的所有顶点以及源点和目标点。

2）如果这些顶点中的任意两个在彼此之间具有视线，并且边缘权重等于两个顶点之间的距离，则它们之间存在边缘。

那么该问题似乎完全类似于图形问题中两点之间的最短距离，其有许多众所周知的解决方法（例如Dijkstra's Algorithm）。