一个网格由许多三角面组成,边通常会被一面或两面引用。统计每条边的引用次数和方向,能发现一些缺口、重复面或局部朝向不一致的线索。
将每条有向三角边归入由较小顶点编号到较大编号的无向键。只有一个引用记为边界边;两个引用时再检查方向是否相反;超过两个引用记为多重共享。顶点集合相同的面还单独列为重复候选。
本例的输入和输出
九个顶点按三乘三网格逐行编号零至八。三角面列表按顶点绕行顺序为[[5, 2, 1], [7, 4, 3], [4, 5, 8], [0, 4, 3], [1, 5, 4], [3, 7, 6], [0, 4, 3]]。
无向边 | 面编号与原始有向边 | 分类 [0, 3] | [[3, 3, 0], [6, 3, 0]] | 同向引用 [0, 4] | [[3, 0, 4], [6, 0, 4]] | 同向引用 [1, 2] | [[0, 2, 1]] | 边界 [1, 4] | [[4, 4, 1]] | 边界 [1, 5] | [[0, 1, 5], [4, 1, 5]] | 同向引用 [2, 5] | [[0, 5, 2]] | 边界 [3, 4] | [[1, 4, 3], [3, 4, 3], [6, 4, 3]] | 多重共享 [3, 6] | [[5, 6, 3]] | 边界 [3, 7] | [[1, 3, 7], [5, 3, 7]] | 同向引用 [4, 5] | [[2, 4, 5], [4, 5, 4]] | 反向配对 [4, 7] | [[1, 7, 4]] | 边界 [4, 8] | [[2, 8, 4]] | 边界 [5, 8] | [[2, 5, 8]] | 边界 [6, 7] | [[5, 7, 6]] | 边界 顶点集合重复的面编号组:[[3, 6]]
表格中的编号只标识当前例子的元素,不应把对象身份、数组下标与计算数值混为一谈。阅读时先核对输入和边界,再沿记录检查每一步;空结果表示规则下没有可用项,并不是默认返回数值零。
复核与适用条件
所有边引用数相加应等于面数的三倍。对希望一致定向的相邻三角面,同一共享边应以相反方向出现;不能仅看到引用次数为二就认为局部朝向一定正确。
这些只是局部拓扑检查,不等于完整的网格有效性检测。顶点附近连接是否合适、三角面是否相交、坐标是否退化以及边界是否符合设计,都需要其他检查,不能凭一张计数表全部确认。
练习时先独立复算一小段,再检查整体结果是否满足文中条件。遇到差异应保留中间记录并定位第一处不一致,而不是只调整最后答案。更换输入或操作规则后,需要重新计算,原记录只对这一例负责。
