Data

Tools

Indexes

Applications

Experiments

Open Source Science

pypoman

Python module for polyhedral geometry

https://github.com/stephane-caron/pypoman

Science Score: 26.0%

This score indicates how likely this project is to be science-related based on various indicators:

  • ○
    CITATION.cff file
  • ✓
    codemeta.json file
    Found codemeta.json file
  • ✓
    .zenodo.json file
    Found .zenodo.json file
  • ○
    DOI references
  • ○
    Academic publication links
  • ○
    Committers with academic emails
  • ○
    Institutional organization owner
  • ○
    JOSS paper metadata
  • ○
    Scientific vocabulary similarity
    Low similarity (12.4%) to scientific vocabulary

Keywords

double-description geometry polyhedron projection python vertex-enumeration
Last synced: 6 months ago · JSON representation

Repository

Python module for polyhedral geometry

Basic Info
  • Host: GitHub
  • Owner: stephane-caron
  • License: gpl-3.0
  • Language: Python
  • Default Branch: main
  • Homepage:
  • Size: 5.33 MB
Statistics
  • Stars: 75
  • Watchers: 6
  • Forks: 10
  • Open Issues: 0
  • Releases: 4
Topics
double-description geometry polyhedron projection python vertex-enumeration
Created almost 8 years ago · Last pushed 10 months ago
Metadata Files
Readme Changelog License

README.md

Polyhedron manipulation in Python

Build Documentation Coverage PyPI version PyPI downloads

This library interfaces common operations over convex polyhedra such as polytope projection and vertex enumeration. Check out the documentation for details.

Installation

Using conda

Install the cdd dependency first:

console $ conda install cddlib

Then install pypoman from PyPI:

console $ pip install pypoman

It won't need to build cdd from source as it is installed from conda-forge.

Building from source

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

console $ sudo apt-get install cython libcdd-dev libglpk-dev libgmp3-dev

You can then install the library from PyPI as follows. This approach will likely require building cdd from source.

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 computepolytopevertices

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 = computepolytopevertices(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 computepolytopehalfspaces

vertices = map( np.array, [[1, 0, 0], [0, 1, 0], [1, 1, 0], [0, 0, 1], [0, 1, 1]], )

A, b = computepolytopehalfspaces(vertices) ```

Polytope projection

Let us project an $n$-dimensional polytope $A x \leq b$ over $x = [x1\ \ldots\ xn]$ onto its first two coordinates $proj(x) = [x1 x2]$:

```python from numpy import array, eye, ones, vstack, zeros from pypoman import plotpolygon, projectpolytope

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: sumi xi = 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) = [x0 x1]

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

Owner

  • Name: Stéphane Caron
  • Login: stephane-caron
  • Kind: user
  • Location: Paris
  • Company: Inria

Likes open source robots.

GitHub Events

Total
  • Create event: 6
  • Release event: 2
  • Issues event: 4
  • Watch event: 9
  • Delete event: 2
  • Issue comment event: 8
  • Push event: 46
  • Pull request event: 5
Last Year
  • Create event: 6
  • Release event: 2
  • Issues event: 4
  • Watch event: 9
  • Delete event: 2
  • Issue comment event: 8
  • Push event: 46
  • Pull request event: 5

Committers

Last synced: 9 months ago

All Time
  • Total Commits: 241
  • Total Committers: 2
  • Avg Commits per committer: 120.5
  • Development Distribution Score (DDS): 0.004
Past Year
  • Commits: 61
  • Committers: 1
  • Avg Commits per committer: 61.0
  • Development Distribution Score (DDS): 0.0
Top Committers
Name Email Commits
Stéphane Caron s****n@n****g 240
Dawei Sun s****4@g****m 1
Committer Domains (Top 20 + Academic)
normalesup.org: 1

Issues and Pull Requests

Last synced: 6 months ago

All Time
  • Total issues: 9
  • Total pull requests: 10
  • Average time to close issues: 4 months
  • Average time to close pull requests: 4 days
  • Total issue authors: 9
  • Total pull request authors: 2
  • Average comments per issue: 1.78
  • Average comments per pull request: 1.0
  • Merged pull requests: 10
  • Bot issues: 0
  • Bot pull requests: 0
Past Year
  • Issues: 2
  • Pull requests: 5
  • Average time to close issues: 19 days
  • Average time to close pull requests: 7 days
  • Issue authors: 2
  • Pull request authors: 1
  • Average comments per issue: 0.5
  • Average comments per pull request: 0.8
  • Merged pull requests: 5
  • Bot issues: 0
  • Bot pull requests: 0
View more stats
Top Authors
Issue Authors
  • MoritzHein (1)
  • spertus (1)
  • alphaville (1)
  • ryanlovett (1)
  • peekxc (1)
  • jtuckerfoltz (1)
  • ferrolho (1)
  • juanvalencialopez (1)
  • paulpacaud (1)
Pull Request Authors
  • stephane-caron (12)
  • sundw2014 (1)
Top Labels
Issue Labels
Pull Request Labels

Packages

  • Total packages: 1
  • Total downloads:
    • pypi 2,455 last-month
  • Total dependent packages: 5
  • Total dependent repositories: 17
  • Total versions: 10
  • Total maintainers: 1
pypi.org: pypoman

Python module for polyhedral geometry.

  • Versions: 10
  • Dependent Packages: 5
  • Dependent Repositories: 17
  • Downloads: 2,455 Last month
Rankings
Dependent packages count: 1.6%
Dependent repos count: 3.5%
Average: 6.9%
Downloads: 7.8%
Stargazers count: 9.5%
Forks count: 11.9%
Maintainers (1)
stephane-caron
Last synced: 6 months ago

Dependencies

setup.py pypi
  • cvxopt *
  • pycddlib *