如何用 Barycentric subdivision 求所有子 simplex 的顶点
结论
一个有 (K) 个顶点的 ((K-1))-simplex 经过一次 Barycentric subdivision,会得到 (K!) 个同维度的子 simplex。
每个子 simplex 对应原顶点的一种排列。设这个排列为
[ (v_{\pi_1},v_{\pi_2},\ldots,v_{\pi_K}), ]
那么子 simplex 的顶点依次为
[ b_1=v_{\pi_1}, ]
[ b_2=\frac{v_{\pi_1}+v_{\pi_2}}{2}, ]
[ \cdots ]
[ b_K=\frac{v_{\pi_1}+v_{\pi_2}+\cdots+v_{\pi_K}}{K}. ]
每个子 simplex 对应一条严格递增的 face chain:
[ {v_{\pi_1}} \subset {v_{\pi_1},v_{\pi_2}} \subset \cdots \subset {v_{\pi_1},\ldots,v_{\pi_K}}. ]
因此,只需枚举顶点的所有排列,不必分别枚举点、边、面及更高维 face。
Python 实现
这个函数适用于任意维度的 simplex,并支持重复 subdivision。level 的含义如下:
level=0:返回原 simplex;level=1:进行一次 Barycentric subdivision;level=n:对上一级得到的每个子 simplex 再进行一次 subdivision。
from itertools import permutations
import numpy as np
def barycentric_subdivision(vertices, level=1):
"""
对一个 simplex 进行重复 Barycentric subdivision。
Parameters
----------
vertices : array-like, shape (K, D)
simplex 的 K 个顶点。顶点位于 D 维坐标空间中。
level : int
subdivision 次数。0 表示不划分。
Returns
-------
list[np.ndarray]
每个元素的 shape 都是 (K, D),表示一个最大维子 simplex。
"""
vertices = np.asarray(vertices, dtype=float)
if vertices.ndim != 2:
raise ValueError("vertices 必须是 shape 为 (K, D) 的二维数组")
if not isinstance(level, int) or level < 0:
raise ValueError("level 必须是非负整数")
num_vertices, coordinate_dimension = vertices.shape
if num_vertices == 0:
raise ValueError("simplex 至少需要一个顶点")
# K 个顶点应当仿射独立,才能构成 (K-1)-simplex。
if num_vertices > 1:
affine_rank = np.linalg.matrix_rank(
vertices[1:] - vertices[0]
)
if affine_rank != num_vertices - 1:
raise ValueError("输入顶点不是仿射独立的,不能构成 simplex")
vertex_orders = list(permutations(range(num_vertices)))
simplices = [vertices.copy()]
for _ in range(level):
next_simplices = []
for simplex in simplices:
for order in vertex_orders:
child = np.empty(
(num_vertices, coordinate_dimension),
dtype=float,
)
running_sum = np.zeros(
coordinate_dimension,
dtype=float,
)
for position, vertex_index in enumerate(order):
running_sum += simplex[vertex_index]
child[position] = running_sum / (position + 1)
next_simplices.append(child)
simplices = next_simplices
return simplices
K = 3 的计算结果
vertices = [
[1, 0, 0],
[0, 1, 0],
[0, 0, 1],
]
simplices = barycentric_subdivision(vertices, level=1)
for simplex in simplices:
print(simplex.tolist())
输出为:
[[1.0, 0.0, 0.0],
[0.5, 0.5, 0.0],
[0.3333333333333333, 0.3333333333333333, 0.3333333333333333]]
[[1.0, 0.0, 0.0],
[0.5, 0.0, 0.5],
[0.3333333333333333, 0.3333333333333333, 0.3333333333333333]]
[[0.0, 1.0, 0.0],
[0.5, 0.5, 0.0],
[0.3333333333333333, 0.3333333333333333, 0.3333333333333333]]
[[0.0, 1.0, 0.0],
[0.0, 0.5, 0.5],
[0.3333333333333333, 0.3333333333333333, 0.3333333333333333]]
[[0.0, 0.0, 1.0],
[0.5, 0.0, 0.5],
[0.3333333333333333, 0.3333333333333333, 0.3333333333333333]]
[[0.0, 0.0, 1.0],
[0.0, 0.5, 0.5],
[0.3333333333333333, 0.3333333333333333, 0.3333333333333333]]
结果包含三角形的 6 个子三角形。
以排列 (0, 1, 2) 为例,它对应的 face chain 为
[ {v_0} \subset {v_0,v_1} \subset {v_0,v_1,v_2}, ]
三个 barycenter 分别为
[ v_0=[1,0,0], ]
[ \frac{v_0+v_1}{2}
\left[\frac12,\frac12,0\right], ]
[ \frac{v_0+v_1+v_2}{3}
\left[\frac13,\frac13,\frac13\right]. ]
需要精确分数时
浮点数只能近似表示 (1/3)。如果结果还要用于符号计算,可以改用 fractions.Fraction:
from fractions import Fraction
from itertools import permutations
def barycentric_subdivision_exact(vertices, level=1):
"""
使用 Fraction 进行精确的 Barycentric subdivision。
"""
if not isinstance(level, int) or level < 0:
raise ValueError("level 必须是非负整数")
if not vertices or not vertices[0]:
raise ValueError("vertices 不能为空")
coordinate_dimension = len(vertices[0])
if any(len(vertex) != coordinate_dimension for vertex in vertices):
raise ValueError("所有顶点必须具有相同的坐标维度")
def to_fraction(value):
if isinstance(value, Fraction):
return value
return Fraction(str(value))
initial_simplex = [
[to_fraction(value) for value in vertex]
for vertex in vertices
]
num_vertices = len(initial_simplex)
vertex_orders = list(permutations(range(num_vertices)))
simplices = [initial_simplex]
for _ in range(level):
next_simplices = []
for simplex in simplices:
for order in vertex_orders:
running_sum = [
Fraction(0) for _ in range(coordinate_dimension)
]
child = []
for position, vertex_index in enumerate(order, start=1):
vertex = simplex[vertex_index]
for coordinate in range(coordinate_dimension):
running_sum[coordinate] += vertex[coordinate]
child.append([
value / position for value in running_sum
])
next_simplices.append(child)
simplices = next_simplices
return simplices
调用方式:
vertices = [
[1, 0, 0],
[0, 1, 0],
[0, 0, 1],
]
simplices = barycentric_subdivision_exact(vertices, level=1)
for simplex in simplices:
print(simplex)
其中一个子 simplex 的表示如下:
[
[Fraction(1, 1), Fraction(0, 1), Fraction(0, 1)],
[Fraction(1, 2), Fraction(1, 2), Fraction(0, 1)],
[Fraction(1, 3), Fraction(1, 3), Fraction(1, 3)]
]
复杂度和返回结果
一个有 (K) 个顶点的 simplex 每经过一层 subdivision,子 simplex 的数量都会乘以 (K!)。经过 (L) 层后,最大维子 simplex 的数量为
[ (K!)^L. ]
具体来说:
- 线段有 2 个顶点,每层数量乘以 (2);
- 三角形有 3 个顶点,每层数量乘以 (6);
- 四面体有 4 个顶点,每层数量乘以 (24)。
随着维度或 subdivision 层数增加,内存占用会迅速增长。如果只需逐个处理结果,可以把函数改成 generator,避免一次保存所有子 simplex。
函数返回的是构成完整分割所需的最大维子 simplex。这些子 simplex 的内部互不相交,边界则会重合,因此同一个 barycenter 可能出现在多个子 simplex 中。构造 mesh 时,可以先对顶点去重,再用索引表示各个 simplex。
输入顶点不必是标准基向量。只要 (K) 个顶点仿射独立,它们就可以位于任意坐标空间中,barycenter 仍按顶点坐标的算术平均值计算。
备注:内容仅供参考。
