c++ - 以 X-Y 坐标给出的点之间的最短路径距离

Question

我目前正在开展一个项目，该项目的 vector 包含大约 800 个点的 X 和 Y 坐标。这些点代表电力线网络。我的目标是计算 A 点和 B 点之间的最短距离路径，该路径可以位于也可以不位于由包含电线 X-Y 坐标的 vector 给出的路径上。

我读过有关 Dijkstra 算法的资料，但由于我不太熟悉它，所以我不确定是否应该朝那个方向发展。如果我能从您那里得到任何可以指导我解决这个问题的反馈或意见，我将非常感激。

Answer 1

任何寻路算法都依赖于路径，点是没有意义的。您现在拥有的是“航路点”列表。但是你还没有解释这些点是如何连接的。例如，如果任何一个点都相互连接，那么最短距离就是 A 和 B 之间的毕达哥拉斯距离。-我也不确定你所说的电线的 X-Y 坐标是什么意思，这样的“线”总是有开始和结束位置吗？

所以第一步不仅要为每个点添加 x,y 坐标，还要添加可连接点的列表。

完成此操作后，您就可以开始使用寻路算法(在这种情况下，A* 似乎比 Dijkstra 的更好)。它只是一个标准实现，每个“成本”是一个点之间的实际距离。 (对于 A*，启发式将是到终点的毕达哥拉斯距离)。

有关 A*(和其他算法)的优秀教程，您应该查看 Amit's pages

编辑，回复评论。

似乎第一步是将一组线段转换为“点”。我要经历的方式是:

collection AllPoints {containing Location & LinksToOtherPoints}
for each Segment
    get start/end Point of Segment
    if Point.Location is not in allPoints
        add Point to AllPoints
    add the other Point of Segment to LinksToOtherPoints

然后您将得到一个简单的列表，其中包含所有点以及它们之间的连接。由于您必须不断搜索 allPoints 集合，我建议将其存储在二叉树结构(集合？)中。