我正在寻找半边数据结构上多边斜面的示例实现或伪代码。单边斜边很容易-但是一次多边...我现在尝试了几个小时都没有成功。我只是在为拓扑变化而苦苦挣扎,正确地插入顶点看起来并不那么困难。
基本上,我正在寻找一种算法,该算法如何在半边数据结构上从左网格移到右网格:
谁能指出我的论文,书本或多边缘斜面的示例实现?
最佳答案
我们可以将操作分为两个概念性步骤。首先,将红色边缘加倍。其次,将入射到至少一个红色边缘的顶点爆炸。
第一步可以一次完成一个边缘。给定红色边e,创建另一个边e'。对于e的一半边缘,将e'的一半边缘作为下一个具有相同头的顺时针方向的半边缘插入。对于e的另一半边,以相同的头按逆时针方向插入e'的另一半边作为下一个半边。
第二步可以一次完成一个顶点。给定一个顶点v入射到至少一个红色边缘,按如下方式将半边缘与头部v分组。从相邻的两对白色边缘之间的同一原始边缘(2)产生的每对相邻的红色半边缘之间断开该圆形列表(1)(相邻意味着两个半边缘按顺时针/逆时针顺序位于下一个/上一个) 。对于每个休息,创建一个新的优势。将所有内容拼接在一起。 (这涉及对折断的片段的末端和新边缘进行操作。我认为在此答案中进行详细级别的详细描述将无济于事。)
关于algorithm - 半边结构上的多边斜面,我们在Stack Overflow上找到一个类似的问题:https://stackoverflow.com/questions/35378378/