Revision history [back]

If you write an equation as list [A,B,C,D] instead of Ax + By + C*z == D, you can easily use matrix operations to find the vertices. This seems to be much faster.

equations =[[1,0,0,1],[1,0,0,-1],[0,1,0,1],[0,1,0,-1],[0,0,1,1],[0,0,1,-1]]

def get_matrix(L,K):
    M = matrix(QQ,3,3)
    M.set_row(0,L[K[0]][:3])
    M.set_row(1,L[K[1]][:3])
    M.set_row(2,L[K[2]][:3])
    return  M

def get_vector(L,K):
    return vector(QQ,(L[K[0]][3],L[K[1]][3],L[K[2]][3]))

def find_vertices_2(eqns):
    vertices = []
    for C in combinations(range(len(eqns)),3):
        M = get_matrix(eqns,C)
        b = get_vector(eqns,C)
        if M.is_invertible():
            P = M.solve_right(b)
            if not P in vertices:
                vertices.append(P)
    return vertices

I compared this function find_vertices_2 with a function find_vertices_1 based on solving systems of linear equations:

timeit('find_vertices_1(eqns)',number=20)

20 loops, best of 3: 1.3 s per loop

timeit('find_vertices_2(equations)',number=20)

20 loops, best of 3: 15.8 ms per loop

If you write an equation as list [A,B,C,D] instead of Ax + By + C*z == D, you can easily use matrix operations to find the vertices. This seems to be much faster.

equations =[[1,0,0,1],[1,0,0,-1],[0,1,0,1],[0,1,0,-1],[0,0,1,1],[0,0,1,-1]]

def get_matrix(L,K):
    M = matrix(QQ,3,3)
    M.set_row(0,L[K[0]][:3])
    M.set_row(1,L[K[1]][:3])
    M.set_row(2,L[K[2]][:3])
    return  M

def get_vector(L,K):
    return vector(QQ,(L[K[0]][3],L[K[1]][3],L[K[2]][3]))

def find_vertices_2(eqns):
    vertices = []
    for C in combinations(range(len(eqns)),3):
        M = get_matrix(eqns,C)
        b = get_vector(eqns,C)
        if M.is_invertible():
            P = M.solve_right(b)
            if not P in vertices:
                vertices.append(P)
    return vertices

I compared this function find_vertices_2 with to a function find_vertices_1 based on solving systems of linear equations:

timeit('find_vertices_1(eqns)',number=20)

20 loops, best of 3: 1.3 s per loop

timeit('find_vertices_2(equations)',number=20)

20 loops, best of 3: 15.8 ms per loop