半边结构实践总结

作者: 姚彧
版本历史：

版权声明：本文为作者原创文章，博客地址：https://www.cnblogs.com/yaoyu126 未经作者允许不得转载。

1. 半边定义

为了方便表达流形表面，通过把一条边拆分成相对两条半边，使我们查找边、顶点、面非常便捷。

2. 半边的基本性质

2.1 一条边

对于一条边来说，对边正好构成了环。

\(e_0=\left\{\begin{aligned} e_1.pair \\ e_1.next \\ e_1.prev \\ \end{aligned}\right.\)
\(e_1=\left\{\begin{aligned} e_0.pair \\ e_0.next \\ e_0.prev \\ \end{aligned}\right.\)

2.2 在顶点插入边

将\(e_n\)插入到\(e_0\)之前，步骤如下：

1. 找到前边\(e_0.prev\);
2. \(e_0.prev.next = e_n.next\)
3. \(e_n.next = e_0\)

3. 基本数据结构

在这里，我们约定按逆时针方向设置半边。

# 顶点
class HE_vert:
    edge        # 顶点指向的半边

# 面
class HE_face:
    edge        # 面右侧的半边

# 半边
class HE_edge:
    vert        # 半边指向的顶点
    pair        # 对边（半边成对）
    next        # 下一条半边
    face        # 半边左侧的面

4. 构网问题

4.1 在三维文件中，面与面之间并不一定连续

面与面的不连续，造成了构网过程时，顶点的遍历算法失效。这是因为构网过程中，造成了它不是流形表面，这时用字典记录点对对应的半边来解决已有边查找问题。在格网构建完成后，因为是流形面，顶点的遍历算法又有效了。