by Pearu Peterson, LGPL


Oct 10, 2007, polyhedron version 0.2.1

Fixed a bug in cddlib-0.94d causing segfault when computing Vrep from a minimal number of vertices. Patched cddlib-0.94d is included.

Oct 9, 2007, polyhedron version 0.2

Made polyhedron a package. Dropped Numeric support, supporting NumPy instead. Added file. The source of cddlib is now included. Using GMP is optional.


PyPolyhedron is a Python interface to a C-library cddlib:
C-Library cddlib (version 0.91) README FILE
1. The C-library  cddlib is a C implementation of the Double Description 
Method of Motzkin et al. for generating all vertices (i.e. extreme points)
and extreme rays of a general convex polyhedron in R^d given by a system 
of linear inequalities:

   P = { x=(x1, ..., xd)^T :  b - A  x  >= 0 }

where  A  is a given m x d real matrix, b is a given m-vector 
and 0 is the m-vector of all zeros.


To use PyPolyhedron, compile it (see below) and import polyhedron from Python program. The package polyhedron provides two classes Hrep and Vrep which will hold polyhedron's data.

Currently, there is no documentation available, but the code is really simple in order to get an idea how to access polyhedron's data from Python. See Polyhedron.__str__ method and the header of _cddmodule.c for more details.

Here follows an example how to construct a convex hull from a set of random points and then to test if a random point is inside or outside the hull:

from numpy import *
from polyhedron import Vrep, Hrep

points = random.random ((20,3))

def mkhull(points):
    p = Vrep (points)
    return Hrep (p.A, p.b)
p = mkhull(points)

print 'Hull vertices:\n',p.generators

points2 = 1.1*random.random ((3,3))
for i in range (len (points2)):
    point = points2[i]
    if alltrue (dot (p.A,point) <= p.b):
        print 'point',point,'is IN'
        print 'point',point,'is OUT'


Run python install to build and install polyhedron package.

Run python build_ext --inplace to build polyhedron package in-situ.


You'll need
  1. Python
  2. NumPy (version or newer) to compile C/API modules.
The source of cddlib-094d is included with the package. Using GMP library is optional (you'll need to update the file properly for that).


  1. src/polyhedron.tgz

Pearu Peterson <>
Last modified: Oct 9, 2007
Submit this page for validation