Description |
This submission contains VERT2LCON and LCON2VERT, which will find the linear constraints defining a bounded polyhedron in R^n, given its vertices, or vice versa. They are extensions of Michael Kleder's VERT2CON and CON2VERT functions that can handle cases where the polyhedron is not solid in R^n. Points in a non-solid polyhedron satisfy both a set of inequalities A*x<=b and a set of equalities Aeq*x=beq. The inequalities define a solid polyhedron while the equalities define an affine set intersecting its interior (illustrated in 3D in the above screenshot). Some other refinements to the original VERT2CON and CON2VERT subroutines, meant to improve speed and reliability, have also been made.
SYNTAX:
[A,b,Aeq,beq]=VERT2LCON(V,TOL)
[V,nr,nre]=LCON2VERT(A,b,Aeq,beq,TOL)
The rows of the N x n matrix V are a series of N vertices of the polyhedron
in R^n, defined by the linear constraints
A*x <= b
Aeq*x = beq
For LCON2VERT, Aeq=beq=[] are the default inputs, implying no equality constraints. The output "nr" lists non-redundant inequality constraints, and "nre" lists non-redundant equality constraints.
It is to be emphasized that A,b must define a solid region, while Aeq and beq should be used to further constrain the region to a sub-manifold of R^n, if needed. You should not use the inequality constraints to express a region in R^n that can be described by equality constraints.
The optional TOL argument is a tolerance used for rank-estimation purposes and to handle finite precision issues. Default=1e-10.
EXAMPLE:
Consider the 3D polyhedron defined by x+y+z=1, x>=0, y>=0, z>=0.
>> [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
And the reverse conversion is,
>> 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
****
NEW as of 12/18/2103
QLCON2VERT has been added to the distribution as a quick version of LCON2VERT. QLCON2VERT needs to be passed a known point x0 in the relative interior of the polyhedron (see "help qlcon2vert"). This allows it to skip some intensive search steps sometimes needed in LCON2VERT. |