Polytope in vertex representation (VPolytope)

LazySets.VPolytopeModule.VPolytopeType
VPolytope{N, VN<:AbstractVector{N}, VT<:AbstractVector{VN}} <: AbstractPolytope{N}

Type that represents a convex polytope in vertex representation.

Fields

  • vertices – list of vertices

Examples

A polytope in vertex representation can be constructed by passing the list of vertices. For example, we can build the tetrahedron:

julia> P = VPolytope([[0, 0, 0], [1, 0, 0], [0, 1, 0], [0, 0, 1]]);

julia> P.vertices
4-element Vector{Vector{Int64}}:
 [0, 0, 0]
 [1, 0, 0]
 [0, 1, 0]
 [0, 0, 1]

Alternatively, a VPolytope can be constructed passing a matrix of vertices, where each column represents a vertex:

julia> M = [0 0 0; 1 0 0; 0 1 0; 0 0 1]'
3×4 adjoint(::Matrix{Int64}) with eltype Int64:
 0  1  0  0
 0  0  1  0
 0  0  0  1

julia> P = VPolytope(M);

julia> P.vertices
4-element Vector{Vector{Int64}}:
 [0, 0, 0]
 [1, 0, 0]
 [0, 1, 0]
 [0, 0, 1]
source

Conversion

Base.convertMethod
convert(::Type{VPolytope}, X::LazySet; [prune]::Bool=true)

Convert a polytopic set to a polytope in vertex representation.

Input

  • VPolytope – target type
  • X – polytopic set
  • prune – (optional, default: true) option to remove redundant vertices

Output

The given set represented as a polytope in vertex representation.

Algorithm

This method uses vertices_list. Use the option prune to select whether to remove redundant vertices before constructing the polytope.

source

Operations

LazySets.API.constraints_listMethod
constraints_list(P::VPolytope)

Return a list of constraints defining a polytope in vertex representation.

Input

  • P – polytope in vertex representation

Output

A list of constraints of the polytope.

Algorithm

We use tohrep to compute the constraint representation of P.

source
LazySets.API.dimMethod
dim(P::VPolytope)

Return the dimension of a polytope in vertex representation.

Input

  • P – polytope in vertex representation

Output

The ambient dimension of the polytope in vertex representation. If P is empty, the result is $-1$.

Examples

julia> P = VPolytope();

julia> isempty(P.vertices)
true

julia> dim(P)
-1

julia> P = VPolytope([ones(3)]);

julia> P.vertices
1-element Vector{Vector{Float64}}:
 [1.0, 1.0, 1.0]

julia> dim(P) == 3
true
source
Polyhedra.polyhedronMethod
polyhedron(P::VPolytope;
           [backend]=default_polyhedra_backend(P),
           [relative_dimension]=nothing)

Return a VRep polyhedron from Polyhedra.jl given a polytope in vertex representation.

Input

  • P – polytope in vertex representation
  • backend – (optional, default: default_polyhedra_backend(P)) the backend for polyhedral computations; see Polyhedra's documentation for further information
  • relative_dimension – (default, optional: nothing) an integer representing the (relative) dimension of the polytope; this argument is mandatory if the polytope is empty

Output

A VRep polyhedron.

Notes

The relative dimension (or just dimension) refers to the dimension of the set relative to itself, independently of the ambient dimension. For example, a point has (relative) dimension zero, and a line segment has (relative) dimension one.

In this library, LazySets.dim always returns the ambient dimension of the set, such that a line segment in two dimensions has dimension two. However, Polyhedra.dim will assign a dimension equal to one to a line segment because it uses a different convention.

source
Base.randMethod
rand(::Type{VPolytope}; [N]::Type{<:Real}=Float64, [dim]::Int=2,
     [rng]::AbstractRNG=GLOBAL_RNG, [seed]::Union{Int, Nothing}=nothing,
     [num_vertices]::Int=-1)

Create a random polytope in vertex representation.

