一組瓷磚 - 計算大綱路徑

問題（僞） 如何查找一組瓷磚的輪廓？假設我們在x/y座標A [20,20]，B [20,30]和C [30,30]處有三個貼圖（這將形成一個簡單的L形）。這些點表示瓦片的中心。每個瓷磚有4個頂點：TL（左上），TR，BL（左下）和BR。這3個瓷磚共有8個獨特（不重疊）的頂點。一組瓷磚 - 計算大綱路徑

我們想要的紅色線（道路），由綠點定義（頂點）： http://img7.imageshack.us/img7/2469/lshapetiles.png

所需的解決方案算法的輸出應該是形成瓷磚的輪廓形狀，由路徑在這些頂點之外 - 以此順序： A TL，A TR，A BR，C TR，C BR，C BL，B BL，B TL（和可選的，A TL再次關閉）。看到紅線。

可能的解決方法（S） 一種選擇是遍歷所有的瓷磚，併爲每個瓦片檢查： +它有一個以上的鄰居？如果沒有，在TL和TR路徑 +它有一個鄰居在右邊？如果沒有，在TR和BR路徑 +它下面有一個鄰居嗎？如果沒有，在BL和BR路徑 +它的左邊是否有一個鄰居？如果不是，則在TL和BL處路徑

如果您僅將找到的頂點添加到路徑中（如果它們尚未添加），則您已成功收集路徑的唯一頂點。但是，它們可能是錯誤的順序。這是一個（問題）。

有人知道一個很好的解決方案（算法）嗎？

來源

2013-04-10 Karel de Boer

首先，構建一個數據結構來表示瓦片結構。

算法： 1找到左上角的點。 2從這一點開始，通過使用向上，向右，向下，向左的順序（在數據結構中，每個點包含這4個鏈接）迭代地找到下一個點，並返回初始點。

如果圖形包含分離的結構，請爲每個連接的組件運行上述算法。

來源

2013-04-10 15:08:39

這似乎是一個很好的方法。謝謝:) PS對於任何人嘗試這個;確保你從你的網格中刪除了關閉的點。在你開始邏輯之前，刪除被四個方塊包圍的點。今天晚些時候我會在這裏發佈一個僞解決方案。 Tnx天韻:) – 2013-04-18 09:02:19

僞解決方案。見：http://img825.imageshack.us/img825/2194/outlinepathfinding.png 1）我們希望這個tilegrid的輪廓，作爲路徑 2）找出所有頂點 3）拆下連接4瓦頂點彼此之間 4）從左上角開始;將它添加到你的路徑 5）現在做天雲說:)（當然，當它不在路徑上時，只添加頂點到你的路徑 GL。Tnx全部:) – 2013-04-18 09:15:37

你可以嘗試這樣的事情：

您反覆建立代表瓷磚，除了 - 當邊緣加倍小的變化的曲線圖，你將其刪除。

因此，您將第一個圖塊添加到圖G中，它的所有邊將被添加。對於下一個圖塊，將所有邊添加到G，但是如果它的任何邊與G中的邊重疊，則從G中刪除該邊。您對所有圖塊繼續此過程。

最後，你只剩下「外部」邊緣，所以你只需要遍歷你已經離開的路徑。

來源

2013-04-10 15:00:11 Bitwise

這將使我完全離開我：擁有路徑的所有邊（兩個頂點的組合），但是是以隨機順序。請注意，訂單很重要。或者我沒有看到你的解決方案是正確的？ – 2013-04-10 15:08:42

@KareldeBoer如果您正確地表示圖表，這應該不是問題，例如每個節點指向其相鄰節點。 – Bitwise 2013-04-10 15:29:29

一組瓷磚 - 計算大綱路徑

回答

相關問題