Polygon in vertex representation (VPolygon)

VPolygon{N, VN<:AbstractVector{N}} <: AbstractPolygon{N}

Type that represents a polygon by its vertices.

Fields

• vertices – the list of vertices

Notes

This type assumes that all vertices are sorted in counter-clockwise fashion.

To ensure this property, the constructor of VPolygon runs a convex-hull algorithm on the vertices by default. This also removes redundant vertices. If the vertices are known to be sorted, the flag apply_convex_hull=false can be used to skip this preprocessing.

Examples

A polygon in vertex representation can be constructed by passing the list of vertices. For example, we can build the right triangle

julia> P = VPolygon([[0, 0], [1, 0], [0, 1]]);

julia> P.vertices
3-element Vector{Vector{Int64}}:
 [0, 0]
 [1, 0]
 [0, 1]

Alternatively, a VPolygon can be constructed passing a matrix of vertices, where each column represents a vertex:

julia> M = [0 1 0; 0 0 1.]
2×3 Matrix{Float64}:
 0.0  1.0  0.0
 0.0  0.0  1.0

julia> P = VPolygon(M);

julia> P.vertices
3-element Vector{Vector{Float64}}:
 [0.0, 0.0]
 [1.0, 0.0]
 [0.0, 1.0]

an_element(X::LazySet)

Return some element of a nonempty set.

Input

• X – set

Output

An element of X unless X is empty.

Extended help

an_element(P::VPolygon)

Output

The first vertex of the polygon in vertex representation.

area(X::LazySet)

Compute the area of a two-dimensional set.

Input

• X – two-dimensional set

Output

A number representing the area of X.

Extended help

area(V::VPolygon)

Algorithm

See area(::LazySets.LazySet).

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

Create a random set of the given set type.

Input

• T – set type
• 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 set of the given set type.

Extended help

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

Input

• num_vertices – (optional, default: -1) number of vertices of the polygon (see comment below)

Notes

The number of vertices can be controlled with the argument num_vertices. For a negative value we choose a random number in the range 3:10.

Algorithm

We follow the idea described here based on [1]. There is also a nice video available here.

[1] Pavel Valtr: Probability that n random points are in convex position. Discret. Comput. Geom. 1995.

remove_redundant_vertices(P::VPolygon;
                          [algorithm]::String="monotone_chain")

Return a polygon obtained by removing the redundant vertices of the given polygon.

Input

• P – polygon in vertex representation
• algorithm – (optional, default: "monotone_chain") the algorithm used to compute the convex hull

Output

A new polygon such that its vertices are the convex hull of the given polygon.

Algorithm

See remove_redundant_vertices!(::VPolygon).

remove_redundant_vertices!(P::VPolygon;
                           [algorithm]::String="monotone_chain")

Remove the redundant vertices from the given polygon in-place.

Input

• P – polygon in vertex representation
• algorithm – (optional, default: "monotone_chain") the algorithm used to compute the convex hull

Output

The modified polygon whose redundant vertices have been removed.

Algorithm

A convex-hull algorithm is used to compute the convex hull of the vertices of the polygon P; see ?convex_hull for details on the available algorithms. The vertices are sorted in counter-clockwise fashion.

tohrep(P::VPolygon, ::Type{HPOLYGON}=HPolygon) where {HPOLYGON<:AbstractHPolygon}

Build a constraint representation of the given polygon.

Input

• P – polygon in vertex representation
• HPOLYGON – (optional, default: HPolygon) type of target polygon

Output

A polygon in constraint representation, an AbstractHPolygon.

Algorithm

The algorithm adds an edge for each consecutive pair of vertices. Since the vertices are already ordered in counter-clockwise fashion (CCW), the constraints will be sorted automatically (CCW).

tovrep(P::VPolygon)

Build a vertex representation of the given polygon.

Input

• P – polygon in vertex representation

Output

The same polygon instance.

Extended help

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

Algorithm

This implementation exploits that the polygon's vertices are sorted in counter-clockwise fashion. Under this assumption we can just check if the vertex lies on the left of each edge, using the dot product.

Examples

julia> P = VPolygon([[2.0, 3.0], [3.0, 1.0], [5.0, 1.0], [4.0, 5.0]]);

julia> [4.5, 3.1] ∈ P
false
julia> [4.5, 3.0] ∈ P
true
julia> [4.4, 3.4] ∈ P  #  point lies on the edge
true

linear_map(M::AbstractMatrix, P::VPolygon; [apply_convex_hull]::Bool=false)

Concrete linear map of a polygon in vertex representation.

Input

• M – matrix
• P – polygon in vertex representation
• apply_convex_hull – (optional; default: false) flag to apply a convex-hull operation (only relevant for higher-dimensional maps)

Output

The type of the result depends on the dimension. in 1D it is an interval, in 2D it is a VPolygon, and in all other cases it is a VPolytope.

Algorithm

This implementation uses the internal _linear_map_vrep method.

σ(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::VPolygon)

Output

If the direction has norm zero, the first vertex is returned.

Algorithm

This implementation uses a binary search algorithm when the polygon has more than 10 vertices and a brute-force search when it has 10 or fewer vertices. The brute-force search compares the projection of each vector along the given direction and runs in $O(n)$ where $n$ is the number of vertices. The binary search runs in $O(log n)$ and we follow this implementation based on an algorithm described in [1].

[1] Joseph O'Rourke, Computational Geometry in C (2nd Edition).

intersection(X::LazySet, Y::LazySet)

Compute the intersection of two sets.

Input

• X – set
• Y – set

Output

A set representing the intersection $X ∩ Y$.

Notes

The intersection of two sets $X$ and $Y$ is defined as

\[ X ∩ Y = \{x \mid x ∈ X \text{ and } x ∈ Y\}.\]

Extended help

intersection(P1::VPolygon, P2::VPolygon; apply_convex_hull::Bool=true)

Output

A VPolygon, or an EmptySet if the intersection is empty.

Algorithm

This function applies the Sutherland–Hodgman polygon clipping algorithm. The implementation is based on the one found in rosetta code.

minkowski_sum(X::LazySet, Y::LazySet)

Compute the Minkowski sum of two sets.

Input

• X – set
• Y – set

Output

A set representing the Minkowski sum $X ⊕ Y$.

Notes

The Minkowski sum of two sets $X$ and $Y$ is defined as

\[ X ⊕ Y = \{x + y \mid x ∈ X, y ∈ Y\}.\]

Extended help

minkowski_sum(P::VPolygon, Q::VPolygon)

Algorithm

We treat each edge of the polygons as a vector, attaching them in polar order (attaching the tail of the next vector to the head of the previous vector). The resulting polygonal chain will be a polygon, which is the Minkowski sum of the given polygons. This algorithm assumes that the vertices of P and Q are sorted in counter-clockwise fashion and has linear complexity $O(m+n)$, where $m$ and $n$ are the number of vertices of P and Q, respectively.