用於簡化2D地圖的離線算法

Question

我有一個環境的多邊形2D地圖，我想簡化一些計劃測試的地圖。

例如，我想關閉機器人模型無法達到的區域，因爲通道太小。

第二個問題是當我有兩個段幾乎平行我想設置它們平行。

任何人都可以告訴我一些算法的名稱嗎？我知道我在哪裏搜索？

謝謝你的幫助。

猛男

Answer 1

第一項任務通常通過將Minkowski difference應用於您的地圖和機器人來解決。這意味着你知道你的機器人的配置文件。

對於第二個任務常見的方法是使用2D捕捉舍入。你可以在scholar.google.com找到關於該主題的大量論文。不過，查看Ramer–Douglas–Peucker algorithm也可能有助於減少曲線中的多個點。它無法幫助解決你的問題，但瞭解它的存在是有用的。

您的工作很可能與Motion Planning相關，所以我強烈建議您閱讀Computational Geometry by Kreweld, De Berg, Overmars and Schwarzkopf。這是計算幾何的經典之作。在那裏你可以找到很多關於可見性圖和運動計劃。

Answer 2

您可以使用地圖的三角網和旅遊網的邊緣的最短路線。

Answer 3

與米哈伊爾的回答類似，對於第一個問題，您可以將地圖多邊形轉換爲二進制圖像並應用考慮機器人大小的morphological dilation。然後，由窄路徑分開的區域將成爲二進制映像中的斷開組件。

另一種方法是將空間劃分爲網格，並根據某些地圖線是否穿過它們將單元格標記爲空或全部。然後根據機器人尺寸加厚邊界，並從機器人要尋找可行路徑的單元中尋找連接的組件。