Polygons in constraint representation (AbstractHPolygon)

AbstractHPolygon{N} <: AbstractPolygon{N}

Abstract type for polygons in constraint representation.

Notes

All subtypes must satisfy the invariant that constraints are sorted counter-clockwise.

Every concrete AbstractHPolygon must have the following fields:

• constraints::Vector{HalfSpace{N, AbstractVector{N}}} – the constraints

The subtypes of AbstractHPolygon:

julia> subtypes(AbstractHPolygon)
2-element Vector{Any}:
 HPolygon
 HPolygonOpt

an_element(P::AbstractHPolygon)

Return some element of a polygon in constraint representation.

Input

• P – polygon in constraint representation

Output

A vertex of the polygon in constraint representation (the first one in the order of the constraints).

∈(x::AbstractVector, P::AbstractHPolygon)

Check whether a given two-dimensional point is contained in a polygon in constraint representation.

Input

• x – two-dimensional point/vector
• P – polygon in constraint representation

Output

true iff $x ∈ P$.

Algorithm

This implementation checks if the point lies inside each constraint.

rand(::Type{HPOLYGON}; [N]::Type=Float64, [dim]::Int=2,
     [rng]::AbstractRNG=GLOBAL_RNG, [seed]::Union{Int, Nothing}=nothing,
     [num_constraints]::Int=-1) where {HPOLYGON<:AbstractHPolygon}

Create a random polygon in constraint representation.

Input

• HPOLYGON – 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_constraints – (optional, default: -1) number of constraints of the polygon (must be 3 or bigger; see comment below)

Output

A random polygon in constraint representation.

Algorithm

We create a random polygon in vertex representation and convert it to constraint representation. See rand(::Type{VPolygon}). For non-flat polygons the number of vertices and the number of constraints are identical.

tohrep(P::HPOLYGON) where {HPOLYGON<:AbstractHPolygon}

Build a constraint representation of the given polygon.

Input

• P – polygon in constraint representation

Output

The identity, i.e., the same polygon instance.

tovrep(P::AbstractHPolygon)

Build a vertex representation of a polygon in constraint representation.

Input

• P – polygon in constraint representation

Output

The same polygon but in vertex representation, a VPolygon.

addconstraint!(P::AbstractHPolygon, constraint::HalfSpace;
               [linear_search]::Bool=length(P.constraints) < 10,
               [prune]::Bool=true)

Add a linear constraint to a polygon in constraint representation, keeping the constraints sorted by their normal directions.

Input

• P – polygon in constraint representation
• constraint – linear constraint to add
• linear_search – (optional, default: length(constraints) < 10) flag to choose between linear and binary search
• prune – (optional, default: true) flag for removing redundant constraints in the end

addconstraint!(constraints::Vector{LC}, new_constraint::HalfSpace;
               [linear_search]::Bool=length(P.constraints) < 10,
               [prune]::Bool=true) where {LC<:HalfSpace}

Add a linear constraint to a sorted vector of constrains, keeping the constraints sorted by their normal directions.

Input

• constraints – vector of linear constraints
• new_constraint – linear constraint to add
• linear_search – (optional, default: length(constraints) < 10) flag to choose between linear and binary search
• prune – (optional, default: true) flag for removing redundant constraints in the end

Algorithm

If prune is active, we check if the new constraint is redundant. If the constraint is not redundant, we perform the same check to the left and to the right until we find the first constraint that is not redundant.

normalize(P::AbstractHPolygon{N}, p::Real=N(2)) where {N}

Normalize a polygon in constraint representation.

Input

• P – polygon in constraint representation
• p – (optional, default: 2) norm

Output

A new polygon in constraint representation whose normal directions $a_i$ are normalized, i.e., such that $‖a_i‖_p = 1$ holds.

isredundant(cmid::HalfSpace, cright::HalfSpace, cleft::HalfSpace)

Check whether a linear constraint is redundant wrt. two surrounding constraints.

Input

• cmid – linear constraint of concern
• cright – linear constraint to the right (clockwise turn)
• cleft – linear constraint to the left (counter-clockwise turn)

Output

true iff the constraint is redundant.

Algorithm

We first check whether the angle between the surrounding constraints is < 180°, which is a necessary condition (unless the direction is identical to one of the other two constraints). If so, we next check if the angle is 0°, in which case the constraint cmid is redundant unless it is strictly tighter than the other two constraints. If the angle is strictly between 0° and 180°, the constraint cmid is redundant if and only if the vertex defined by the other two constraints lies inside the set defined by cmid.

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 fewer constraints left. Hence for unbounded 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.

constraints_list(P::AbstractHPolygon)

Return the list of constraints defining a polygon in constraint representation.

Input

• P – polygon in constraint representation

Output

The list of constraints of the polygon. The implementation guarantees that the constraints are sorted counter-clockwise.

vertices_list(P::AbstractHPolygon{N};
              apply_convex_hull::Bool=true,
              check_feasibility::Bool=true) where {N}

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

Input

• P – polygon in constraint representation
• apply_convex_hull – (optional, default: true) flag to post-process the intersection of constraints with a convex hull
• check_feasibility – (optional, default: true) flag to check whether the polygon was empty (required for correctness in case of empty polygons)

Output

List of vertices.

Notes

By construction an AbstractHPolygon should not contain any redundant vertices. Still the apply_convex_hull argument is activated by default to remove potential duplicate vertices. They can exist due to numeric instability.

julia> p = HPolygon([HalfSpace([1.0, 0.0], 1.0),
                     HalfSpace([0.0, 1.0], 1.0),
                     HalfSpace([-1.0, 0.0], -1.0),
                     HalfSpace([0.0, -1.0], -1.0)]);

julia> vertices_list(p, apply_convex_hull=false)
4-element Vector{Vector{Float64}}:
 [1.0, 1.0]
 [1.0, 1.0]
 [1.0, 1.0]
 [1.0, 1.0]

If it is known that each constraint has a "proper" distance to the next vertex, this step can be skipped.

Algorithm

We compute each vertex as the intersection of consecutive lines defined by the half-spaces. If check_feasibility is active, we then check if the constraints of the polygon were actually feasible (i.e., they pointed in the right direction). For this we compute the average of all vertices and check membership in each constraint.

isbounded(P::AbstractHPolygon, [use_type_assumption]::Bool=true)

Determine whether a polygon in constraint representation is bounded.

Input

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

Output

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

Algorithm

If !use_type_assumption, we use _isbounded_unit_dimensions.