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

Question

我正在实现一个算法，在这个算法中，我需要操纵网格，快速添加和删除边，并在CCW或CW顺序中与顶点相邻的边上快速迭代。

winged-edge结构用于描述我正在使用的算法，但我找不到任何关于如何在此数据结构上执行这些操作的简明描述。

Answer 1

我在大学里就知道了，但那是不久前的事了。

为了回答这个问题，我也在网上搜索过任何好的文档，没有找到好的文档，但我们可以在这里快速查看CCW和CW订单以及插入/删除的示例。请看下表和图表：

在此页面中：

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

表中只给出了一条边的条目a，在真实的表中，每条边都有这一行。你可以看到你得到了：

• 左前置、
• 左前置、
• 右前置、
• 右前置

但关键点来了:它给出了它们相对于边的方向，在本例中是X->Y，以及当它是右遍历(e->a->c)的时候。

因此，对于遍历图的CW顺序，这很容易读懂: edge a left有右后继者c，然后查看行中的边c。

好的，对于CW-order遍历，这个表很容易阅读；对于CCW，你必须思考“当我向后遍历这个边缘时，我来自哪个边缘”。实际上，您可以通过在本例中采用left-traverse-predecessor来获得CCW order中的下一个边，并以相同的方式继续边b的行条目。

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

那么，a可以参考到哪里呢？仅在边表中(所有其他边都太远而不知道a)加上顶点->边表(但在本例中我们只考虑边表)。

作为我们如何修复边缘的一个例子，让我们来看看c。像a一样，c有一个左右的前置和后置(所以有4个边)，其中哪一个是a？如果不进行检查，我们就无法知道这一点，因为c的表项可以在其起始节点或结束节点中包含节点Y。因此，我们必须检查它是哪一个，假设我们发现c的起始节点中有Y，然后我们必须检查a是否是c's右前导(它是，我们通过查看c's条目并将其与a进行比较来发现它)，或者它是否是c's右后继。“后继者？？”你可能会问？是的，因为请记住，这两个“左遍历”-columns是相对于向后走的边。所以，现在我们已经发现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和北边中的一条边之间。向量减法是新X的期望位置减去Y的期望位置。