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]

convert(::Type{VPolygon}, X::LazySet)

Convert a two-dimensional polytopic set to a polygon in vertex representation.

Input

• VPolygon – target type
• X – two-dimensional polytopic set

Output

The 2D set represented as a polygon.

Algorithm

This method uses vertices_list.

area(V::VPolygon)

Compute the area of a polygon in vertex representation.

Input

• V – polygon in vertex representation

Output

A number representing the area of V.

Algorithm

See area(::LazySets.LazySet).

an_element(P::VPolygon)

Return some element of a polygon in vertex representation.

Input

• P – polygon in vertex representation

Output

The first vertex of the polygon in vertex representation.

constraints_list(P::VPolygon)

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

Input

• P – polygon in vertex representation

Output

The list of constraints of the polygon.

Algorithm

We convert to constraint representation using tohrep.

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

Create a random polygon in vertex representation.

Input

• VPolygon – 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_vertices – (optional, default: -1) number of vertices of the polygon (see comment below)

Output

A random polygon in vertex representation.

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{N}, ::Type{HPOLYGON}=HPolygon
      ) where {N, 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.

vertices_list(P::VPolygon; kwargs...)

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

Input

• P – polygon in vertex representation

Output

The list of vertices.

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

Check whether a given point is contained in a polygon in vertex representation.

Input

• x – point/vector
• P – polygon in vertex representation

Output

true iff $x ∈ P$.

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.

permute(V::VPolygon, p::AbstractVector{Int})

Permute the dimensions according to a permutation vector.

Input

• P – polygon in vertex representation
• p – permutation vector

Output

The permuted polygon in vertex representation.

σ(d::AbstractVector, P::VPolygon)

Return a support vector of a polygon in a given direction.

Input

• d – direction
• P – polygon in vertex representation

Output

A support vector in the given direction. 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).

translate(P::VPolygon, v::AbstractVector)

Translate (i.e., shift) a polygon in vertex representation by a given vector.

Input

• P – polygon in vertex representation
• v – translation vector

Output

A translated polygon in vertex representation.

Notes

See translate!(::VPolygon, ::AbstractVector) for the in-place version.

translate!(P::VPolygon, v::AbstractVector)

Translate (i.e., shift) a polygon in vertex representation by a given vector, in-place.

Input

• P – polygon in vertex representation
• v – translation vector

Output

The polygon translated by the vector.

Algorithm

We add the vector to each vertex of the polygon.

Notes

See translate(::VPolygon, ::AbstractVector) for the out-of-place version.

convex_hull(P::VPolygon, Q::VPolygon; [algorithm]::String="monotone_chain")

Return the convex hull of two polygons in vertex representation.

Input

• P – polygon in vertex representation
• Q – 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 two polygons.

Notes

The vertices of the output polygon are sorted in counter-clockwise fashion.

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

Compute the intersection of two polygons in vertex representation.

Input

• P1 – polygon in vertex representation
• P2 – polygon in vertex representation
• apply_convex_hull – (default, optional: true) if false, skip the computation of the convex hull of the resulting polygon

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(P::VPolygon, Q::VPolygon)

The Minkowski Sum of two polygons in vertex representation.

Input

• P – polygon in vertex representation
• Q – polygon in vertex representation

Output

A polygon in vertex representation.

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.