在假定停留在「道路」的情況下尋找連接兩點的最短路徑？

我搜索以下問題的名稱（以及後面的算法;））：找到從點z0到澤的最短路徑，例如路徑停留在「道路」上。下面的插圖顯示它更好。道路由兩個向量X =（x1，...，xk）和Y =（y1，...，yn）定義。我們假設問題並不棘手（即路徑X，Y不交叉，初始/終點在「道路上」等）。我們想要找到紅線（定義爲矢量）Z是連接z0和zend並僅通過道路的最短路徑。算法不需要很快。非常感謝任何提示！在假定停留在「道路」的情況下尋找連接兩點的最短路徑？

enter image description here

UPDATE：這句話後，我改變了形象，因爲它顯示出錯誤的解決辦法...：/

來源

2014-01-08 stymek

非常感謝您的評論！解決方案是錯誤的。我糾正了它。 – stymek

所繪製的方式，你的道路單調多邊形（也就是說，當你直接面向北方時，總是有Y在你的左邊，而X在你的右邊）。一旦你對多邊形進行了三角剖分，就有一種專門用於在單調三角測量中找到最短路徑的算法，稱爲「漏斗算法」。

對於單調的三角測量，Mark de Berg的計算幾何中的描述很好，但是失敗了，http://www.cs.ucf.edu/courses/cot5520/Triangul_monotone.ppt看起來不錯。對於漏斗算法，請嘗試here。

來源

2014-01-08 10:40:18 Sneftel

在您提供的第二個鏈接中複製「理論」中的一些內容可能會有所幫助，所以答案會更獨立一些（更少依賴於鏈接）。 – Dukeling

通常我會..但網絡已經有太多的半完整的漏斗算法的描述，並且有足夠完整的描述，我並不太擔心鏈接腐爛。 – Sneftel

我問了[一個Meta問題]（http://meta.stackexchange.com/a/212924/206447）關於不久以前非常相似的事情。普遍的共識似乎是，你仍然應該包括一個簡短的概述。 – Dukeling

-1

也許這是錯誤的答案，但我假設x和y座標是道路的輪廓。如果是這樣，爲什麼不能做到以下幾點：

畫線的道路（分流量）的中間，
假設用戶在駕駛右側（或離開英國，澳大利亞或日本）。
假設一條線路，然後在右側中間畫一條線。
這條線將是沿着道路行駛的距離。

如果這是一條道路，並且您在示例中看到紅線，則司機有時處於緊急車道或遏制路線中，其他時間處於迎面而來的交通狀況。

來源

2014-01-09 22:29:47

如果我瞭解您的解決方案，它將定義一條路徑，但不是最短路徑。 – stymek

如果我正確地理解了這個問題，最短路徑會將您帶到其他車道或路邊。如果這真的是一條道路，那麼該算法不應該模型化一輛汽車沿着正確的方向沿着一條車道行駛嗎？ –

問題具體是要求最短路徑。根據與問題中陳述的內容直接相反的假設，回答問題通常不是明智之舉。如果這個問題看起來矛盾，最好先在評論中澄清一下。另外請注意，「道路」在問題中多次用引號引起，這意味着它可能不是指實際的道路。 – Dukeling

在假定停留在「道路」的情況下尋找連接兩點的最短路徑？

回答

相關問題