Welcome to the documentation of pypoman, a PYthon module for POlyhedral MANipulations.

Chebyshev center¶

pypoman.polyhedron.compute_chebyshev_center(A: ndarray, b: ndarray) → ndarray¶

Compute the Chebyshev center of a polyhedron.

The Chebyshev center is the point furthest away from all inequalities.

Parameters:

A – Matrix of halfspace representation.
b – Vector of halfspace representation.

Returns:

Point further away from all inequalities.

Notes

The Chebyshev center is discussed in [Boyd04], Section 4.3.1, p. 148.

Duality¶

Functions to switch between halfspace and vertex representations.

pypoman.duality.compute_cone_face_matrix(S: ndarray) → ndarray¶

Compute the face matrix of a polyhedral cone from its span matrix.

Parameters:: S – Span matrix defining the cone as \(x = S \lambda\) with \(\lambda \geq 0\).
Returns:: Face matrix defining the cone equivalently by \(F x \leq 0\).

pypoman.duality.compute_polytope_halfspaces(vertices: List[ndarray]) → ndarray | Tuple[ndarray, ndarray]¶

Compute the halfspace representation (H-rep) of a polytope.

The polytope is defined as convex hull of a set of vertices:

\[A x \leq b \quad \Leftrightarrow \quad x \in \mathrm{conv}(\mathrm{vertices})\]

Parameters:: vertices – List of polytope vertices.
Returns:: Tuple (A, b) of the halfspace representation, or empty array if it is empty.

pypoman.duality.compute_polytope_vertices(A: ndarray, b: ndarray) → List[ndarray]¶

Compute the vertices of a polytope.

The polytope is given in halfspace representation by \(A x \leq b\).

Parameters:

A – Matrix of halfspace representation.
b – Vector of halfspace representation.

Returns:

List of polytope vertices.

Notes

This method won’t work well if your halfspace representation includes equality constraints \(A x = b\) written as \((A x \leq b \wedge -A x \leq -b)\). If this is your use case, consider using directly the linear set lin_set of equality-constraint generatorsin pycddlib.

pypoman.duality.convex_hull(points: List[ndarray]) → List[ndarray]¶

Compute the convex hull of a set of points.

Parameters:: points – Set of points.
Returns:: List of polytope vertices.

Intersection¶

Intersections between lines and polyhedra.

pypoman.intersection.intersect_line_cylinder(line: Tuple[ndarray, ndarray], vertices: List[ndarray]) → List[ndarray]¶

Intersect the line segment [p1, p2] with a vertical cylinder.

The vertical cylinder has a polygonal cross-section. If the intersection has two points, this function returns the one closest to p1.

Parameters:

line – End points of the 3D line segment.
vertices – Vertices of the polygon.

Returns:

List of intersection points between the line segment and the cylinder.

Return type:

inter_points

pypoman.intersection.intersect_line_polygon(line: Tuple[ndarray, ndarray], vertices: List[ndarray], apply_hull: bool) → List[ndarray]¶

Intersect a line segment with a polygon.

Parameters:

line – End points of the line segment (2D or 3D).
vertices – Vertices of the polygon.
apply_hull – Set to True to apply a convex hull algorithm to vertices. Otherwise, the function assumes that vertices are already sorted in clockwise or counterclockwise order.

Returns:

List of intersection points between the line segment and the polygon.

Notes

This code is adapted from <https://stackoverflow.com/questions/20677795/how-do-i-compute-the-intersection-point-of-two-lines-in-python/20679579#20679579>. On the same setting with apply_hull=False, it %timeits to 6 us.

pypoman.intersection.intersect_polygons(polygon1: List[ndarray], polygon2: List[ndarray]) → List[ndarray]¶

Intersect two polygons.

Parameters:

polygon1 – Vertices of the first polygon in counterclockwise order.
polygon1 – Vertices of the second polygon in counterclockwise order.

Returns:

Vertices of the intersection in counterclockwise order.

Linear programming¶

