pypoman

Name	pypoman JSON
Version	1.2.0 JSON
	download
home_page	None
Summary	Python module for polyhedral geometry.
upload_time	2025-01-06 14:09:46
maintainer	None
docs_url	None
author	None
requires_python	>=3.9
license	None
keywords	convex polyhedron polyhedra polytope projection duality
VCS
bugtrack_url
requirements	No requirements were recorded.
Travis-CI	No Travis.
coveralls test coverage	No coveralls.

            # Polyhedron manipulation in Python

[![Build](https://img.shields.io/github/actions/workflow/status/stephane-caron/pypoman/ci.yml?branch=main)](https://github.com/stephane-caron/pypoman/actions)
[![Coverage](https://coveralls.io/repos/github/stephane-caron/pypoman/badge.svg?branch=main)](https://coveralls.io/github/stephane-caron/pypoman?branch=main)
[![Documentation](https://img.shields.io/badge/docs-online-brightgreen?logo=read-the-docs&style=flat)](https://scaron.info/doc/pypoman/)
[![PyPI version](https://img.shields.io/pypi/v/pypoman?color=blue)](https://pypi.org/project/pypoman/)
[![PyPI downloads](https://img.shields.io/pypi/dm/pypoman?color=blue)](https://pypistats.org/packages/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). Check out the [API documentation](https://scaron.info/doc/pypoman/) for details.

## Installation

Install system packages for Python and GLPK, for instance for Debian-based Linux distributions:

```console
$ sudo apt-get install cython libglpk-dev python python-dev python-pip
```

Then, install the library by:

```console
$ pip install pypoman
```

Some functions, such as point-polytope projection and polygon intersection, are optional and not installed by default. To enable all of them, run:

```console
$ pip install pypoman[all]
```

## 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')
```

We can then plot the projected polytope:

```python
import pylab

pylab.ion()
pylab.figure()
plot_polygon(vertices)
```

## See also

- A short introduction to [Polyhedra and polytopes](https://scaron.info/blog/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.9",
    "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/73/aa/e138a986e6146f84f8ea77ef0d6fccbda7b502617e83e368a4677dc801dc/pypoman-1.2.0.tar.gz",
    "platform": null,
    "description": "# Polyhedron manipulation in Python\n\n[![Build](https://img.shields.io/github/actions/workflow/status/stephane-caron/pypoman/ci.yml?branch=main)](https://github.com/stephane-caron/pypoman/actions)\n[![Coverage](https://coveralls.io/repos/github/stephane-caron/pypoman/badge.svg?branch=main)](https://coveralls.io/github/stephane-caron/pypoman?branch=main)\n[![Documentation](https://img.shields.io/badge/docs-online-brightgreen?logo=read-the-docs&style=flat)](https://scaron.info/doc/pypoman/)\n[![PyPI version](https://img.shields.io/pypi/v/pypoman?color=blue)](https://pypi.org/project/pypoman/)\n[![PyPI downloads](https://img.shields.io/pypi/dm/pypoman?color=blue)](https://pypistats.org/packages/pypoman)\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). Check out the [API documentation](https://scaron.info/doc/pypoman/) for details.\n\n## Installation\n\nInstall system packages for Python and GLPK, for instance for Debian-based Linux distributions:\n\n```console\n$ sudo apt-get install cython libglpk-dev python python-dev python-pip\n```\n\nThen, install the library by:\n\n```console\n$ pip install pypoman\n```\n\nSome functions, such as point-polytope projection and polygon intersection, are optional and not installed by default. To enable all of them, run:\n\n```console\n$ pip install pypoman[all]\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```\n\nWe can then plot the projected polytope:\n\n```python\nimport pylab\n\npylab.ion()\npylab.figure()\nplot_polygon(vertices)\n```\n\n## See also\n\n- A short introduction to [Polyhedra and polytopes](https://scaron.info/blog/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.2.0",
    "project_urls": {
        "Changelog": "https://github.com/stephane-caron/pypoman/blob/main/CHANGELOG.md",
        "Documentation": "https://scaron.info/doc/pypoman/",
        "Homepage": "https://github.com/stephane-caron/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": "e58b5dba19312eab895c4aff368228f1b0f25cd743bcbce5b274b4499f1b13d3",
                "md5": "ad12baa7822a34ddac08b3d509eba21e",
                "sha256": "7af008697e6a720f69f7501e7f072c3ab366fa2759aba983192c317283c4337e"
            },
            "downloads": -1,
            "filename": "pypoman-1.2.0-py3-none-any.whl",
            "has_sig": false,
            "md5_digest": "ad12baa7822a34ddac08b3d509eba21e",
            "packagetype": "bdist_wheel",
            "python_version": "py3",
            "requires_python": ">=3.9",
            "size": 29559,
            "upload_time": "2025-01-06T14:09:45",
            "upload_time_iso_8601": "2025-01-06T14:09:45.105540Z",
            "url": "https://files.pythonhosted.org/packages/e5/8b/5dba19312eab895c4aff368228f1b0f25cd743bcbce5b274b4499f1b13d3/pypoman-1.2.0-py3-none-any.whl",
            "yanked": false,
            "yanked_reason": null
        },
        {
            "comment_text": null,
            "digests": {
                "blake2b_256": "73aae138a986e6146f84f8ea77ef0d6fccbda7b502617e83e368a4677dc801dc",
                "md5": "35a583a30870588c1db2d564c1f81a0c",
                "sha256": "8c88e335d87457724aaa631df6259300283096bedfbbe091474d4d5fc8ee20f7"
            },
            "downloads": -1,
            "filename": "pypoman-1.2.0.tar.gz",
            "has_sig": false,
            "md5_digest": "35a583a30870588c1db2d564c1f81a0c",
            "packagetype": "sdist",
            "python_version": "source",
            "requires_python": ">=3.9",
            "size": 35748,
            "upload_time": "2025-01-06T14:09:46",
            "upload_time_iso_8601": "2025-01-06T14:09:46.739957Z",
            "url": "https://files.pythonhosted.org/packages/73/aa/e138a986e6146f84f8ea77ef0d6fccbda7b502617e83e368a4677dc801dc/pypoman-1.2.0.tar.gz",
            "yanked": false,
            "yanked_reason": null
        }
    ],
    "upload_time": "2025-01-06 14:09:46",
    "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"
}