# Polyhedron manipulation in Python
[](https://pypi.org/project/pypoman/)
[](https://scaron.info/doc/pypoman/)
This library allows common operations over [convex polyhedra](https://en.wikipedia.org/wiki/Convex_polyhedron) such as [polytope projection](https://scaron.info/doc/pypoman/index.html#module-pypoman.projection) and [vertex enumeration](https://scaron.info/doc/pypoman/index.html#module-pypoman.duality).
See the [API documentation](https://scaron.info/doc/pypoman/) for details.
## Installation
Install system packages (here for Debian-based distributions) for Python and GLPK by:
```console
$ sudo apt-get install cython libglpk-dev python python-dev python-pip python-scipy
```
Then, install the library by:
```console
$ pip install pypoman
```
## Examples
### Vertex enumeration
We can compute the list of vertices of a polytope described in halfspace representation by $A x \leq b$:
```python
import numpy as np
from pypoman import compute_polytope_vertices
A = np.array([
[-1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
[0, -1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
[0, 0, -1, 0, 0, 0, 0, 0, 0, 0, 0, 0],
[0, 0, 0, -1, 0, 0, 0, 0, 0, 0, 0, 0],
[0, 0, 0, 0, -1, 0, 0, 0, 0, 0, 0, 0],
[0, 0, 0, 0, 0, -1, 0, 0, 0, 0, 0, 0],
[0, 0, 0, 0, 0, 0, -1, 0, 0, 0, 0, 0],
[0, 0, 0, 0, 0, 0, 0, -1, 0, 0, 0, 0],
[0, 0, 0, 0, 0, 0, 0, 0, -1, 0, 0, 0],
[0, 0, 0, 0, 0, 0, 0, 0, 0, -1, 0, 0],
[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, -1, 0],
[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, -1],
[1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0],
[0, 0, 0, 1, 1, 1, 0, 0, 0, 0, 0, 0],
[0, 0, 0, 0, 0, 0, 1, 1, 1, 0, 0, 0],
[0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1],
[1, 0, 0, 1, 0, 0, 1, 0, 0, 1, 0, 0],
[0, 1, 0, 0, 1, 0, 0, 1, 0, 0, 1, 0],
[0, 0, 1, 0, 0, 1, 0, 0, 1, 0, 0, 1]])
b = np.array([0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 2, 1, 2, 2, 1, 2, 3])
vertices = compute_polytope_vertices(A, b)
```
### Halfspace enumeration
The other way round, assume we know the vertices of a polytope, and want to get its halfspace representation $A x \leq b$.
```python
import numpy as np
from pypoman import compute_polytope_halfspaces
vertices = map(
np.array,
[[1, 0, 0], [0, 1, 0], [1, 1, 0], [0, 0, 1], [0, 1, 1]],
)
A, b = compute_polytope_halfspaces(vertices)
```
### Polytope projection
Let us project an $n$-dimensional polytope $A x \leq b$ over $x = [x_1\ \ldots\ x_n]$ onto its first two coordinates $proj(x) = [x_1 x_2]$:
```python
from numpy import array, eye, ones, vstack, zeros
from pypoman import plot_polygon, project_polytope
n = 10 # dimension of the original polytope
p = 2 # dimension of the projected polytope
# Original polytope:
# - inequality constraints: \forall i, |x_i| <= 1
# - equality constraint: sum_i x_i = 0
A = vstack([+eye(n), -eye(n)])
b = ones(2 * n)
C = ones(n).reshape((1, n))
d = array([0])
ineq = (A, b) # A * x <= b
eq = (C, d) # C * x == d
# Projection is proj(x) = [x_0 x_1]
E = zeros((p, n))
E[0, 0] = 1.
E[1, 1] = 1.
f = zeros(p)
proj = (E, f) # proj(x) = E * x + f
vertices = project_polytope(proj, ineq, eq, method='bretl')
if __name__ == "__main__": # plot projected polytope
import pylab
pylab.ion()
pylab.figure()
plot_polygon(vertices)
```
## See also
- A short introduction to [Polyhedra and polytopes](https://scaron.info/teaching/polyhedra-and-polytopes.html)
- Komei Fukuda's [Frequently Asked Questions in Polyhedral Computation](https://www.inf.ethz.ch/personal/fukudak/polyfaq/polyfaq.html)
- The [Polyhedron](http://doc.sagemath.org/html/en/reference/discrete_geometry/sage/geometry/polyhedron/constructor.html) class in [Sage](http://www.sagemath.org/)
- [StabiliPy](https://github.com/haudren/stabilipy): a Python package implementing a more general recursive method for polytope projection
Raw data
{
"_id": null,
"home_page": null,
"name": "pypoman",
"maintainer": null,
"docs_url": null,
"requires_python": ">=3.7",
"maintainer_email": "St\u00e9phane Caron <stephane.caron@normalesup.org>",
"keywords": "convex, polyhedron, polyhedra, polytope, projection, duality",
"author": null,
"author_email": "St\u00e9phane Caron <stephane.caron@normalesup.org>",
"download_url": "https://files.pythonhosted.org/packages/36/bc/c1d3e3b313a4e24291deda8ec0e894a279f5c880c8a584576f34c98ca49a/pypoman-1.0.0.tar.gz",
"platform": null,
"description": "# Polyhedron manipulation in Python\n\n[](https://pypi.org/project/pypoman/)\n[](https://scaron.info/doc/pypoman/)\n\n\nThis library allows common operations over [convex polyhedra](https://en.wikipedia.org/wiki/Convex_polyhedron) such as [polytope projection](https://scaron.info/doc/pypoman/index.html#module-pypoman.projection) and [vertex enumeration](https://scaron.info/doc/pypoman/index.html#module-pypoman.duality).\n\nSee the [API documentation](https://scaron.info/doc/pypoman/) for details.\n\n## Installation\n\nInstall system packages (here for Debian-based distributions) for Python and GLPK by:\n\n```console\n$ sudo apt-get install cython libglpk-dev python python-dev python-pip python-scipy\n```\n\nThen, install the library by:\n\n```console\n$ pip install pypoman\n```\n\n## Examples\n\n### Vertex enumeration\n\nWe can compute the list of vertices of a polytope described in halfspace representation by $A x \\leq b$:\n\n```python\nimport numpy as np\nfrom pypoman import compute_polytope_vertices\n\nA = np.array([\n [-1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],\n [0, -1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],\n [0, 0, -1, 0, 0, 0, 0, 0, 0, 0, 0, 0],\n [0, 0, 0, -1, 0, 0, 0, 0, 0, 0, 0, 0],\n [0, 0, 0, 0, -1, 0, 0, 0, 0, 0, 0, 0],\n [0, 0, 0, 0, 0, -1, 0, 0, 0, 0, 0, 0],\n [0, 0, 0, 0, 0, 0, -1, 0, 0, 0, 0, 0],\n [0, 0, 0, 0, 0, 0, 0, -1, 0, 0, 0, 0],\n [0, 0, 0, 0, 0, 0, 0, 0, -1, 0, 0, 0],\n [0, 0, 0, 0, 0, 0, 0, 0, 0, -1, 0, 0],\n [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, -1, 0],\n [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, -1],\n [1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0],\n [0, 0, 0, 1, 1, 1, 0, 0, 0, 0, 0, 0],\n [0, 0, 0, 0, 0, 0, 1, 1, 1, 0, 0, 0],\n [0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1],\n [1, 0, 0, 1, 0, 0, 1, 0, 0, 1, 0, 0],\n [0, 1, 0, 0, 1, 0, 0, 1, 0, 0, 1, 0],\n [0, 0, 1, 0, 0, 1, 0, 0, 1, 0, 0, 1]])\nb = np.array([0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 2, 1, 2, 2, 1, 2, 3])\n\nvertices = compute_polytope_vertices(A, b)\n```\n\n### Halfspace enumeration\n\nThe other way round, assume we know the vertices of a polytope, and want to get its halfspace representation $A x \\leq b$.\n\n```python\nimport numpy as np\nfrom pypoman import compute_polytope_halfspaces\n\nvertices = map(\n np.array,\n [[1, 0, 0], [0, 1, 0], [1, 1, 0], [0, 0, 1], [0, 1, 1]],\n)\n\nA, b = compute_polytope_halfspaces(vertices)\n```\n\n### Polytope projection\n\nLet us project an $n$-dimensional polytope $A x \\leq b$ over $x = [x_1\\ \\ldots\\ x_n]$ onto its first two coordinates $proj(x) = [x_1 x_2]$:\n\n```python\nfrom numpy import array, eye, ones, vstack, zeros\nfrom pypoman import plot_polygon, project_polytope\n\nn = 10 # dimension of the original polytope\np = 2 # dimension of the projected polytope\n\n# Original polytope:\n# - inequality constraints: \\forall i, |x_i| <= 1\n# - equality constraint: sum_i x_i = 0\nA = vstack([+eye(n), -eye(n)])\nb = ones(2 * n)\nC = ones(n).reshape((1, n))\nd = array([0])\nineq = (A, b) # A * x <= b\neq = (C, d) # C * x == d\n\n# Projection is proj(x) = [x_0 x_1]\nE = zeros((p, n))\nE[0, 0] = 1.\nE[1, 1] = 1.\nf = zeros(p)\nproj = (E, f) # proj(x) = E * x + f\n\nvertices = project_polytope(proj, ineq, eq, method='bretl')\n\nif __name__ == \"__main__\": # plot projected polytope\n import pylab\n pylab.ion()\n pylab.figure()\n plot_polygon(vertices)\n```\n\n## See also\n\n- A short introduction to [Polyhedra and polytopes](https://scaron.info/teaching/polyhedra-and-polytopes.html)\n- Komei Fukuda's [Frequently Asked Questions in Polyhedral Computation](https://www.inf.ethz.ch/personal/fukudak/polyfaq/polyfaq.html)\n- The [Polyhedron](http://doc.sagemath.org/html/en/reference/discrete_geometry/sage/geometry/polyhedron/constructor.html) class in [Sage](http://www.sagemath.org/)\n- [StabiliPy](https://github.com/haudren/stabilipy): a Python package implementing a more general recursive method for polytope projection\n",
"bugtrack_url": null,
"license": null,
"summary": "Python module for polyhedral geometry.",
"version": "1.0.0",
"project_urls": {
"Changelog": "https://github.com/stephane-caron/pypoman/blob/master/CHANGELOG.md",
"Documentation": "https://scaron.info/doc/pypoman/",
"Source": "https://github.com/stephane-caron/pypoman",
"Tracker": "https://github.com/stephane-caron/pypoman/issues"
},
"split_keywords": [
"convex",
" polyhedron",
" polyhedra",
" polytope",
" projection",
" duality"
],
"urls": [
{
"comment_text": null,
"digests": {
"blake2b_256": "9f1f41df88e28741e36aad74b53f5f11a27e2289ec74d3fc9899a99602debdb2",
"md5": "3019dedcd426f70e53cf76cb43032f17",
"sha256": "53602c6800839b39b33ccee60ef1afbbc475f70dfd5d0e2b736a15499804ab72"
},
"downloads": -1,
"filename": "pypoman-1.0.0-py3-none-any.whl",
"has_sig": false,
"md5_digest": "3019dedcd426f70e53cf76cb43032f17",
"packagetype": "bdist_wheel",
"python_version": "py3",
"requires_python": ">=3.7",
"size": 32652,
"upload_time": "2023-05-18T15:31:44",
"upload_time_iso_8601": "2023-05-18T15:31:44.881919Z",
"url": "https://files.pythonhosted.org/packages/9f/1f/41df88e28741e36aad74b53f5f11a27e2289ec74d3fc9899a99602debdb2/pypoman-1.0.0-py3-none-any.whl",
"yanked": false,
"yanked_reason": null
},
{
"comment_text": null,
"digests": {
"blake2b_256": "36bcc1d3e3b313a4e24291deda8ec0e894a279f5c880c8a584576f34c98ca49a",
"md5": "4d00c3e9c494ab7d2758eb44b62c61d8",
"sha256": "ecbb352b1bae6e65b4569e1c7a52d3c45e3a9fa1fb805ca439ade45fe4826489"
},
"downloads": -1,
"filename": "pypoman-1.0.0.tar.gz",
"has_sig": false,
"md5_digest": "4d00c3e9c494ab7d2758eb44b62c61d8",
"packagetype": "sdist",
"python_version": "source",
"requires_python": ">=3.7",
"size": 34509,
"upload_time": "2023-05-18T15:31:52",
"upload_time_iso_8601": "2023-05-18T15:31:52.623636Z",
"url": "https://files.pythonhosted.org/packages/36/bc/c1d3e3b313a4e24291deda8ec0e894a279f5c880c8a584576f34c98ca49a/pypoman-1.0.0.tar.gz",
"yanked": false,
"yanked_reason": null
}
],
"upload_time": "2023-05-18 15:31:52",
"github": true,
"gitlab": false,
"bitbucket": false,
"codeberg": false,
"github_user": "stephane-caron",
"github_project": "pypoman",
"travis_ci": false,
"coveralls": false,
"github_actions": true,
"tox": true,
"lcname": "pypoman"
}
JSON
