通過集合線定義的地圖的合適尋路算法

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）。您需要計算上述所有四種可能性的實際距離。無論哪個值最小都是最短的路徑。然後你可以爲它着色。

這個計算沒有公開的庫文件。我必須用手寫一次。