Representation

Polyhedra can be described in 2 different ways.

H-representation: As the intersection of finitely many halfspaces given by its facets.
V-representation: As the convex hull of its vertices + the conic hull of its rays where '+' is the Minkowski sum.

In Polyhedra.jl, those representations are given the respective abstract types HRepresentation and VRepresentation which are themself subtypes of Representation.

For instance, consider the 2-dimensional polyhedron described by the following H-representation:

\[\begin{align*} x_1 + x_2 &\leq 1 \\ x_1 - x_2 &\leq 0 \\ x_1 & \geq 0. \end{align*}\]

This set of inequalities can be written in the matrix form $Ax \leq b$ where

\[A = \begin{pmatrix}1 & 1\\1 & -1\\-1 & 0\end{pmatrix}, b = \begin{pmatrix}1\\0\\0\end{pmatrix}.\]

Let's create this H-representation using the concrete subtype SimpleHRepresentation of the abstract type HRepresentation.

julia> using Polyhedra
julia> A = [1 1;1 -1;-1 0]
julia> b = [1,0,0]
julia> hrep = SimpleHRepresentation(A, b)
julia> typeof(hrep)
Polyhedra.SimpleHRepresentation{2,Int64}

This polyhedron has three vertices: $(0,0)$, $(0,1)$ and $(0.5,0.5)$. We can create this V-representation using the concrete subtype SimpleVRepresentation of the abstract type VRepresentation. Because $0.5$ is fractional, have two choices: either use exact rational arithemtic

julia> V = [0 0; 0 1; 1//2 1//2]
julia> vrep = SimpleVRepresentation(V)
julia> typeof(vrep)
Polyhedra.SimpleVRepresentation{2,Rational{Int64}}

or use floating point arithmetic

julia> Vf = [0 0; 0 1; 1/2 1/2]
julia> vrepf = SimpleVRepresentation(Vf)
julia> typeof(vrepf)
Polyhedra.SimpleVRepresentation{2,Float64}

Representation interface

These functions can be called on both H-representation and V-representation

Polyhedra.fulldim — Function.

fulldim(rep::Rep)

Returns the dimension of the space in which the representation is defined. That is, a straight line in a 3D space has fulldim 3.

H-representation interface

Polyhedra.hreps — Function.

hreps(hr::HRep)

Returns an iterator over the elements of the H-representation.

Note

This is type unstable as the iterator returns both halfspaces and hyperplanes. It is therefore more efficient to call eqs and ineqs separately.

Polyhedra.nhreps — Function.

nhreps(hr::HRep)

Returns the number of halfspaces and hyperplanes of the H-representation.

Note

Note that it does not do redundancy removal so it is not the minimal number of halfspace and hyperplanes needed to represent the polyhedron, it is simply the number that are currently used.

Polyhedra.hashreps — Function.

hashreps(hr::HRep)

Returns whether the H-representation contain any halfspace or hyperplane.

Polyhedra.eqs — Function.

eqs(hr::HRep)

Returns an iterator over the hyperplanes of the H-representation.

Polyhedra.neqs — Function.

neqs(hr::HRep)

Returns the number of hyperplanes of the H-representation.

Polyhedra.haseqs — Function.

haseqs(hr::HRep)

Returns whether the H-representation contain any hyperplane.

Polyhedra.ineqs — Function.

ineqs(hr::HRep)

Returns an iterator over the halfspaces of the H-representation.

Polyhedra.nineqs — Function.

nineqs(hr::HRep)

Returns the number of halfspaces of the H-representation.

Polyhedra.hasineqs — Function.

hasineqs(hr::HRep)

Returns whether the H-representation contain any halfspace.

Polyhedra.hrepiscomputed — Function.

hrepiscomputed(p::Polyhedron)

Returns whether the H-representation of this polyhedron has been computed.

V-representation interface

Polyhedra.vreps — Function.

vreps(vr::VRep)

Returns an iterator over the elements of the V-representation.

Note

This is type unstable as the iterator returns both points and rays. It is therefore more efficient to call points and rays separately.

Polyhedra.nvreps — Function.

nvreps(vr::VRep)

Returns the number of points and rays of the V-representation.

Note

Note that it does not do redundancy removal so it is not the minimal number of points and rays needed to represent the polyhedron, it is simply the number that are currently used.

Polyhedra.hasvreps — Function.

hasvreps(vr::VRep)

Returns whether the V-representation contain any ray or point.

Polyhedra.rays — Function.

rays(vr::VRep)

Returns an iterator over the rays of the V-representation.

Polyhedra.nrays — Function.

nrays(hr::HRep)

Returns the number of rays of the V-representation.

Polyhedra.hasrays — Function.

hasrays(vr::VRep)

Returns whether the V-representation contain any ray.

Polyhedra.points — Function.

points(vr::VRep)

Returns an iterator over the points of the V-representation.

Polyhedra.npoints — Function.

npoints(vr::VRep)

Returns the number of points of the V-representation.

Polyhedra.haspoints — Function.

haspoints(vr::VRep)

Returns whether the V-representation contain any point.

Polyhedra.vrepiscomputed — Function.

vrepiscomputed(p::Polyhedron)

Returns whether the V-representation of this polyhedron has been computed.