半边数据结构上的多边形边缘倒角

Question

我正在寻找多边缘棱角斜切在半边数据结构中的样例实现或者伪代码。单棱角斜切很容易，但一次进行多个边缘的操作...我已经尝试了几个小时还没有成功。我只是在处理拓扑变化方面遇到了困难，正确地推动顶点似乎并不那么困难。 基本上，我正在寻找如何通过半边数据结构从左侧网格转换为右侧网格的算法: 有人可以给我指引一篇论文、一本书或者一个多边缘棱角斜切的样例实现吗？

- matthias_buehlmann

Answer 1

我们可以将操作分为两个概念步骤。首先，加倍红色边缘。其次，爆炸至少与一个红色边缘相连的顶点。

第一步可以逐个边完成。给定红色边e，创建另一个边e'。对于e的一半边，将e'的一半边插入到具有相同头部的下一个半边中，顺时针排序。对于e的另一半边，将e'的另一半边插入到具有相同头部的下一个半边中，逆时针排序。

第二步可以逐个顶点完成。给定至少与一个红色边缘相连的顶点v，按如下方式分组具有头部v的半边。在每个相邻的从同一原始边缘产生的红色半边之间（2）和白色边缘之间（相邻意味着两个半边在顺时针/逆时针顺序中是下一个/上一个），打破该循环列表（1）。对于每个断点，创建一个新边。拼接所有内容。 （这涉及对断片和新边缘的端点进行操作。我认为在此答案的详细程度上进行详细描述是无益的。）

- David Eisenstat

---

你好，谢谢。到目前为止，对我来说这还不太有意义。我同意第一步是插入重复边。例如，“对于e的另一半边，在逆时针顺序中将e'的另一半边作为具有相同头部的下一个半边插入。” 这个我不理解的是，“外部”的那些半边为什么要这样处理？另外，“将所有东西拼接在一起”是我主要苦恼的地方。 - matthias_buehlmann

也许没有解释得很清楚，但这个答案是可靠的。本质上：通常情况下，当你倒角一个顶点（David 称之为爆炸）时，会在每个轮辐边之间创建一个新的边缘。然而，在这种情况下，在添加了初始的新红色边缘之后，您只想在两个红色和两个白色轮辐边之间创建一条边缘，而不是在红色和白色轮辐边之间创建一条边缘。实际上，首先创建删除顶点函数，连接顶点函数（在2个顶点之间创建边缘），可以用来创建倒角顶点函数。后者应该跳过在红色和白色辐条之间创建边缘的步骤。 - Xartec