有牆的地圖上的有效路徑生成算法

Question

我需要一個高效的算法來解決以下問題。有一個建築物的2D地圖。該建築有一個多邊形的外牆，每個內牆都是一條線段。網格放置在地圖上。建築物內的一個網格點上有一個機器人。機器人在網格點上移動。已知機器人的最大速度（每秒格點數）。我必須得到一組所有的網格點，機器人可以在下一秒內到達，而不是穿過牆壁，不超過最大速度。

目前我只是用中間的一個機器人（矩形的一邊是2 * max_velocity * 1s）遍歷矩形中的所有點，並檢查機器人在移動到這個點時是否穿過牆。我存儲陣列中的牆。每堵牆都是一對端。

有沒有更快的方法來解決這個問題？

Answer 1

廣義沃羅諾伊圖也適用於尋路(Robot Path Planning Using Generalized Voronoi Diagrams)，因爲它是Delaunay三角剖分和最小生成樹的對偶。您可以簡單地刪除矩形內的點。