pythoncombinatoricssimplexn-dimensional

Find the vertices of all the sub-simplexes following Barycentric subdivision


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:

  1. Find the mid point of each edge: [1/2, 1/2, 0], [1/2, 0, 1/2],[0, 1/2, 1/2]
  2. Find the barycentric point: [1/3, 1/3, 1/3]

The following list of lists provides all the vertices of each sub-simplex which partitions the original simplex:

  1. [[[1,0,0], [1/2, 1/2, 0] [1/3, 1/3, 1/3]]]
  2. [[[1,0,0], [1/2, 0, 1/2] [1/3, 1/3, 1/3]]]
  3. [[[0,1,0], [1/2, 1/2, 0] [1/3, 1/3, 1/3]]]
  4. [[[0,1,0], [0, 1/2, 1/2] [1/3, 1/3, 1/3]]]
  5. [[[0,0,1], [1/2, 0 ,1/2] [1/3, 1/3, 1/3]]]
  6. [[[0,0,1], [0, 1/2, 1/2] [1/3, 1/3, 1/3]]]

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.


Solution

  • 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.