CON2VERT - constraints to vertices

Convert convex constraint inequalities into a set of vertices; i.e., polygon "vertex enumeration."


Updated 11 Jul 2005

No License

CON2VERT - convert a convex set of constraint inequalities into the set of vertices at the intersections of those inequalities;i.e., solve the "vertex enumeration" problem.

V = con2vert(A,b)

Converts the polytope (convex polygon, polyhedron, etc.) defined by the system of inequalities A*x <= b into a list of vertices V. Each ROW of V is a vertex. For n variables:
A = m x n matrix, where m >= n (m constraints, n variables)
b = m x 1 vector (m constraints)
V = p x n matrix (p vertices, n variables)

(1) This program emplyes a primal-dual polytope method.
(2) In dimensions higher than 2, duplicate vertices can appear using this method. This program detects duplicates at up to twelve digits of precision, then returns the unique vertices.
(3) Non-bounding constraints give erroneous results; therefore, the program detects non-bounding constraints and returns an error. You may wish to implement large "box" constraints on your variables if you need to induce bounding. For example, if x is a person's height in feet, the box constraint
-1 <= x <= 1000 would be a reasonable choice to induce boundedness, since no possible solution for x would be prohibited by the bounding box.
(4) This program requires that the feasible region have some finite extent in all dimensions. For example, the feasible region cannot be a line segment in 2-D space, or a plane in 3-D space.
(5) At least two dimensions are required.
(6) See companion function VERT2CON.
(7) Numerous examples are provided.
(8) ver 1.0: initial version, June 2005
(9) ver 1.1: enhanced redundancy checks, July 2005
(10) Written by Michael Kleder

Cite As

Michael Kleder (2023). CON2VERT - constraints to vertices (, MATLAB Central File Exchange. Retrieved .

MATLAB Release Compatibility
Created with R14SP1
Compatible with any release
Platform Compatibility
Windows macOS Linux
Find more on Computational Geometry in Help Center and MATLAB Answers

Community Treasure Hunt

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

Start Hunting!
Version Published Release Notes

Enhanced redundancy checks.