從肋骨點A到肋緣點B查找路徑

Question

我有一條看似棘手的挑戰，試圖從一個海港到另一個海港，制定出一條海路。最終目標是將其繪製在Google（或Bing）地圖上作爲折線。

的路徑需要：

• 是合理的，如船不能在陸地上（顯然）去
• 不能運行太靠近海岸線。船隻不能走近岸邊
• 不要太複雜。它將被繪製在谷歌地圖上，所以2000點多段線不會這樣做。
• 是最短的，而不是在以上三點

所以，我第一個想法是上獲得世界各地的海岸線數據的費用。這樣的東西可用here。不幸的是，它不完整。 OpenStreetMap顯示這些數據，加勒比羣島等海岸線缺失。

我也想過地理編碼（沒有足夠的可靠再加上我將通過數千燒試圖繪製路線的請求）

我的下一個想法就是以某種方式使用谷歌地圖和測試點是否藍色或不。一個很好的.NET Mapping組件，允許我通過創建一個它渲染和測試像素顏色的位圖來實現這一點。

第一個問題是這個命中測試的準確性只與我測試的圖像的分辨率圖像一樣好。對於彼此靠得很近的港口來說，這對於更遠的港口來說很好，準確度會受到影響。

第二個問題，假設我使用某種'藍色像素測試'的方法，是什麼算法適合尋找路線。 A* algorithm看起來很有希望，但我不知道如何推動從出口到海岸附近的路徑。也不知道如何降低折線的複雜性。

所以... 任何輸入：想法，想法，鏈接，示例代碼等將受到歡迎。謝謝。

（我要補充一點，這是一個旅遊網站，準確度不是太重要，我不是導演運輸或任何東西）

Answer 1

問題二，假設我用某種「藍色像素的測試'的方法，是什麼算法適合尋找路線。 A *算法看起來很有前途，但我不確定如何將路徑從存在推向靠近海岸。也不知道如何降低折線的複雜性。

首先創建世界的二元海圖像（白：海，黑：不是海），然後侵蝕圖像。侵蝕後的所有白點都可以通航。當然，忽視奇怪的一兩個沙洲。

正如你所猜測的，這種方法揭示了你尋路的一個核心問題：大多數船隻必須靠近陸地才能到達港口，違反了導航規則。然而，這可以通過在與特定港口相鄰的最近通航海上點開始導航來解決。

Answer 2

爲了簡化你從例如*搜索，你可以使用像Douglas-Peucker這樣的算法。另見參考文獻列表：http://maven.smith.edu/~orourke/TOPP/P24.html。

另一種想法：應用A *的常用方法是將每個像素視爲可能的狀態（位置），但沒有理由不能使用像素的一個子集作爲可能的狀態。如果你使得開始和結束點附近的狀態密度較高，遠離任一端點的狀態密度較低，那麼你將自動獲得以短而精確的運動開始和結束的路徑，但在中間有很長的直線段（例如，穿越太平洋時）。如果你這樣做，你可能還想增加靠近陸地的位置密度。

另一種可能的A *調整：您可以將「當前方向」納入狀態，並懲罰導致方向改變的移動。這往往會在你的路上產生長長的直線。這會使你的狀態空間乘以8，但這可能是可以忍受的。由於您只會增加解決方案的成本，因此您通常使用的直線到目標啓發式方法對於這種新的成本函數仍然可以接受，因此不會出現任何複雜情況。

Answer 3

谷歌爲「歐幾里得最短路徑」。維基百科也有一些信息

「歐幾里德最短路徑問題是計算幾何中的一個問題：給定一組歐幾里德空間中的多面障礙物，以及兩點，找到點之間的最短路徑，障礙「。

http://en.wikipedia.org/wiki/Euclidean_shortest_path

Answer 4

如果我是你，我會選擇一個圖形理論方法。你唯一的問題是收集數據庫的邊緣。如果你有他們，你可以用A *或Dijkstra的算法來計劃最短路線。 反正，如果我假設它是正確的，你需要類似於(Searoutefinder)的東西吧？祝你好運！

Answer 5

高分辨率的海岸線可以在網站上找到從NOAA。

爲了解決您的問題，您還可以採取更簡單的方式，並通過AtoBviaC詢問航運路線web服務的預算，並預先計算所有預期航線，但這可能對您的需求來說過於昂貴。