This submission contains a set of files for analyzing N-dimensional convex polyhedra. It is intended for fairly low dimensions N -- basically low enough so that vertex and facet enumeration using MATLAB's convhulln() command is tractable. For now, it is also limited to bounded polyhedra (i.e., polytopes). A bounded convex polyhedron can be represented either as the convex hull of a finite set of vertices V(i,:) or by using a combination of linear constraint equalities and inequalities,
Here, A and Aeq are MxN and PxN matrices while b and beq are Mx1 and Px1 column vectors, respectively. The (in)equality representation expresses the polyhedron as the intersection of two regions. One region is a solid N-dimensional shape, described by the inequalities, while the other is a possibly lower-dimensional sub-space, described by the equalities. The screenshot above illustrates this, showing how a triangle in 3D can be represented as the intersection of a tetrahedron (a solid shape in R^3) and a plane.
The package contains tools for converting between the two representations (see VERT2LCON and LCON2VERT) as well as for taking intersections and unions of polyhedra in either form (see intersectionHull and unionHull).
The package was inspired by Michael Kleder's vert2con and con2vert functions, which were limited to N-dimensional polyhedra possessing non-zero volume in R^N.Thus, for example, they could not handle a triangle floating in R^3 as depicted in the above screenshot. Although a triangle has non-zero volume (i.e., area) in R^2 it has zero volume in R^3. The extension made in this package covers general bounded polyhedra. NOTE: however, when using linear constraint data A, b, Aeq, beq to represent a given polyhedron, it is important that the inequalities A*x<=b still be chosen to correspond with a region of non-zero N-dimensional volume. Zero-volume polyhedra are captured by adding equality constraints Aeq*x=beq.
Consider the 3D polyhedron defined by x+y+z=1, x>=0, y>=0, z>=0. Equivalent constraint in/equalities can be obtained from the known vertices by doing,
0.4082 -0.8165 0.4082
0.4082 0.4082 -0.8165
-0.8165 0.4082 0.4082
0.5774 0.5774 0.5774
Conversely, the vertices can be obtained by doing,
1.0000 0.0000 0.0000
0.0000 0.0000 1.0000
-0.0000 1.0000 0.0000
When an interior point of the polyhedron is known a priori, one can instead use QLCON2VERT, a quicker version of LCON2VERT which uses the known point to get around some computationally intensive steps.
Matt J (2023). Analyze N-dimensional Convex Polyhedra (https://www.mathworks.com/matlabcentral/fileexchange/30892-analyze-n-dimensional-convex-polyhedra), MATLAB Central File Exchange. Retrieved .
MATLAB Release Compatibility
Platform CompatibilityWindows macOS Linux
Community Treasure Hunt
Find the treasures in MATLAB Central and discover how the community can help you!Start Hunting!
Edited descriptive text
Editing of descriptive text only.
Bug fix - the case where the equality constraint system Aeq*x=beq had a unique solution was not handled properly
Minor grammatical and spelling edits to description page.
* improved error checking in lcon2vert
If lcon2vert fails to find an initial interior point after many iterations of the alg it uses, it will now quit with V=.
Various bug fixes and improvements in robustness. These address failure cases discovered recently by users.
*Further robustness of lcon2vert
Improved the reliability of CON2VERT subroutine, both in terms of performance and of error reporting.
added LCON2VERT which does the inverse of VERT2CON