創建不同路線的圖

Question

問題我有一個二進制圖像，可遍歷和阻塞的單元格。在此地圖上設定興趣點（POI）。我的目標是從這些POI中創建一個尊重障礙（見圖像）的圖表，它代表所有可能的和真正獨特的路徑。如果兩條路徑不能合併爲一條路徑，那麼兩條路徑是完全不同的。例如。如果圖片1中的建築物的外部可通行，則建築物周圍的路徑不能與穿過建築物的通道合併。

研究之我已經看過迷宮求解器和各種最短路徑尋找算法（如A *，西塔*，披*），雖然他們會爲這個問題他們只搜索有用爲兩點之間的路徑，並且不考慮已經建立的路線。

最佳猜測我正在考慮使用Phi *來搜索所有可能的路線，然後使用魔法（想法？）合併，但這不會給我真正獨特的選擇。

有人可以幫忙嗎？

PS：我使用C++，我不急於真正自己做這一點，所以如果有這已經這樣做了一個庫... :)

Answer 1

我發現（並決定使用）一併行細化算法（現在的詹燦）創建一個圖像骨架。這實際上是假設幾何形狀決定了常見路線，我認爲這很好。

通過使用Rutovitz交叉編號，我可以從生成的骨架中提取分叉和交叉。然後，我將確定我的興趣點（使用Bresenham算法）到提取的交叉點以將它們連接到圖的最短視線。

我希望這會幫助沿途的人:)