Input

  • VPolytope – type for dispatch
  • N – (optional, default: Float64) numeric type
  • dim – (optional, default: 2) dimension
  • rng – (optional, default: GLOBAL_RNG) random number generator
  • seed – (optional, default: nothing) seed for reseeding
  • num_vertices – (optional, default: -1) upper bound on the number of vertices of the polytope (see comment below)

Output

A random polytope in vertex representation.

Algorithm

All numbers are normally distributed with mean 0 and standard deviation 1.

The number of vertices can be controlled with the argument num_vertices. For a negative value we choose a random number in the range dim:5*dim (except if dim == 1, in which case we choose in the range 1:2). Note that we do not guarantee that the vertices are not redundant.

source
LazySets.remove_redundant_verticesMethod
remove_redundant_vertices(P::VPolytope{N};
                          [backend]=nothing,
                          [solver]=nothing) where {N}

Return the polytope obtained by removing the redundant vertices of the given polytope in vertex representation.

Input

  • P – polytope in vertex representation
  • backend – (optional, default: nothing) the backend for polyhedral computations; see default_polyhedra_backend(P) or Polyhedra's documentation for further information
  • solver – (optional, default: nothing) the linear programming solver used in the backend, if needed; see default_lp_solver_polyhedra(N)

Output

A new polytope such that its vertices are the convex hull of the given polytope.

Notes

The optimization problem associated to removing redundant vertices is handled by Polyhedra. If the polyhedral computations backend requires an LP solver, but it has not been specified, we use default_lp_solver_polyhedra(N) to define such solver. Otherwise, the redundancy-removal function of the polyhedral backend is used.

source
LazySets.API.reflectMethod
reflect(P::VPolytope)

Concrete reflection of a polytope in vertex representation P, resulting in the reflected set -P.

Input

  • P – polytope in vertex representation

Output

The VPolytope representing -P.

source
LazySets.tohrepMethod
tohrep(P::VPolytope{N};
       [backend]=default_polyhedra_backend(P)) where {N}

Transform a polytope in vertex representation to a polytope in constraint representation.

Input

  • P – polytope in vertex representation
  • backend – (optional, default: default_polyhedra_backend(P)) the backend for polyhedral computations; see Polyhedra's documentation for further information

Output

A HPolytope as the constraint representation of P.

Notes

The conversion may not preserve the numeric type (e.g., with N == Float32) depending on the backend.

source
LazySets.tovrepMethod
tovrep(P::VPolytope)

Return a vertex representation of the given polytope in vertex representation (no-op).

Input

  • P – polytope in vertex representation

Output

The same polytope instance.

source
LazySets.API.vertices_listMethod
vertices_list(P::VPolytope)

Return the list of vertices of a polytope in vertex representation.

Input

  • P – polytope in vertex representation

Output

The list of vertices.

source
LazySets.API.linear_mapMethod
linear_map(M::AbstractMatrix, P::VPolytope; [apply_convex_hull]::Bool=false)

Concrete linear map of a polytope in vertex representation.

Input

  • M – matrix
  • P – polytope in vertex representation
  • apply_convex_hull – (optional, default: false) flag for applying a convex hull to eliminate redundant vertices

Output

A polytope in vertex representation.

Algorithm

The linear map $M$ is applied to each vertex of the given set $P$, obtaining a polytope in vertex representation. The output type is again a VPolytope.

source
Base.:∈Method
∈(x::AbstractVector{N}, P::VPolytope{N};
  solver=default_lp_solver(N)) where {N}

Check whether a given point is contained in a polytope in vertex representation.

Input

  • x – point/vector
  • P – polytope in vertex representation
  • solver – (optional, default: default_lp_solver(N)) the backend used to solve the linear program

Output

true iff $x ∈ P$.

Algorithm

We check, using linear programming, the definition of a convex polytope that a point is in the set if and only if it is a convex combination of the vertices.

