半边数据结构：从邻接关系到遍历

2014 年做计算机图形学作业时，我需要用到半边数据结构，于是翻译了 flipcode 的 The Half-Edge Data Structure。这次迁移保留原笔记的问题与解释线索，校订复杂度和边界条件，并补上一个独立的代码例子。

无论是顶点列表、面列表还是半边结构，都是把网格存进内存的方式。选择的关键不只是能否画出同一个物体，还在于接下来要做哪些运算。

为什么要显式保存邻接关系

共享顶点列表加上面的顶点索引，是表示多边形网格的一种直接方式。但做边折叠等局部修改时，我们还需要知道：哪些面使用一个顶点，哪些边属于一个面，一条边两侧分别是什么面？如果每次都扫描整个面列表，局部操作就会付出不必要的代价。

半边结构把这些关系直接保存下来，用额外的存储换取方便的局部访问。与翼边结构一样，它属于显式描述网格拓扑关系的表示方法。

一条边，两个方向

半边不是把一条线段截成两段，而是给同一条边的两个方向分别建记录。内部边的两条半边方向相反，互为 twin。沿一个面的边界走，半边通过 next 组成环；全网格采用一致的面朝向。

下面用共享边 AB 的两个三角形表示这种关系：

          C
         / \
        /   \
       A ──→ B       上方的面：A → B → C → A
        ←──          下方的面：B → A → D → B
        \   /
         \ /
          D

h = A → B，twin(h) = B → A
next(h) = B → C

每条半边可以保存起点、所属面、下一条半边和反向半边。也有实现保存终点；这是约定的差别，遍历时必须保持一致。顶点保存一条出发半边，面保存边界上的任意一条半边，作为遍历入口。

边界与流形条件

常见的半边结构面向可一致定向的二维流形网格。闭合网格的每条边邻接两个面；有边界的网格允许边只邻接一个面。边界可以用空 twin，也可以建立没有内部面的外侧半边来表示，不能把“有洞或有边界”一概当作半边结构不能处理的情况。

如果三个或更多的面共享同一条边，普通的单个 twin 字段就不够用了。只检查每条边的面数也不足以保证流形性，还需要检查顶点周围的面是否构成单个扇形或环。T 形接缝等不一致连接，也需要先修正拓扑或采用能表示它的扩展结构。

最小代码例子

以下 Python 例子使用数组索引保存关系，origin 表示起点；边界半边的 twin 为 None。它只展示已建好结构的遍历，不包含网格导入、验证和修改算法。

from dataclasses import dataclass
from typing import Optional

@dataclass
class HalfEdge:
    origin: str
    face: int
    next: int
    twin: Optional[int] = None

edges = [
    HalfEdge("A", 0, 1, 3),  # A -> B
    HalfEdge("B", 0, 2),     # B -> C
    HalfEdge("C", 0, 0),     # C -> A
    HalfEdge("B", 1, 4, 0),  # B -> A
    HalfEdge("A", 1, 5),     # A -> D
    HalfEdge("D", 1, 3),     # D -> B
]

def face_vertices(start):
    result = []
    current = start
    seen = set()
    while current not in seen:
        seen.add(current)
        edge = edges[current]
        if edge.face != edges[start].face:
            raise ValueError("next crosses a face boundary")
        result.append(edge.origin)
        current = edge.next
    if current != start:
        raise ValueError("face ring does not return to its start")
    return result

assert face_vertices(0) == ["A", "B", "C"]
assert face_vertices(3) == ["B", "A", "D"]
assert edges[edges[0].twin].twin == 0

在这个起点约定下，对于闭合、定向一致的流形顶点，从一条出发半边沿 twin.next 可以转到同一起点的另一条出发半边。但上例存在边界，不能不检查 twin 就套用闭合环遍历；要枚举完整边界邻域，还需要约定遍历起点和两个方向的处理方式。

“常数时间”的准确含义

访问已知半边的 next、twin 或所属面是 O(1)。枚举一个面上的 k 条半边仍然需要 O(k)，枚举一个顶点周围的 d 个邻接面需要 O(d)，并不是整个邻域查询都只要常数时间。

半边结构省下的是每次从全局列表重新寻找邻接关系的工作。局部编辑也要维护成对关系、面环和入口索引；结构方便并不意味着拓扑修改天然正确。