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。

好的，这个表对于CW-order遍历很容易阅读；对于CCW，您必须考虑“当我向后走这条边时，我来自哪个边”。实际上，在这种情况下，您可以通过采用左遍历前驱来获得 CCW 顺序中的下一条边，并以相同的方式b继续进行边的行条目。b

现在插入和删除：很明显，您不能只删除边并认为图形仍然只包含三角形；在删除过程中，您必须连接X两个顶点，例如Y在图形中。要做到这一点，您首先必须确保边缘a被引用的所有地方 - 我们必须修复该引用。

那么哪里可以a参考呢？仅在边缘中b,c,d and e（所有其他边缘都太远而无法知道a）加上顶点->边缘表（如果您有的话）（但在此示例中我们只考虑边缘表）。

作为我们如何修复边缘的示例，让我们看一下c. 像a，c有一个左右前和后继（所以 4 个边），其中哪一个是a？如果不检查，我们无法知道这一点，因为表条目c可以Y在其开始节点或结束节点中包含节点。所以我们必须检查它是哪一个，假设我们发现c它的开始节点中有 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和（例如，如果新边缘是水平的而不是图形中的垂直）！您首先必须找出即将成为的边的哪两条边之间以及新边的哪两条边之间添加：您只需选择哪些边应位于一个节点上，哪些应位于另一个节点上：在此示例图形中: 选择你想要的,eecaXYbc并且在一个节点上它们之间向北的 2 条边，因此其他边在另一个节点上，它将变为X。然后，您通过向量减法发现新边a必须在 b 和 c 之间，而不是在 c 和北方的 2 条边之一之间。向量减法是新X的期望位置减去期望的位置Y。