Finding the faces of a convex 4D polytope in Python

user_19844488 0
Viewed 58

I'm trying to get the faces of a convex 4-dymensional polytope whose vertices are known. How could I do that?

I have the 10 vertices of the polytope, which are:

p0=np.array([0,0,0,0])
p1=np.array([1,-1,0,0])
p2=np.array([1,0,0,-1])
p3=np.array([2,1,1,1])
p4=np.array([0,-1,1,0])
p5=np.array([0,0,1,-1])
p6=np.array([1,1,2,1])
p7=np.array([1,-1,1,-1])
p8=np.array([2,0,2,1])
p9=np.array([2,1,2,0])

I know in SymPy there is a function (Polyhedron.faces()) that returns the faces of 3D polyhedra. But I haven't found any other symilar functions for a higher dimension.

computational-geometry math algorithm python
2 Answers

Not a very appropriate answer because it is in R, with the cxhull package. But this package is a wrapper of the C(++) library qhull, and there exists a Python library wrapping this library as well, so maybe you can find the equivalent with Python.

library(cxhull)

vertices <- rbind(
  c(0, 0, 0, 0),
  c(1, -1, 0, 0),
  c(1, 0, 0, -1),
  c(2, 1, 1, 1),
  c(0, -1, 1, 0),
  c(0, 0, 1, -1),
  c(1, 1, 2, 1),
  c(1, -1, 1, -1),
  c(2, 0, 2, 1),
  c(2, 1, 2, 0)
)

hull <- cxhull(vertices)

The convex hull has 10 vertices:

length(hull$vertices)
10

Since we provided 10 vertices, we deal with a convex polytope.

Below is the information about the first facet (we say facet rather than face). It has four vertices, hence this is a tetrahedron.

### 1st facet:
hull[["facets"]][[1]]
# $vertices
# [1] 3 2 4 1
# 
# $edges
#      [,1] [,2]
# [1,]    1    2
# [2,]    1    3
# [3,]    1    4
# [4,]    2    3
# [5,]    2    4
# [6,]    3    4
# 
# $ridges
# [1] 1 2 3 4
# 
# $neighbors
# [1]  3  5  8 10
# 
# $volume
# [1] 0.7264832
# 
# $center
# [1] 1.00 0.00 0.25 0.00
# 
# $normal
# [1]  0.2294157  0.2294157 -0.9176629  0.2294157
# 
# $offset
# [1] 0
# 
# $family
# [1] NA
# 
# $orientation
# [1] 1

Let's get the number of vertices of each facet of the convex hull:

### numbers of vertices for each facet:
sapply(hull[["facets"]], function(facet) length(facet[["vertices"]]))
# 4 4 6 4 6 4 4 6 6 6

There are 10 facets having either four vertices (tetrahedra) or six vertices (octahedra).

More info about cxhull: https://github.com/stla/cxhull.

user_11001070

There is scipy.spatial.ConvexHull, a wrapper for C++ library qhull.

Documentation: https://docs.scipy.org/doc/scipy/reference/generated/scipy.spatial.ConvexHull.html

The facets are called "simplices" and the points that make them are referred to by index.

import numpy as np
from scipy.spatial import ConvexHull

points = np.array([[0,0,0,0],[1,-1,0,0],[1,0,0,-1],[2,1,1,1],[0,-1,1,0],[0,0,1,-1],[1,1,2,1],[1,-1,1,-1],[2,0,2,1],[2,1,2,0]])

hull = ConvexHull(points)

hull
# <scipy.spatial._qhull.ConvexHull object at 0x7ff4cbcea170>

hull.simplices
# array([[2, 1, 3, 0],
#        [5, 4, 6, 0],
#        [7, 9, 5, 2],
#        [8, 9, 6, 3],
#        [8, 7, 4, 1],
#        [9, 6, 3, 0],
#        [9, 2, 3, 0],
#        [9, 5, 2, 0],
#        [9, 5, 6, 0],
#        [7, 4, 1, 0],
#        [7, 5, 2, 0],
#        [7, 2, 1, 0],
#        [7, 5, 4, 0],
#        [8, 1, 3, 0],
#        [8, 6, 3, 0],
#        [8, 4, 1, 0],
#        [8, 4, 6, 0],
#        [8, 9, 5, 6],
#        [8, 5, 4, 6],
#        [8, 7, 5, 4],
#        [8, 7, 9, 5],
#        [8, 9, 2, 3],
#        [8, 7, 2, 1],
#        [8, 2, 1, 3],
#        [8, 7, 9, 2]], dtype=int32)
user_30807230
Related