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.HPolytope
— TypeHPolytope{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 = \bigcap_{i = 1}^m H_i,\]
where each $H_i = \{x \in \mathbb{R}^n : a_i^T x \leq b_i \}$ is a half-space, $a_i \in \mathbb{R}^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 HPolyhedron
, which does not make such an assumption).
Fields
constraints
– vector of linear constraintscheck_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
Most functionality is shared with HPolyhedron
. Additional functionality specific to HPolytope
is listed below.
Base.rand
— Methodrand(::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 dispatchN
– (optional, default:Float64
) numeric typedim
– (optional, default: 2) dimensionrng
– (optional, default:GLOBAL_RNG
) random number generatorseed
– (optional, default:nothing
) seed for reseedingnum_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})
.
LazySets.vertices_list
— Methodvertices_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 representationbackend
– (optional, default:nothing
) the backend for polyhedral computationsprune
– (optional, default:true
) flag to remove redundant vertices
Output
A list of the vertices.
Algorithm
If the polytope is two-dimensional, the polytope is converted to a polygon in constraint representation and then its vertices_list
implementation is used. This ensures that, by default, the optimized two-dimensional methods are used.
It is possible to use the Polyhedra
backend in two-dimensions 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.
LazySets.isbounded
— Functionisbounded(P::HPolytope, [use_type_assumption]::Bool=true)
Determine whether a polytope in constraint representation is bounded.
Input
P
– polytope in constraint representationuse_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.
Inherited from AbstractPolytope
: