File Exchange

image thumbnail

Analyze N-dimensional Convex Polyhedra

version 1.9.0.2 (14.9 KB) by Matt J
Find vertex or (in)equality forms of convex polyhedra in R^n (for n not super large). Also, compute their intersections and unions.

5K Downloads

Updated 21 Mar 2021

View License

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,
A*x<=b,
Aeq*x=beq

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.


EXAMPLE:

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,


>> [A,b,Aeq,beq]=vert2lcon(eye(3))

A =

0.4082 -0.8165 0.4082
0.4082 0.4082 -0.8165
-0.8165 0.4082 0.4082


b =

0.4082
0.4082
0.4082


Aeq =

0.5774 0.5774 0.5774


beq =

0.5774

Conversely, the vertices can be obtained by doing,

>> V=lcon2vert(A,b,Aeq,beq)

V =

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.

Cite As

Matt J (2021). 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
Created with R2010b
Compatible with any release
Platform Compatibility
Windows macOS Linux

Community Treasure Hunt

Find the treasures in MATLAB Central and discover how the community can help you!

Start Hunting!