假設我目前有一組可以被認為是“開”或“關”的單元格，類似于這張圖片（白色表示關閉，黑色表示開啟）
細胞
單元格基本上是大小 = 1 的正方形，每個角可以通過以下方式計算：
p0 = p
p1 = p (0, 1)
p2 = p (1, 1)
p3 = p (1, 0)
所以每個單元實際上是一個具有 4 個頂點的多邊形
我想生成一個有序的頂點串列，創建一個多邊形，其中所有單元格都組合在一起，洗掉內部和冗余頂點，如下所示：
分組的單元格
所以，我在嘗試解決這個問題時遇到的演算法只檢測頂點，它們檢測正確，實際上它的代碼非常簡單。它是這樣作業的：
foreach cell
foreach corner of the cell //each corner is a vertex of a square cell
if !vertex_list.contains(corner)
vertex_list.add(corner)
else
vertex_list.remove(corner)
endif
endfor
endfor
但是，它沒有對它們進行正確排序，如果我遍歷每個頂點，從它畫一條線到前一個頂點，它會產生一團糟
我如何創建一個演算法來生成一個排序的頂點串列來創建一個多邊形？
uj5u.com熱心網友回復：
您可以采用這種方法：
為每個頂點（角）創建節點物件。每個節點將具有（唯一的）x、y 坐標和對鄰居的四個參考：上、右、下、左。其中每一個要么參考另一個節點（指標），要么為空（當該方向沒有邊時）。例如，如果您有兩個相鄰的單元格，則此步驟將創建 6 個節點（不是 8 個，因為這些單元格共享 2 個頂點，并且應該為每個唯一頂點創建一個節點）。您將為這些節點創建一個哈希表（字典/映射），以它們的 x、y 坐標為鍵，以避免為同一個頂點創建多個節點。
找到最北的節點。這是起始節點。也將其命名為當前節點。
將當前方向設定為“右”
當當前節點在當前方向有一個鄰居時，請執行以下操作：
- 使該鄰居成為當前節點
- 將（現在）當前節點添加到解決方案中
- 逆時針方向改變方向，如果對了就補上。如果它起來了，讓它離開，......等等。
- 如果當前節點是起始節點，則結束演算法
由于當前節點現在在當前方向上沒有鄰居，所以順時針旋轉改變當前方向，如果它是正確的，就讓它下來。如果它被關閉，讓它離開，......等等。
從第 4 步開始重復。
這假設所有單元都連接在一起，并且形成的形狀沒有完全包圍的孔。
轉載請註明出處，本文鏈接：https://www.uj5u.com/net/482227.html