I have a set of K dimension standard basis vectors and the (K-1)-simplex defined over these vectors. I want to divide this simplex into sub-simplexes which partition the original simplex using Barycentric subdivision.
For example when K = 3, the three vertices of the simplex are [1,0,0], [0,1,0] and [0,0,1]. If you subdivide this at the coarsest level using barycentric subdivision you get the following:
The following list of lists provides all the vertices of each sub-simplex which partitions the original simplex:
In lower dimensions this is an easy task to do by hand, however I would like to write a function (ideally in python, though I am flexible) that takes the vertices of the original simplex and the level of split and returns the list of lists of each sub-simplex and it's vertices.
I have tried to develop an algorithm that answers this problem, however I get stuck in the logic. Each sub-simplex will contain a vertex on of the (K-1) dimensions, e.g. in this case a point, on the edge and on the face. Therefore I tried a combinatory approach, but couldn't extend it to N dimensions in way that can be programmed into a function.
Is anyone aware of a relevant package (or mathematical software?) that can help answer this question, or on how to write the logic into a python function.
You can try the following:
from itertools import permutations
import numpy as np
from sympy import Rational
k = 2 # dimension of the simplex
fracs = np.c_[[Rational(1, i) for i in range(1, k+2)]]
subdivision = []
for p in permutations(range(k+1)):
s = np.where(np.tile(p, (k+1, 1)) <= np.c_[:k+1], fracs, 0)
subdivision.append(s)
for s in subdivision:
print(*s)
It gives:
[1 0 0] [1/2 1/2 0] [1/3 1/3 1/3]
[1 0 0] [1/2 0 1/2] [1/3 1/3 1/3]
[0 1 0] [1/2 1/2 0] [1/3 1/3 1/3]
[0 0 1] [1/2 0 1/2] [1/3 1/3 1/3]
[0 1 0] [0 1/2 1/2] [1/3 1/3 1/3]
[0 0 1] [0 1/2 1/2] [1/3 1/3 1/3]
The code will work for any k, but since the barycentric subdivision of a k-simplex has (k+1)! simplices of dimension k, it is not practical compute them all for larger values of k.