半边缘结构上的多边斜角

Question

我正在寻找半边数据结构上的多边斜角的示例实现或伪代码.单边斜角很容易 - 但是同时有多个边缘......我现在试了好几个小时都没有成功.我只是在拓扑变化中挣扎,正确地推动顶点看起来并不那么困难.基本上,我正在寻找一种关于如何在半边数据结构上从左网格到右网格的算法:

任何人都可以指向一篇论文,一本书或多边斜角的示例实现吗？

Answer 1

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

第一步可以一次完成一个边缘。给定一条红边 e，创建另一条边 e'。对于e的一个半边，按顺时针顺序插入e'的一个半边作为下一个相同头的半边。对于e的另一半边，将e'的另一半边按逆时针顺序插入，作为同头的下半边。

第二步可以一次完成一个顶点。给定一个与至少一个红色边相关的顶点 v，将具有头 v 的半边分组如下。打破每对相邻的红色半边之间的循环列表 (1)，这些红色半边源自每对相邻的白色边之间的同一原始边 (2)（相邻意味着两个半边按顺时针/逆时针顺序是下一个/上一个半边） 。对于每个中断，创建一个新边缘。将所有东西拼接在一起。（这涉及对破碎碎片的末端和新边缘进行操作。我认为这个答案中的详细描述是没有帮助的。）