HalfSpace

Half-space (HalfSpace)

LazySets.HalfSpace — Type.
HalfSpace{N<:Real, VN<:AbstractVector{N}} <: AbstractPolyhedron{N}

Type that represents a (closed) half-space of the form $a⋅x ≤ b$.

Fields

  • a – normal direction (non-zero)
  • b – constraint

Examples

The half-space $x + 2y - z ≤ 3$:

julia> HalfSpace([1, 2, -1.], 3.)
HalfSpace{Float64,Array{Float64,1}}([1.0, 2.0, -1.0], 3.0)

To represent the set $y ≥ 0$ in the plane, we have to rearrange the expression as $0x - y ≤ 0$:

julia> HalfSpace([0, -1.], 0.)
HalfSpace{Float64,Array{Float64,1}}([0.0, -1.0], 0.0)
source
LazySets.LinearConstraint — Type.
LinearConstraint

Alias for HalfSpace

source
LazySets.dim — Method.
dim(hs::HalfSpace)

Return the dimension of a half-space.

Input

  • hs – half-space

Output

The ambient dimension of the half-space.

source
LazySets.ρ — Method.
ρ(d::AbstractVector{N}, hs::HalfSpace{N}) where {N<:Real}

Evaluate the support function of a half-space in a given direction.

Input

  • d – direction
  • hs – half-space

Output

The support function of the half-space. If the set is unbounded in the given direction, the result is Inf.

source
LazySets.σ — Method.
σ(d::AbstractVector{N}, hs::HalfSpace{N}) where {N<:Real}

Return the support vector of a half-space.

Input

  • d – direction
  • hs – half-space

Output

The support vector in the given direction, which is only defined in the following two cases:

  1. The direction has norm zero.
  2. The direction is the half-space's normal direction.

In both cases the result is any point on the boundary (the defining hyperplane). Otherwise this function throws an error.

source
Base.:∈ — Method.
∈(x::AbstractVector{N}, hs::HalfSpace{N}) where {N<:Real}

Check whether a given point is contained in a half-space.

Input

  • x – point/vector
  • hs – half-space

Output

true iff $x ∈ hs$.

Algorithm

We just check if $x$ satisfies $a⋅x ≤ b$.

source
LazySets.an_element — Method.
an_element(hs::HalfSpace{N}) where {N<:Real}

Return some element of a half-space.

Input

  • hs – half-space

Output

An element on the defining hyperplane.

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

Create a random half-space.

Input

  • HalfSpace – 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

Output

A random half-space.

Algorithm

All numbers are normally distributed with mean 0 and standard deviation 1. Additionally, the constraint a is nonzero.

source
LazySets.isbounded — Method.
isbounded(hs::HalfSpace)

Determine whether a half-space is bounded.

Input

  • hs – half-space

Output

false.

source
LazySets.isuniversal — Method.
isuniversal(hs::HalfSpace{N}, [witness]::Bool=false) where {N<:Real}

Check whether a half-space is universal.

Input

  • P – half-space
  • witness – (optional, default: false) compute a witness if activated

Output

  • If witness option is deactivated: false
  • If witness option is activated: (false, v) where $v ∉ P$

Algorithm

Witness production falls back to isuniversal(::Hyperplane).

source
Base.isempty — Method.
isempty(hs::HalfSpace)

Return if a half-space is empty or not.

Input

  • hs – half-space

Output

false.

source
LazySets.constraints_list — Method.
constraints_list(hs::HalfSpace{N}) where {N<:Real}

Return the list of constraints of a half-space.

Input

  • hs – half-space

Output

A singleton list containing the half-space.

source
LazySets.constraints_list — Method.
constraints_list(A::AbstractMatrix{N}, b::AbstractVector{N}) where {N<:Real}

Convert a matrix-vector representation to a linear-constraint representation.

Input

  • A – matrix
  • b – vector

Output

A list of linear constraints.

source
LazySets.constrained_dimensions — Method.
constrained_dimensions(hs::HalfSpace{N}) where {N<:Real}

Return the indices in which a half-space is constrained.

Input

  • hs – half-space

Output

A vector of ascending indices i such that the half-space is constrained in dimension i.

Examples

A 2D half-space with constraint $x1 ≥ 0$ is constrained in dimension 1 only.

source
LazySets.translate — Method.
translate(hs::HalfSpace{N}, v::AbstractVector{N}; share::Bool=false
         ) where {N<:Real}

Translate (i.e., shift) a half-space by a given vector.

Input

  • hs – half-space
  • v – translation vector
  • share – (optional, default: false) flag for sharing unmodified parts of the original set representation

Output

A translated half-space.

Notes

The normal vectors of the halfspace (vector a in a⋅x ≤ b) is shared with the original halfspace if share == true.

Algorithm

A half-space $a⋅x ≤ b$ is transformed to the half-space $a⋅x ≤ b + a⋅v$. In other words, we add the dot product $a⋅v$ to $b$.

source
LazySets.halfspace_left — Method.
halfspace_left(p::AbstractVector{N}, q::AbstractVector{N}) where {N<:Real}

Return a half-space describing the 'left' of a two-dimensional line segment through two points.

Input

  • p – first point
  • q – second point

Output

The half-space whose boundary goes through the two points p and q and which describes the left-hand side of the directed line segment pq.

Algorithm

The implementation is simple: the half-space $a⋅x ≤ b$ is calculated as a = [dy, -dx], where $d = (dx, dy)$ denotes the line segment pq, that is, $\vec{d} = \vec{p} - \vec{q}$, and b = dot(p, a).