pypoman.lp.solve_lp(c: ndarray, G: ndarray, h: ndarray, A: ndarray | None = None, b: ndarray | None = None, solver: str | None = 'glpk') → ndarray¶

Solve a linear program (LP).

The linear program is defined by:

\[\begin{split}\mathrm{minimize} \ & c^T x \\ \mathrm{subject\ to} \ & G x \leq h \\ & A x = b\end{split}\]

using the CVXOPT interface to LP solvers.

Parameters:

c – Linear-cost vector.
G – Linear inequality constraint matrix.
h – Linear inequality constraint vector.
A – Linear equality constraint matrix.
b – Linear equality constraint vector.
solver – Solver to use, default is GLPK if available

Returns:

Optimal solution to the LP.

Raises:

ValueError – If the LP is not feasible.

Polygon manipulation¶

Functions on polygons, that is, 2D polyhedra.

pypoman.polygon.compute_polygon_hull(B: ndarray, c: ndarray) → List[ndarray]¶

Compute the vertex representation of a polygon.

The polygon is defined by:

\[B x \leq c\]

where \(x\) is a 2D vector.

Parameters:

B – Linear inequality matrix of size \(2 \times K\).
c – Linear inequality vector.

Returns:

List of 2D vertices in counterclockwise order.

pypoman.polygon.plot_polygon(points: ndarray, alpha: float = 0.4, color: str = 'g', linestyle: str = 'solid', fill: bool = True, linewidth: float | None = None, resize: bool = False) → None¶

Plot a polygon in matplotlib.

Parameters:

points – Array or list of points.
alpha – Transparency value.
color – Color in matplotlib format.
linestyle – Line style in matplotlib format.
fill – When True, fills the area inside the polygon.
linewidth – Line width in matplotlib format.
resize – When True, resets axis limits to center on the polygon.

Projection¶

Polytope projection functions.

pypoman.projection.project_point_to_polytope(point: ndarray, ineq: Tuple[ndarray, ndarray], qpsolver: str, **kwargs) → ndarray¶

Projet a point onto a polytope in H-representation.

Parameters:

point – Point to project.
ineq – Pair (A, b) describing the inequality constraint.
qpsolver – Name of the backend quadratic programming solver to use, to be picked in qpsolvers.available_solvers.

Returns:

Projected point.

Note

This function requires qpsolvers.

pypoman.projection.project_polyhedron(proj: Tuple[ndarray, ndarray], ineq: Tuple[ndarray, ndarray], eq: Tuple[ndarray, ndarray] | None = None, canonicalize: bool = True) → Tuple[List[ndarray], List[ndarray]]¶

Apply the affine projection \(y = E x + f\) to a polyhedron.

The polyhedron is defined by:

\[\begin{split}\begin{split}\begin{array}{ll} A x & \leq b \\ C x & = d \end{array}\end{split}\end{split}\]

Parameters:

proj – Pair (E, f) describing the affine projection.
ineq (pair of arrays) – Pair (A, b) describing the inequality constraint.
eq (pair of arrays, optional) – Pair (C, d) describing the equality constraint.
canonicalize (bool, optional) – Apply equality constraints from eq to reduce the dimension of the input polyhedron. May be a blessing or a curse, see notes below.

Returns:

vertices (list of arrays) – List of vertices of the projection.
rays (list of arrays) – List of rays of the projection.

Notes

When the equality set eq of the input polytope is not empty, it is usually faster to use these equality constraints to reduce the dimension of the input polytope (cdd function: canonicalize()) before enumerating vertices (cdd function: get_generators()). Yet, on some descriptions this operation may be problematic: if it fails, or if you get empty outputs when the output is supposed to be non-empty, you can try setting canonicalize=False.

References¶

[Boyd04]

Convex Optimization, Stephen Boyd and Lieven Vandenberghe, Cambridge University Press, 2004.

[Bretl08]

Testing Static Equilibrium for Legged Robots, T. Bretl and S. Lall, IEEE Transactions on Robotics, vol. 24, no. 4, pp. 794-807, August 2008.