c# - 适合由线集合定义的地图的寻路算法

Question

我有一组线。一条线由两个点定义。A Point 具有 (x,y) 坐标。有些线只在一个点与其他线相连。这组线定义了一个地图。您可以在下图中看到一个示例。现在让我们假设我想从任何线段上的一个点（不仅仅是一条线的端点）到另一条线上的另一个点。

背景：从一个点移动到另一个点时，我想沿途画一条线，所以最后只画经过的路径。将其视为路径的热图。我会使用什么算法？有没有我可以使用的库？

Answer 1

将图形表示为具有 xy 坐标的线集不适合路径查找算法，因此您应该从线段集构建正确的图形。我认为您可以使用这些公式： http: //en.wikipedia.org/wiki/Distance_from_a_point_to_a_line http://en.wikipedia.org/wiki/Line-line_intersection 来确定每个线段的相邻线段。两条线的每个交点都应转换为四条或三条线，以便它们仅通过端点连接。在构建每个节点代表一条线并且每个边代表线之间的连接的图形之后，您可以使用 Dijkstra 算法来查找任何一对节点（线）之间的最短路径： http ://en.wikipedia.org/wiki/Dijkstra%27s_algorithm

Answer 2

由于两点之间可能存在多条路径，因此无法确定问题。

如果您想要两点之间的最短路径，则必须进行 4 路计算：假设点 A 在线段 a1-a2 上，点 B 在线段 b1-b2 上。您使用 Dijstra 算法计算以下四个路径和距离：

a1 到 b1
a1 到 b2
a2 到 b1
a2 到 b2

现在，适当地增加或减少距离 A/B。例如，如果路径是这样的：

A -> a1 -> b2 -> B

那么这条路径的总实际距离是（A 到 a1）+（a1 到 b2）+（b2 到 B）。您需要计算上面列出的所有四种可能性的实际距离。取值最小的就是最短路径。然后你可以给它上色。

没有公共库可以进行此计算。我不得不手写一次。