最短路徑/僞代碼

Question

我有一個多邊形（在PHP），通過X，Y點的數組來表示。我希望能夠找到點A和點B.在實際應用中的多邊形，我有一個任意區域，定義爲一個簡單的多邊形內部的最短路徑，我想知道通過的距離（例如，把它作爲代表一個多邊形一條線索 - 我想估計線索的時間長短）。

尋找僞代碼或者從哪裏開始的一些技巧。除了一些關於三角測量和漏斗算法的難以理解的論文之外，我瀏覽互聯網似乎並不走運。

Answer 1

谷歌搜索最短路徑通過多邊形變成了很多有用的鏈接。一個算法的一個很好的描述是found here（完成一個applet動畫演示算法）。許多算法是針對允許在多邊形中出現空洞的更復雜的問題—。對於簡單的多邊形，它們可以不加修改地使用。 （其實，你的問題可以被認爲是通過一般多邊形尋找路徑的特殊情況，其中所有的洞（障礙物）與邊緣共享一個點。）

我認爲最好的方法是A *搜索多邊形頂點的可見性圖形加上開始點和結束點（如果它們不是頂點）所定義的空間。

Answer 2

一個簡單的算法使用的事實是，路徑必須從反射頂點到反射頂點（除了第一步和最後一步）。因此，使用所有反射頂點和起點和終點來繪製圖形，並使用標準最短路徑算法找到最短路徑。我有相當短的Mathematica代碼，可以完成所有這些工作，並且很快將在網站的演示demo.wolfram.com上發佈演示。如果你想要的代碼給我一個消息。