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.
Polyhedra.HRepresentation
— TypeHRepresentation{T<:Real}
Supertype for H-representations with coefficient type T
.
Polyhedra.VRepresentation
— TypeVRepresentation{T<:Real}
Supertype for V-representations coefficient type T
.
Polyhedra.Representation
— TypeRepresentation{T<:Real}
Supertype for H-(or V-)representations with coefficient type T
.
In Polyhedra.jl
, those representations are given the respective abstract types HRepresentation
and VRepresentation
which are themself subtypes of Representation
.
These functions can be called on both H-representation and V-representation
Polyhedra.fulldim
— Functionfulldim(rep::Rep)::Int
Returns the dimension of the space in which polyhedron, representation, element or vector is defined. That is, a straight line in a 3D space has fulldim
3 even if its dimension is 1.
Polyhedra.FullDim
— TypeFullDim(p)::FullDim
Similar to fulldim
but used for type stability with the vector type. If the vector type is StaticArrays.SVector
then it returns a StaticArrays.Size
.
Polyhedra.coefficient_type
— Functioncoefficient_type(rep::Rep)
Returns the type of the coefficients used in the representation of rep
.
H-representation
The fundamental element of an H-representation is the halfspace
Polyhedra.HalfSpace
— Typestruct HalfSpace{T, AT} <: HRepElement{T, AT}
a::AT
β::T
end
An halfspace defined by the set of points $x$ such that $\langle a, x \rangle \le \beta$.
An H-representation can be created as the intersection of several halfspaces. For instance, the polytope
\[\begin{aligned} x_1 + x_2 &\leq 1 \\ x_1 - x_2 &\leq 0 \\ x_1 & \geq 0. \end{aligned}\]
can be created as follows:
HalfSpace([1, 1], 1) ∩ HalfSpace([1, -1], 0) ∩ HalfSpace([-1, 0], 0)
Even if HalfSpace
s are enough to describe any polyhedron, it is sometimes important to represent the fact that the polyhedron is contained in an affine subspace. For instance, the simplex
\[\begin{aligned} x_1 + x_2 &= 1 \\ x_1 &\geq 0 \\ x_2 &\geq 0 \end{aligned}\]
is 1-dimensional even if it is defined in a 2-dimensional space.
The fundamental element of an affine subspace is the hyperplane
Polyhedra.HyperPlane
— Typestruct HyperPlane{T, AT} <: HRepElement{T, AT}
a::AT
β::T
end
An hyperplane defined by the set of points $x$ such that $\langle a, x \rangle = \beta$.
An affine subspace can be created as the intersection of several hyperplanes. For instance
HyperPlane([1, 1], 1) ∩ HyperPlane([1, 0], 0)
represents the 0-dimensional affine subspace only containing the point $(0, 1)$.
To represent a polyhedron that is not full-dimensional, hyperplanes and halfspaces can be mixed in any order. For instance, the simplex defined above can be obtained as follows:
HalfSpace([-1, 0], 0) ∩ HyperPlane([1, 1], 1) ∩ HalfSpace([0, -1], 0)
In addition to being created incrementally with intersections, an H-representation can also be created using the hrep
function. The hrep
function is also used to query the H-representation of a given polyhedron.
Polyhedra.hrep
— Functionhrep(p::Polyhedron)
Returns an H-representation for the polyhedron p
.
hrep(hyperplanes::HyperPlaneIt; d::FullDim)
Creates an affine space of full dimension d
from the list of hyperplanes hyperplanes
.
Examples
hrep([HyperPlane([0, 1, 0], 1), HyperPlane([0, 0, 1], 0)])
creates the 1-dimensional affine subspace containing all the points $(x_1, 0, 0)$, i.e. the $x_1$-axis.
hrep([HyperPlane([1, 1], 1), HyperPlane([1, 0], 0)])
creates the 0-dimensional affine subspace only containing the point $(0, 1)$.
hrep(hyperplanes::HyperPlaneIt, halfspaces::HalfSpaceIt; d::FullDim)
Creates an H-representation for the polyhedron of full dimension d
equal to the intersection of the hyperplanes hyperplanes
and halfspaces halfspaces
.
Examples
For instance, the simplex
\[\begin{aligned} x_1 + x_2 &= 1 \\ x_1 &\geq 0 \\ x_2 &\geq 0 \end{aligned}\]
can be created as follows:
julia> hrep([HyperPlane([1, 1], 1)], [HalfSpace([0, -1], 0), HalfSpace([-1, 0], 0)])
H-representation Polyhedra.Intersection{Int64, Vector{Int64}, Int64}:
1-element iterator of HyperPlane{Int64, Vector{Int64}}:
HyperPlane([1, 1], 1),
2-element iterator of HalfSpace{Int64, Vector{Int64}}:
HalfSpace([0, -1], 0)
HalfSpace([-1, 0], 0)
hrep(halfspaces::HalfSpaceIt; d::FullDim)
Creates an H-representation for the polyhedron of full dimension d
equal to the intersection of the halfspaces halfspaces
.
Examples
For instance, the polytope
\[\begin{aligned} x_1 + x_2 &\leq 1 \\ x_1 - x_2 &\leq 0 \\ x_1 & \geq 0. \end{aligned}\]
can be created as follows:
hrep([HalfSpace([1, 1], 1), HalfSpace([1, -1], 0), HalfSpace([-1, 0], 0)])
hrep(A::AbstractMatrix, b::AbstractVector, linset::BitSet=BitSet())
Creates an H-representation for the polyhedron defined by the inequalities $\langle A_i, x \rangle = b_i$ if i in linset
and $\langle A_i, x \rangle \le b_i$ otherwise where $A_i$ is the $i$th row of A
, i.e. A[i,:]
and $b_i$ is b[i]
.
The H-representation of a given polyhedron can be altered with the Polyhedra.resethrep!
and Polyhedra.sethrep!
. Use Polyhedra.sethrep!
with caution as it does not invalidate the V-representation! Use Polyhedra.resethrep!
in case you are unsure on which one to use.
Polyhedra.resethrep!
— FunctionPolyhedra.resethrep!(p::Polyhedron, h::HRepresentation, redundancy::Redundancy = UNKNOWN_REDUNDANCY)
Reset the H-representation of p
to h
. The redundancy of p
is assumed to be redundancy
; see Polyhedra.Redundancy
.
The representation is not assumed to be a valid representation for p
so it invalidates the V-representation of p
. Use Polyhedra.sethrep!
if h
is known to be a valid representation for p
.
Polyhedra.sethrep!
— FunctionPolyhedra.sethrep!(p::Polyhedron, h::HRepresentation, redundancy::Redundancy = UNKNOWN_REDUNDANCY)
Reset the H-representation of p
to h
. The redundancy of p
is assumed to be redundancy
; see Polyhedra.Redundancy
.
The representation is assumed to be a valid representation for p
so it does not invalidate the V-representation of p
if it was already computed previously. Use Polyhedra.resethrep!
if h
is not known to be a valid representation for p
.
Interface
An H-representation is represented as an intersection halfspaces and hyperplanes. The halfspaces can be obtained with halfspaces
and the hyperplanes with hyperplanes
. As an hyperplane $\langle a, x \rangle = \beta$ is the intersection of the two halfspaces $\langle a, x \rangle \le \beta$ and $\langle a, x \rangle \ge \beta$, even if the H-representation contains hyperplanes, a list of halfspaces whose intersection is the polyhedron can be obtained with allhalfspaces
, which has nhalfspaces(p) + 2nhyperplanes(p)
elements for an H-representation p
since each hyperplane is split in two halfspaces.
Polyhedra.halfspaces
— Functionhalfspaces(hrep::HRep)
Returns an iterator over the halfspaces of the H-representation hrep
.
Polyhedra.nhalfspaces
— Functionnhalfspaces(hrep::HRep)
Returns the number of halfspaces of the H-representation hrep
.
Polyhedra.hashalfspaces
— Functionhashalfspaces(hrep::HRep)
Returns whether the H-representation hrep
has any halfspace.
Polyhedra.hyperplanes
— Functionhyperplanes(hrep::HRep)
Returns an iterator over the hyperplanes of the H-representation hrep
.
Polyhedra.nhyperplanes
— Functionnhyperplanes(hrep::HRep)
Returns the number of hyperplanes of the H-representation hrep
.
Polyhedra.hashyperplanes
— Functionhashyperplanes(hrep::HRep)
Returns whether the H-representation hrep
has any hyperplane.
Polyhedra.allhalfspaces
— Functionallhalfspaces(hrep::HRep)
Returns an iterator over the halfspaces and hyperplanes in the H-representation hrep
splitting hyperplanes in two halfspaces.
Examples
hrep = HyperPlane([1, 0], 1) ∩ HalfSpace([0, 1], 1)
collect(allhalfspaces(hrep)) # Returns [HalfSpace([1, 0]), HalfSpace([-1, 0]), HalfSpace([0, 1])]
Polyhedra.nallhalfspaces
— Functionnallhalfspaces(hrep::HRep)
Returns the number of halfspaces plus twice the number of hyperplanes in the H-representation hrep
, i.e. length(allhalfspaces(hrep))
Polyhedra.hasallhalfspaces
— Functionhasallhalfspaces(hrep::HRep)
Returns whether the H-representation hrep
contains any halfspace or hyperplane.
V-representation
The fundamental elements of an V-representation are the points (represented by AbstractVector
s and and rays
Polyhedra.Ray
— Typestruct Ray{T, AT <: AbstractVector{T}}
a::AT
end
The conic hull of a
, i.e. the set of points λa
where λ
is any nonnegative real number.
A V-representation can be created as the minkowski sum between a convex hull of points and a conic hull of rays. For instance, the positive orthant without the simplex defined in the H-representation section can be created as follows:
convexhull([1, 0], [0, 1]) + conichull([1, 0], [0, 1])
The V-representation represents the polyhedron as a minkowski sum of a polytope and a polyhedral cone. The polytope is represented using a P-representation : a convex hull of points. The polyhedral cone is represented using an R-representation : a conic hull of rays.
Even if rays are enough to describe any polyhedral cone, it is sometimes important to represent the fact that the polyhedron contains an affine subspace. For instance, the polyhedron created with
convexhull([1, 0], [0, 1]) + conichull([1, 1], [-1, -1])
contains the line [1, 1]
.
The fundamental element of an affine subspace is the line
Polyhedra.Line
— Typestruct Line{T, AT <: AbstractVector{T}}
a::AT
end
The conic hull of a
and -a
, i.e. the set of points λa
where λ
is any real number.
An affine subspace can be created as the conic hull/minkownski sum of several lines. For instance
conichull(Line([1, 0]), Line([0, 1]))
represents the full space.
In addition to being created incrementally with convex hull and minkowsky addition, a V-representation can also be created using the vrep
function. The vrep
function is also used to query the V-representation of a given polyhedron.
Polyhedra.vrep
— Functionvrep(p::Polyhedron)
Returns a V-representation for the polyhedron p
.
vrep(lines::LineIt; d::FullDim)
Creates an affine space of full dimension d
from the list of lines lines
.
Examples
vrep([Line([1, 0, 0]), Line([0, 1, 0])])
creates the 2-dimensional affine subspace containing all the points $(x_1, x_2, 0)$, i.e. the $x_1$$x_2$-plane.
vrep(points::PointIt; d::FullDim)
Creates a V-representation for the polytope of full dimension d
equal to the convex hull of the points points
.
Examples
The convex hull of $(0, 0)$, $(0, 1)$ and $(1/2, 1/2)$ can be created as follows using exact arithmetic
vrep([[0, 0], [0, 1], [1//2, 1//2]])
or as follows using floating point arithmetic
vrep([[0, 0], [0, 1], [1/2, 1/2]])
vrep(lines::LineIt, rays::RayIt; d::FullDim)
Creates a V-representation for the polyhedral cone of full dimension d
equal to the conic hull of the lines lines
and rays rays
.
Examples
vrep([Line([0, 1])], [Ray([1, 0])])
creates a V-representation for the halfspace $x_1 \ge 0$.
vrep(rays::RayIt)
Creates a V-representation for the polyhedral cone of full dimension d
equal to the conic hull of the rays rays
.
Examples
vrep([Ray([1, 0]), Ray([0, 1])])
creates a V-representation for positive orthant.
vrep(points::PointIt, lines::LineIt, rays::RayIt;
d = Polyhedra.FullDim_rec(points, lines, rays))
Creates a V-representation for the polyhedron of full dimension d
equal to the minkowski sum of the convex hull of points
with the conic hull of lines
and rays
.
vrep(V::AbstractMatrix, R::AbstractMatrix, Rlinset::BitSet=BitSet())
Creates a V-representation for the polyhedron defined by the points $V_i$, lines $R_i$ if i in Rlinset
and rays $R_i$ otherwise where $V_i$ (resp. $R_i$) is the $i$th row of V
(resp. R
), i.e. V[i,:]
(resp. R[i,:]
).
The H-representation of a given polyhedron can be altered with the Polyhedra.resetvrep!
and Polyhedra.setvrep!
. Use Polyhedra.setvrep!
with caution as it does not invalidate the V-representation! Use Polyhedra.resetvrep!
in case you are unsure on which one to use.
Polyhedra.resetvrep!
— FunctionPolyhedra.resetvrep!(p::Polyhedron, v::VRepresentation, redundancy::Redundancy = UNKNOWN_REDUNDANCY)
Reset the V-representation of p
to v
. The redundancy of p
is assumed to be redundancy
; see Polyhedra.Redundancy
.
The representation is not assumed to be a valid representation for p
so it invalidates the H-representation of p
. Use Polyhedra.setvrep!
if v
is known to be a valid representation for p
.
Polyhedra.setvrep!
— FunctionPolyhedra.setvrep!(p::Polyhedron, v::HRepresentation, redundancy::Redundancy = UNKNOWN_REDUNDANCY)
Reset the H-representation of p
to v
. The redundancy of p
is assumed to be redundancy
; see Polyhedra.Redundancy
.
The representation is assumed to be a valid representation for p
so it does not invalidate the H-representation of p
if it was already computed previously. Use Polyhedra.resetvrep!
if v
is not known to be a valid representation for p
.
Interface
A P-representation is represented as a convex hull points. The points can be obtained with points
.
Polyhedra.points
— Functionpoints(vrep::VRep)
Returns an iterator over the points of the V-representation vrep
.
Polyhedra.npoints
— Functionnpoints(vrep::VRep)
Returns the number of points of the V-representation vrep
.
Polyhedra.haspoints
— Functionhaspoints(vrep::VRep)
Returns whether the V-representation vrep
has any point.
An R-representation is represented as a conic hull of lines and rays. The rays can be obtained with rays
and the lines with lines
. As a line $r$ is the conic hull of of the two rays $r$ and $-r$, even if the R-representation contains lines, a list of rays whose conic hull is the polyhedral cone can be obtained with allrays
, which has nrays(R) + 2nlines(R)
elements for an R-representation R
since each line is split in two rays.
Polyhedra.rays
— Functionrays(vrep::VRep)
Returns an iterator over the rays of the V-representation vrep
.
Polyhedra.nrays
— Functionnrays(vrep::VRep)
Returns the number of rays of the V-representation vrep
.
Polyhedra.hasrays
— Functionhasrays(vrep::VRep)
Returns whether the V-representation vrep
has any ray.
Polyhedra.lines
— Functionlines(vrep::VRep)
Returns an iterator over the lines of the V-representation vrep
.
Polyhedra.nlines
— Functionnlines(vrep::VRep)
Returns the number of lines of the V-representation vrep
.
Polyhedra.haslines
— Functionhaslines(vrep::VRep)
Returns whether the V-representation vrep
has any line.
Polyhedra.allrays
— Functionallrays(vrep::VRep)
Returns an iterator over the rays and lines in the V-representation vrep
splitting lines in two rays.
Examples
vrep = Line([1, 0]) + Ray([0, 1])
collect(allrays(vrep)) # Returns [Ray([1, 0]), Ray([-1, 0]), Ray([0, 1])]
Polyhedra.nallrays
— Functionnallrays(vrep::VRep)
Returns the number of rays plus twice the number of lines in the V-representation vrep
, i.e. length(allrays(vrep))
Polyhedra.hasallrays
— Functionhasallrays(vrep::VRep)
Returns whether the V-representation vrep
contains any ray or line.