Polytope in constraint representation (HPolytope)

Convex polytopes are bounded polyhedra. The type HPolytope represents polytopes. While identical to HPolyhedron in its representation, HPolytope instances are assumed to be bounded.

LazySets.HPolytopeModule.HPolytopeType
HPolytope{N, VN<:AbstractVector{N}} <: AbstractPolytope{N}

Type that represents a convex polytope in constraint representation, i.e., a bounded set characterized by a finite intersection of half-spaces,

\[P = ⋂_{i = 1}^m H_i,\]

where each $H_i = \{x ∈ ℝ^n : a_i^T x ≤ b_i \}$ is a half-space, $a_i ∈ ℝ^n$ is the normal vector of the $i$-th half-space and $b_i$ is the displacement. It is assumed that $P$ is bounded (see also LazySets.HPolyhedron, which does not make such an assumption).

Fields

  • constraints – vector of linear constraints
  • check_boundedness – (optional, default: false) flag for checking if the constraints make the polytope bounded; (boundedness is a running assumption for this type)

Notes

A polytope is a bounded polyhedron.

Boundedness is a running assumption for this type. For performance reasons, boundedness is not checked in the constructor by default. We also exploit this assumption, so a boundedness check may not return the answer you would expect.

julia> P = HPolytope([HalfSpace([1.0], 1.0)]);  # x <= 1

julia> isbounded(P)  # uses the type assumption and does not actually check
true

julia> isbounded(P, false)  # performs a real boundedness check
false
source

Conversion

Base.convertMethod
convert(::Type{HPolytope}, X::LazySet)

Convert a polytopic set to a polytope in constraint representation.

Input

  • HPolytope – target type
  • X – polytopic set

Output

The given polytope represented as a polytope in constraint representation.

Algorithm

This method uses constraints_list.

source

Operations

Most functionality is shared with HPolyhedron. Additional functionality specific to HPolytope is listed below.

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

Create a random polytope in constraint representation.

Input

  • HPolytope – 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 constraint representation.

Algorithm

We create a random polytope in vertex representation and convert it to constraint representation (hence the argument num_vertices). See rand(::Type{VPolytope}).

source
LazySets.API.vertices_listMethod
vertices_list(P::HPolytope; [backend]=nothing, [prune]::Bool=true)

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

Input

  • P – polytope in constraint representation
  • backend – (optional, default: nothing) the backend for polyhedral computations
  • prune – (optional, default: true) flag to remove redundant vertices

Output

A list of the vertices.

Algorithm

If the polytope is one-dimensional (resp. two-dimensional), it is converted to an interval (resp. polygon in constraint representation) and then the respective optimized vertices_list implementation is used.

It is possible to use the Polyhedra backend in the one- and two-dimensional case as well by passing a backend.

If the polytope is not two-dimensional, the concrete polyhedra-manipulation library Polyhedra is used. The actual computation is performed by a given backend; for the default backend used in LazySets see default_polyhedra_backend(P). For further information on the supported backends see Polyhedra's documentation.

source
LazySets.API.isboundedFunction
isbounded(P::HPolytope, [use_type_assumption]::Bool=true)

Determine whether a polytope in constraint representation is bounded.

Input

  • P – polytope in constraint representation
  • use_type_assumption – (optional, default: true) flag for ignoring the type assumption that polytopes are bounded

Output

true if use_type_assumption is activated. Otherwise, true iff P is bounded.

source

Inherited from AbstractPolytope: