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, alpha=0.4, color='g', linestyle='solid', fill=True, linewidth=None, resize=False)

Plot a polygon in matplotlib.

Parameters:
• points (list of arrays) – List of poitns.

• alpha (scalar, optional) – Transparency value.

• color (string, optional) – Color in matplotlib format.

• linestyle (scalar, optional) – Line style in matplotlib format.

• fill (bool, optional) – When True, fills the area inside the polygon.

• linewidth (scalar, optional) – Line width in matplotlib format.

• resize (bool, optional) – When True, resets axis limits to center on the polygon.

# Projection¶

Polytope projection functions.

Projet a point onto a polytope in H-representation.

Parameters:
• point (array) – Point to project.

• ineq (pair of arrays) – Pair (A, b) describing the inequality constraint.

• solver (string) – Name of the quadratic programming solver to use.

Returns:

projection – Projected point.

Return type:

array

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.

This

pypoman.projection.project_polytope(proj, ineq, eq=None, method='cdd', **kwargs)

Apply the affine projection $$y = E x + f$$ to a polytope.

The polytope is defined by:

$\begin{split}A x & \leq b \\ C x & = d\end{split}$
Parameters:
• proj (pair of arrays) – 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.

• method (string, optional) – Choice between ‘bretl’ and ‘cdd’.

Returns:

vertices – List of vertices of the projection.

Return type:

list of arrays

Note

Additional keyword arguments can be provided when the method is ‘bretl’. They are passed directly to the corresponding function pypoman.projection.project_polytope_bretl().

Notes

The number of columns of all matrices A, C and E corresponds to the dimension of the input space, while the number of lines of E corresponds to the dimension of the output space.

pypoman.projection.project_polytope_bretl(proj, ineq, eq, max_radius=100000.0, max_iter=1000, init_angle=None)

Project a polytope into a 2D polygon using the IP algorithm.

The incremental projection algorithm is detailed in [Bretl08]. The 2D affine projection $$y = E x + f$$ is applied to the polyhedron defined by:

$\begin{split}A x & \leq b \\ C x & = d\end{split}$
Parameters:
• proj (pair of arrays) – 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.

• max_radius (scalar, optional) – Maximum distance from origin (in [m]) used to make sure the output is bounded.

• max_iter (integer, optional) – Maximum number of calls to the LP solver.

• init_angle (scalar, optional) – Angle in [rad] giving the direction of the initial ray cast.

Returns:

vertices – List of vertices of the projected polygon.

Return type:

list of arrays

# 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.