网格的翼边结构如何工作？

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.

好的,这个表很容易阅读CW顺序遍历; 对于CCW你必须思考"当我向后走这条边时,我从哪个边缘来".通过在这种情况下采用左移 - 前导,b并以b相同的方式继续边缘的行条目,有效地获得CCW顺序的下一个边缘.

现在插入和删除:显然你不能删除边缘并认为图形仍然只包含三角形; 在删除过程中,您必须连接两个顶点,例如X和Y图形.要做到这一点,首先必须确保在a引用边缘的任何地方,我们必须修复该引用.

那么哪里可以a参考？只有在边缘b,c,d and e(所有其他边缘都太远而无法知道a)加上vertex-> edge-table如果你有(但在这个例子中我们只考虑edge-table).

作为我们如何修复边缘的示例,我们来看看c.比如a,c有一个左右前置和后置(所以4个边缘),其中一个是a什么？我们无法知道没有检查,因为table-entry for c可以Y在其Start-node或End-Node中有节点.所以我们必须检查它是哪一个,让我们假设我们发现c在它的Start-Node 中有Y,然后我们必须检查它是否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的平面)!您首先必须找出即将添加的X两条边和Y新边的两条边之间:您只需选择哪一条边应位于一个节点上,哪一条位于另一个节点上:在此示例中为图形:选择你想要的b,c并在一个节点上选择它们之间的北边2个边缘,然后其他边缘位于另一个节点上X.然后通过向量减法找到新边a必须在b和c之间,而不是在c和北边的2个边之一之间.向量减法是新X的期望位置减去期望的位置Y.