Examples

The left half-space of the "east" and "west" directions in two-dimensions are the upper and lower half-spaces:

julia> using LazySets: halfspace_left

julia> halfspace_left([0.0, 0.0], [1.0, 0.0])
HalfSpace{Float64,Array{Float64,1}}([0.0, -1.0], 0.0)

julia> halfspace_left([0.0, 0.0], [-1.0, 0.0])
HalfSpace{Float64,Array{Float64,1}}([0.0, 1.0], 0.0)

We create a box from the sequence of line segments that describe its edges:

julia> H1 = halfspace_left([-1.0, -1.0], [1.0, -1.0]);

julia> H2 = halfspace_left([1.0, -1.0], [1.0, 1.0]);

julia> H3 = halfspace_left([1.0, 1.0], [-1.0, 1.0]);

julia> H4 = halfspace_left([-1.0, 1.0], [-1.0, -1.0]);

julia> H = HPolygon([H1, H2, H3, H4]);

julia> B = BallInf([0.0, 0.0], 1.0);

julia> B ⊆ H && H ⊆ B
true
source
LazySets.halfspace_right — Method.
halfspace_right(p::AbstractVector{N}, q::AbstractVector{N}) where {N<:Real}

Return a half-space describing the 'right' of a two-dimensional line segment through two points.

Input

  • p – first point
  • q – second point

Output

The half-space whose boundary goes through the two points p and q and which describes the right-hand side of the directed line segment pq.

Algorithm

See the documentation of halfspace_left.

source
LazySets.tosimplehrep — Method.
tosimplehrep(constraints::AbstractVector{LC})
    where {N<:Real, LC<:LinearConstraint{N}}

Return the simple H-representation $Ax ≤ b$ from a list of linear constraints.

Input

  • constraints – a list of linear constraints

Output

The tuple (A, b) where A is the matrix of normal directions and b is the vector of offsets.

source
LazySets.remove_redundant_constraints — Function.
remove_redundant_constraints(
    constraints::AbstractVector{<:LinearConstraint{N}};
    backend=default_lp_solver(N)) where {N<:Real}

Remove the redundant constraints of a given list of linear constraints.

Input

  • constraints – list of constraints
  • backend – (optional, default: default_lp_solver(N)) the backend used to solve the linear program

Output

The list of constraints with the redundant ones removed, or an empty set if the constraints are infeasible.

Algorithm

See remove_redundant_constraints!(::AbstractVector{<:LinearConstraint}) for details.

source
remove_redundant_constraints(P::HPoly{N};
                             backend=default_lp_solver(N)
                            ) where {N<:Real}

Remove the redundant constraints in a polyhedron in H-representation.

Input

  • P – polyhedron
  • backend – (optional, default: default_lp_solver(N)) the backend used to solve the linear program

Output

A polyhedron equivalent to P but with no redundant constraints, or an empty set if P is detected to be empty, which may happen if the constraints are infeasible.

Algorithm

See remove_redundant_constraints!(::AbstractVector{<:LinearConstraint}) for details.

source
LazySets.remove_redundant_constraints! — Function.
 remove_redundant_constraints!(
     constraints::AbstractVector{<:LinearConstraint{N}};
     [backend]=default_lp_solver(N)) where {N<:Real}

Remove the redundant constraints of a given list of linear constraints; the list is updated in-place.

Input

  • constraints – list of constraints
  • backend – (optional, default: default_lp_solver(N)) the backend used to solve the linear program

Output

true if the function was successful and the list of constraints constraints is modified by removing the redundant constraints, and false only if the constraints are infeasible.

Notes

Note that the result may be true even if the constraints are infeasible. For example, $x ≤ 0 && x ≥ 1$ will return true without removing any constraint. To check if the constraints are infeasible, use isempty(HPolyhedron(constraints).

Algorithm

If there are m constraints in n dimensions, this function checks one by one if each of the m constraints is implied by the remaining ones.

To check if the k-th constraint is redundant, an LP is formulated using the constraints that have not yet being removed. If, at an intermediate step, it is detected that a subgroup of the constraints is infeasible, this function returns false. If the calculation finished successfully, this function returns true.

For details, see Fukuda's Polyhedra FAQ.

source
remove_redundant_constraints!(P::AbstractHPolygon)

Remove all redundant constraints of a polygon in constraint representation.

Input

  • P – polygon in constraint representation

Output

The same polygon with all redundant constraints removed.

Notes

Since we only consider bounded polygons and a polygon needs at least three constraints to be bounded, we stop removing redundant constraints if there are three or less constraints left. This means that for non-bounded polygons the result may be unexpected.

Algorithm

We go through all consecutive triples of constraints and check if the one in the middle is redundant. For this we assume that the constraints are sorted.

source
remove_redundant_constraints!(P::HPoly{N};
                              backend=default_lp_solver(N)) where {N<:Real}

Remove the redundant constraints in a polyhedron in H-representation; the polyhedron is updated in-place.

Input

  • P – polyhedron
  • backend – (optional, default: default_lp_solver(N)) the backend used to solve the linear program

Output

true if the method was successful and the polyhedron P is modified by removing its redundant constraints, and false if P is detected to be empty, which may happen if the constraints are infeasible.

Algorithm

See remove_redundant_constraints!(::AbstractVector{<:LinearConstraint}) for details.

source

Inherited from LazySet: