查找多邊形中花費最少的路徑

我正在嘗試在多邊形內部查找其路徑，以考慮其成本。查找多邊形中花費最少的路徑

在我的具體情況中，我有一個角色只應該比較直，也就是說，移動到北部，東部，南部或西部的角度應該不會超過幾度。

理想情況下，我會分配一個隨偏差而增加的成本。我認爲這是一個圖論相關的問題，但我不知道如何在多邊形中做到這一點...

圖中的紅色虛線路徑是常規算法產生的;綠色是關於我想要的。 編輯：我搞砸了一下這幅畫;澄清：紅色路徑是多邊形內最短路徑，我希望綠色路徑是角度約束下可能的最短路徑。

（爲了澄清，如果我的多邊形看起來像(1)，我希望的路徑是這樣(2)，不是單純的點之間的直線）

(1) ,-------------------+  (2) ,-------------------+ 
    /    (B) |   /    (B) | 
    /     |  /   / | 
+--+      | -> +--+    / | 
|      +-+  |    / +-+ 
| (A)     |  | (A)-------------+  | 
+-----------------------+  +-----------------------+

來源

2014-07-10 user1449556

A *可能適合您的角度限制 – sp2danny

是您的空間離散還是連續？ –

@VikramBhat它是連續的，並且作爲一組點/頂點或三角化出現 – user1449556

這實在是更多的評論，但我不能評論，因爲它需要50個聲望......奧托，我不認爲有滿意的答案問題，因爲它沒有很好的定義。但對於一個有趣的問題+1 :-)

給出紅色虛線的算法從您的路徑的起點和終點之間的直線開始（它不完全位於多邊形內）。然後，沿着直到你碰到一個角落，並將其作爲你的新起點。（請注意，您繪製的紅色虛線並不是最短的路徑。）現在，您的綠線基本上是紅線，用於替換您不喜歡的（錯誤的角度）棋子，但路徑較長，但由於某種原因更好（好角度）。這也是給你下面例子的「正確」答案。從（A）到（B）的直線開始，這是最短路徑，位於多邊形內部。現在用更有利的角度更換這條線。（這可能會迫使你在一般情況下需要轉多圈......）

只是有些想法。

來源

2014-07-10 11:02:26 1k5

再次我不能評論其他答案，所以我會評論我自己的......而如果你的情況比你所描述的情況更復雜（如你的多邊形內所有形狀的障礙物），John Doe的第一個答案是非常好的。對於一個簡單的多邊形，John Doe的第二個答案基本上和我的一樣，除了他更喜歡採用隨機路徑而不是我的確定性方法:-) – 1k5

感謝您的輸入！「不是很好定義」是什麼意思？ – user1449556

這是數學家代表你說的並不是非常精確的指定你正在尋找的路徑類型。特別是我有點困惑：（1）紅色路徑實際上並不是最短的，這就是我認爲你在尋找的東西;（2）綠色路徑的水平部分延伸到左邊的角落，這使得它比必要的稍長。是否有一個原因？ – 1k5

運行Rapidly exploring random tree algorithm但限制探測方向在平行於軸線的幾個方向內，並且通過選擇較大的增量距離來保持轉彎數量較低。基本上根據你的意願添加任何啓發式。

Rapidly-Exploring Random Trees: A New Tool for Path Planning是關於快速探索隨機樹木的開創性論文。

來源

2014-07-10 11:15:38

我會在這裏添加另一個答案，因爲它與我的另一個有很大的不同。從常規路徑尋找算法的結果開始，運行隨機優化以使適應度函數最大化，該適應度函數通過添加頂點，移動頂點並刪除頂點來描述路徑的「相對平直度」（以及短度和其他度量，如果您願意的話）一條路徑，同時仍然保持路徑有效。

常見的隨機優化方法包括Simulated Annealing。

來源

2014-07-10 11:19:51

查找多邊形中花費最少的路徑

回答

相關問題