C實現翼緣結構？

Question

我正在實現一種算法，我需要操縱網格，快速添加和刪除邊緣，並以CCW或CW順序快速遍歷與頂點相鄰的邊緣迭代。

翼緣結構用於描述我正在使用的算法，但是我找不到關於如何在這個數據結構上執行這些操作的簡明描述。

Answer 1

我已經在大學瞭解了它，但那是前一陣子。

爲了迴應這個問題，我也在網上搜索了任何好的文檔，發現沒有那麼好，但是我們可以在這裏通過CCW和CW順序以及插入/刪除的快速示例。 看一看這個表格和圖形：此頁面 ：

http://www.cs.mtu.edu/~shene/COURSES/cs3621/NOTES/model/winged-e.html

表給出了僅一個邊緣a的條目，在一個真正的表，你有此行的每一個角落。你可以看到你得到的：

• 左前身，
• 左接班人，
• 右前身，
• 權繼任

，但來這裏的關鍵點：它給了他們相對到的方向的邊緣是X->Y，在這種情況下，以及它是否正確穿越(e->a->c)。

所以對於通過圖形的CW順序這很容易閱讀：邊緣a左邊有右繼承者c然後你看看行c邊緣。 OK，這張表很容易讀CW順序遍歷;對於CCW來說，你不得不認爲「當我向後走這條邊時，我從哪個邊緣出來」。實際上，在CCW順序中，通過取左邊遍歷前導符b得到下一個邊，並以相同的方式繼續處理邊b的行條目。

現在插入和刪除：很明顯，你不能只刪除邊緣，並認爲該圖形仍然只包含三角形;在刪除期間，您必須加入兩個頂點，例如圖中的X和Y。要做到這一點，你首先必須確保邊緣a被引用的任何地方 - 我們必須修復該引用。

那麼a哪裏可以提及？只有在邊緣b,c,d and e（所有其他邊緣距離太遠以知道a）加上頂點 - >邊緣表中（如果有的話）（但在本例中只考慮邊緣表）。

作爲我們如何修復邊緣的一個例子，我們來看看c。像a,c有一個左右前和後繼（如此4個邊），其中之一是a？如果沒有檢查，我們無法知道，因爲c的表項可以在其開始或結束節點中具有節點Y。所以我們要檢查哪一個是，假設我們發現c具有Ÿ在其啓動的節點，我們就必須檢查a是否c's正確的前身（這是和我們通過觀察c's入境找出和它比較a），或者是否是正確的c's繼任。 「接班人？？」你可能會問？是的，因爲記住兩個「左移」列相對於向後移動邊緣。所以，現在我們已經發現，a是c's正確的前身，我們可以通過插入a's右前身修復的參考。繼續使用其他3條邊，並完成邊緣表。修復額外的Node->Vertices當然是微不足道的，只需查看X和Y的條目並在那裏刪除a即可。

添加邊緣是基本上這種修復4其他邊緣，但有點扭曲的反向。讓我們打電話，我們要分割Z（它將被分成X和Y）的節點。您必須小心，因爲您可以將d和e合併到一個節點中，或者將e和c（如果新邊緣是水平的而不是圖中的垂直a）組合在一起，那麼您必須謹慎分割它！你首先要找出它們之間的2個邊即將成爲X和它們之間的Y 2個邊的新的邊緣添加：你剛纔選擇哪個邊緣應一個節點和其他節點上：在這個例如圖形：選擇您想要b，c和2個邊向北它們之間的一個節點上，它遵循的其他邊緣的其他節點將成爲X上。然後通過矢量減法找到新邊緣a必須位於b和c之間，而不是在c和北邊的兩條邊之一之間。向量減法是新的X的期望位置減去Y的期望位置。