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

发布于 2024-11-19 19:32:44 字数 126 浏览 3 评论 0原文

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

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

原文

分享到QQ

分享到微博

如果你对这篇内容有疑问，欢迎到本站社区发帖提问参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。

发布评论

需要登录才能够评论，你可以免费注册一个本站的账号。

忆梦 2024-11-26 19:32:44

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

为了回答这个问题，我也在网上搜索了任何好的文档，没有找到好的文档，但我们可以在此处查看 CCW 和 CW 顺序以及插入/删除的快速示例。
看看这个表格和图形：
在此处输入图像描述
从此页面：

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

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

左前驱，
左后继，
右前驱，
右后继，

但关键点来了：它给出了它们相对于边缘的方向，即X-> ;Y 在这种情况下，以及当它被右遍历时(e->a->c)。

因此，对于遍历图形的 CW 顺序，这很容易阅读：左边的边 a 具有右后继 c，然后查看边 a 的行代码>c。

好吧，这张表对于CW阶遍历来说很容易读懂；对于CCW，你必须思考“当我向后走这条边时，我是从哪边来的”。实际上，您可以通过在本例中采用左遍历前驱 b 来获得逆时针顺序的下一条边，并以相同的方式继续边 b 的行条目。

现在插入和删除：很明显，你不能只删除边并认为图形仍然仅由三角形组成；在删除过程中，您必须连接两个顶点，例如图形中的X和Y。为此，您首先必须确保边缘 a 在任何地方都被引用 - 我们必须修复该引用。

那么a可以在哪里引用呢？仅在边 b,c,d 和 e 中（所有其他边都离得太远而无法知道 a），如果有的话，请在 vertex->edge-table 中加上（但我们只考虑本例中的边表）。

作为我们如何修复边缘的示例，让我们看一下 c。与a 类似，c 也有左右前继和后继（因此有 4 个边），其中哪一个是 a？如果不进行检查，我们就无法知道这一点，因为 c 的表条目可以在其 Start-Node 或 End-Node 中包含节点 Y。所以我们必须检查它是哪一个，假设我们发现c的起始节点中有Y，然后我们必须检查a是否是c的 右前任（它是，我们通过查看 c's 条目并将其与 a 进行比较来找到）或者是否是 c's代码> 右后继者。 “接班人？？”你可能会问？是的，因为记住两个“左遍历”列是相对于向后移动边缘的。因此，现在我们发现 a 是 c 的右前驱，我们可以通过插入 a 的右前驱来修复该引用。继续处理其他 3 个边，边表就完成了。当然，修复额外的 Node->Vertices 很简单，只需查看 X 和 Y 的条目并删除其中的 a 即可。

添加边缘基本上与其他 4 个边缘的修复过程相反，但略有不同。让我们调用我们想要拆分的节点 Z （它将被拆分为 X 和 Y）。您必须注意以正确的方向拆分它，因为您可以将 d 和 e 组合在一个节点中，也可以将 e 和 < code>c （就像新边缘是水平的而不是图形中的垂直a）！您首先必须找出在即将成为的 X 的哪 2 条边之间以及在 Y 的哪 2 条边之间添加新边：您只需选择哪些边应位于一个节点上，哪个节点位于另一个节点上：在此示例图形中：选择您想要的 b、c 以及它们之间的北边 2 条边节点，因此其他边位于另一个节点上，该节点将变为X。然后，通过向量减法，您会发现新的边 a 必须位于 b 和 c 之间，而不是位于 c 和北部 2 个边之一之间。向量减法是新X的期望位置减去Y的期望位置。

I've learned about it in University but that was a while ago.

In response to this question i've searched the web too for any good documentation, found none that is good, but we can go through a quick example for CCW and CW order and insertion/deletion here.
Have a look at this table and graphic:
enter image description here
from this page:

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

The table gives only the entry for one edge a, in a real table you have this row for every edge. You can see you get the:

left predecessor,
left successor,
right predecessor,
right successor

but here comes the critical point: it gives them relative to the direction of the edge which is X->Y in this case, and when it is right-traversed (e->a->c).

So for the CW-order of going through the graph this is very easy to read: edge a left has right-successor c and then you look into the row for edge c.

Ok, this table is easy to read for CW-order traversal; for CCW you have to think "from which edge did i come from when i walked this edge backwards". Effectively you get the next edge in CCW-order by taking the left-traverse-predecessor in this case b and continue with the row-entry for edge b in the same manner.

Now insertion and deletion: It is clear that you cant just remove the edge and think that the graph would still consist of only triangles; during deletion you have to join two vertices, for example X and Y in the graphic. To do this you first have to make sure that everywhere the edge a is referred-to we have to fix that reference.

So where can a be referred-to? only in the edges b,c,d and e (all other edges are too far away to know a) plus in the vertex->edge-table if you have that (but let's only consider the edges-table in this example).

As an example of how we have to fix edges lets take a look at c. Like a, c has a left and right pre- and successor (so 4 edges), which one of those is a? We cannot know that without checking because the table-entry for c can have the node Y in either its Start- or End-Node. So we have to check which one it is, let's assume we find that c has Y in its Start-Node, we then have to check whether a is c's right predecessor (which it is and which we find out by looking at c's entry and comparing it to a) OR whether it is c's right successor. "Successor??" you might ask? Yes because remember the two "left-traverse"-columns are relative to going the edge backward. So, now we have found that a is c's right predecessor and we can fix that reference by inserting a's right predecessor. Continue with the other 3 edges and you are done with the edges-table. Fixing an additional Node->Vertices is trivial of course, just look into the entries for X and Y and delete a there.

Adding edges is basically the reverse of this fix-up of 4 other edges BUT with a little twist. Lets call the node which we want to split Z (it will be split into X and Y). You have to take care that you split it in the right direction because you can have either d and e combined in a node or e and c (like if the new edge is horizontal instead of the vertical a in the graphic)! You first have to find out between which 2 edges of the soon-to-be X and between which 2 edges of Y the new edge is added: You just choose which edges shall be on one node and which on the other node: In this example graphic: choose that you want b, c and the 2 edges to the north in between them on one node, and it follows that the other edges are on the other node which will become X. You then find by vector-subtraction that the new edge a has to be between b and c, not between say c and one of the 2 edges in the north. The vector-subtraction is the desired position of the new X minus the desired position of Y.