Polygon in vertex representation (VPolygon)

LazySets.VPolygonType
VPolygon{N, VN<:AbstractVector{N}} <: AbstractPolygon{N}

Type that represents a polygon by its vertices.

Fields

  • vertices – the list of vertices

Notes

The constructor of VPolygon runs a convex hull algorithm on its vertices by default, to remove the possibly redundant vertices. The vertices are sorted in counter-clockwise fashion. Use the flag apply_convex_hull=false to skip the computation of the convex hull.

  • VPolygon(vertices::Vector{Vector{N}}; apply_convex_hull::Bool=true, algorithm::String="monotone_chain")

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]
source
LazySets.σMethod
σ(d::AbstractVector, P::VPolygon)

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

Input

  • d – direction
  • P – polygon in vertex representation

Output

The 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 ten vertices and a brute-force search when it has ten or less. For the brute-force search, it compares the projection of each vector along the given direction and runs in $O(n)$ where $n$ is the number of vertices. For the binary search the algorithm runs in $O(log n)$. We follow this implementation based on an algorithm described in [1].

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

source
Base.:∈Method
∈(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]];
                    apply_convex_hull=false);

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
source
LazySets.an_elementMethod
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.

source
Base.randMethod
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.

Algorithm

We follow the idea here based on P. Valtr. Probability that n random points are in convex position. There is also a nice video available here.

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.

source
LazySets.vertices_listMethod
vertices_list(P::VPolygon)

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

Input

  • P – a polygon vertex representation

Output

List of vertices.

source
LazySets.tohrepMethod
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

The same polygon but in constraint representation, an AbstractHPolygon.

Algorithm

The algorithms consists of adding an edge for each consecutive pair of vertices. Since the vertices are already ordered in counter-clockwise fashion (CWW), the constraints will be sorted automatically (CCW) if we start with the first edge between the first and second vertex.

source
LazySets.tovrepMethod
tovrep(P::VPolygon)

Build a vertex representation of the given polygon.

Input

  • P – polygon in vertex representation

Output

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

source
LazySets.constraints_listMethod
constraints_list(P::VPolygon)

Return the list of constraints defining a polygon in V-representation.

Input

  • P – polygon in V-representation

Output

The list of constraints of the polygon.

Algorithm

First the H-representation of $P$ is computed, then its list of constraints is returned.

source
LazySets.translateMethod
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.

Algorithm

We add the vector to each vertex of the polygon.

Notes

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

source
LazySets.translate!Method
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

A translated polygon in vertex representation.

Algorithm

We add the vector to each vertex of the polygon.

Notes

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

source
LazySets.remove_redundant_verticesMethod
remove_redundant_vertices(P::VPolygon;
                          [algorithm]::String="monotone_chain")

Return the 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

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

source
LazySets.remove_redundant_vertices!Method
remove_redundant_vertices!(P::VPolygon;
                           [algorithm]::String="monotone_chain")

Remove 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

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

source

Inherited from ConvexSet:

Inherited from AbstractPolyhedron:

Inherited from AbstractPolytope:

Inherited from AbstractPolygon: