指定为XY坐标的点之间的最短路径距离

Question

我目前正在从事一个项目，该项目的向量包含大约800点的X和Y坐标。这些点代表线的电网。我的目标是计算沿着包含电线的XY坐标的向量所给出的路径可以位于或不能位于A点和B点之间的最短距离路径。

我已经读过有关Dijkstra算法的信息，但是由于我对它不甚了解，因此我不确定是否应该朝这个方向发展。如果能收到您的任何反馈或意见，可以指导我解决此问题，我将非常感谢。

Answer 1

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

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

一旦完成此操作，您就可以开始使用寻路算法（在这种情况下，A* 似乎比 Dijkstra 算法更好）。这只是一个标准实现，每个“成本”都是点之间的实际距离。（对于 A*，启发式是到终点的勾股距离）。

有关 A*（和其他算法）的优秀教程，您应该查看Amit 的页面

编辑，回复评论。

看来第一步是将一组线段转换为“点”。我将经历这个过程的方式是：

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 集合，因此我建议将其存储在二叉树结构（集合？）中。