Let $\{v_j\}$ be the $m$ vertices of P. Then we solve the following $m$-dimensional linear program.

\[\max 0 \text{ s.t. } ⋀_{i=1}^n ∑_{j=1}^m λ_j v_j[i] = x[i] ∧ ∑_{j=1}^m λ_j = 1 ∧ ⋀_{j=1}^m λ_j ≥ 0\]

source
LazySets.API.ρMethod
ρ(d::AbstractVector, P::VPolytope)

Evaluate the support function of a polytope in vertex representation in a given direction.

Input

  • d – direction
  • P – polytope in vertex representation

Output

Evaluation of the support function in the given direction.

source
LazySets.API.σMethod
σ(d::AbstractVector, P::VPolytope)

Return a support vector of a polytope in vertex representation in a given direction.

Input

  • d – direction
  • P – polytope in vertex representation

Output

A support vector in the given direction.

Algorithm

A support vector maximizes the support function. For a polytope, the support function is always maximized in some vertex. Hence it is sufficient to check all vertices.

source
LazySets.API.translateMethod
translate(P::VPolytope, v::AbstractVector)

Translate (i.e., shift) a polytope in vertex representation by a given vector.

Input

  • P – polytope in vertex representation
  • v – translation vector

Output

A translated polytope in vertex representation.

Notes

See translate!(::VPolytope, ::AbstractVector) for the in-place version.

source
LazySets.API.translate!Method
translate!(P::VPolytope, v::AbstractVector)

Translate (i.e., shift) a polytope in vertex representation by a given vector, in-place.

Input

  • P – polytope in vertex representation
  • v – translation vector

Output

The polytope P translated by v.

Notes

See translate(::VPolytope, ::AbstractVector) for the out-of-place version.

Algorithm

We add the vector to each vertex of the polytope.

source
LazySets.API.cartesian_productMethod
cartesian_product(P1::VPolytope, P2::VPolytope; [backend]=nothing)

Compute the Cartesian product of two polytopes in vertex representation.

Input

  • P1 – polytope in vertex representation
  • P2 – polytope in vertex representation
  • backend – (optional, default: nothing) backend for polyhedral computation

Output

The VPolytope obtained by the concrete Cartesian product of P1 and P2.

Notes

For further information on the supported backends see Polyhedra's documentation.

source
LazySets.API.convex_hullMethod
convex_hull(P1::VPolytope, P2::VPolytope; [backend]=nothing)

Compute the convex hull of two polytopes in vertex representation.

Input

  • P1 – polytope in vertex representation
  • P2 – polytope in vertex representation
  • backend – (optional, default: nothing) the polyhedral computation backend

Output

The VPolytope obtained by the concrete convex hull of P1 and P2.

Notes

This function takes the union of the vertices of each polytope and then relies on a concrete convex-hull algorithm. For low dimensions, a specialized implementation for polygons is used. For higher dimensions, convex_hull relies on the polyhedral backend that can be specified using the backend keyword argument.

For performance reasons, it is suggested to use the CDDLib.Library() backend.

source
LazySets.API.minkowski_sumMethod
minkowski_sum(P1::VPolytope, P2::VPolytope;
              [apply_convex_hull]=true,
              [backend]=nothing,
              [solver]=nothing)

Compute the Minkowski sum of two polytopes in vertex representation.

Input

  • P1 – polytope
  • P2 – polytope
  • apply_convex_hull – (optional, default: true) if true, post-process the pairwise sums using a convex-hull algorithm
  • backend – (optional, default: nothing) the backend for polyhedral computations used to post-process with a convex hull; see default_polyhedra_backend(P1)
  • solver – (optional, default: nothing) the backend used to solve the linear program; see default_lp_solver_polyhedra(N)

Output

A new polytope in vertex representation whose vertices are the convex hull of the sum of all possible sums of vertices of P1 and P2.

source

Inherited from LazySet:

Inherited from AbstractPolyhedron:

Inherited from AbstractPolytope: