Polygon in constraint representation (HPolygon)

HPolygon{N, VN<:AbstractVector{N}} <: AbstractHPolygon{N}

Type that represents a convex polygon in constraint representation whose edges are sorted in counter-clockwise fashion with respect to their normal directions.

Fields

• constraints – list of linear constraints, sorted by the normal direction in counter-clockwise fashion

Notes

Further constructor arguments:

• sort_constraints – (optional, default: true) flag for sorting the constraints (being sorted is a running assumption of this type)
• check_boundedness – (optional, default: false) flag for checking if the constraints make the polygon bounded; (boundedness is a running assumption of this type)
• prune – (optional, default: true) flag for removing redundant constraints

The option sort_constraints can be used to deactivate automatic sorting of constraints in counter-clockwise fashion, which is an invariant of this type. Alternatively, one can construct an HPolygon with empty constraints list, which can then be filled iteratively using addconstraint!.

Similarly, the option prune can be used to deactivate automatic pruning of redundant constraints.

Another type assumption is that the polygon is bounded. The option check_boundedness can be used to assert this. This option is deactivated by default because we explicitly want to allow the iterative addition of the constraints, and hence one has to initially construct an empty list of constraints (which represents an unbounded set). The user has to make sure that the HPolygon is not used before the constraints actually describe a bounded set.

σ(d::AbstractVector, X::LazySet)

Compute a support vector of a set in a given direction.

Input

• d – direction
• X – set

Output

A support vector of X in direction d.

Notes

A convenience alias support_vector is also available.

Extended help

σ(d::AbstractVector, P::HPolygon;
  [linear_search]::Bool=(length(P.constraints) < 10))

Input

• linear_search – (optional, default: see below) flag for controlling whether to perform a linear search or a binary search

Output

The result is always one of the vertices; in particular, if the direction has norm zero, any vertex is returned.

Algorithm

Comparison of directions is performed using polar angles; see the definition of ⪯ for two-dimensional vectors.

For polygons with 10 or more constraints we use a binary search by default.

translate(X::LazySet, v::AbstractVector)

Compute the translation of a set with a vector.

Input

• X – set
• v – vector

Output

A set representing $X + \{v\}$.

Extended help

translate(v::AbstractVector, P::HPolygon; [share]::Bool=false)

Input

• share – (optional, default: false) flag for sharing unmodified parts of the original set representation

Notes

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

Algorithm

We translate every constraint.