通过集合线定义的地图的合适寻路算法

Question

我有一组线。一条线由两个点定义。点有（x，y）坐标。 有些线路只能在一个点上与其他线路连接。这组线定义了一张地图。你可以在下面的图片中看到一个例子。现在让我们假设我想从任一行的一个点（不只是一行的终点）到另一行的另一个点。

背景：从一个点移动到另一个点时，我想在路上画一条线，所以最后只会绘制走过的路径。把它想象成路径的热图。我会用什么算法？有我可以使用的任何图书馆吗？

Answer 1

将图形表示为一组带有x-y cooridinates的线条不适合路径查找算法，因此您应该从一组线段中构建适当的图形。 我认为你可以使用这些公式： 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 - >乙

然后，对于该路径中的总的实际距离是（A至A1）+（a1至B2）+（ b2到B）。您需要计算上述所有四种可能性的实际距离。无论哪个值最小都是最短的路径。然后你可以为它着色。

这个计算没有公开的库文件。我必须用手写一次。