PAYATHON 2026

如何用 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 仍按顶点坐标的算术平均值计算。

备注:内容仅供参考。