Polygon in vertex representation (VPolygon)

VPolygon{N<:Real, 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]])
VPolygon{Int64,Array{Int64,1}}(Array{Int64,1}[[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 Array{Float64,2}:
 0.0  1.0  0.0
 0.0  0.0  1.0

julia> VPolygon(M)
VPolygon{Float64,Array{Float64,1}}(Array{Float64,1}[[0.0, 0.0], [1.0, 0.0], [0.0, 1.0]])

σ(d::AbstractVector{N}, P::VPolygon{N}) where {N<:Real}

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)

∈(x::AbstractVector{N}, P::VPolygon{N}) where {N<:Real}

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 -> floating-point error
false
julia> P = VPolygon([[2//1, 3//1], [3//1, 1//1], [5//1, 1//1], [4//1, 5//1]];
                     apply_convex_hull=false);

julia> [44//10, 34//10] ∈ P  #  with rational numbers the answer is correct
true

an_element(P::VPolygon{N}) where {N<:Real}

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.

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.

vertices_list(P::VPolygon{N}) where {N<:Real}

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

Input

• P – a polygon vertex representation

Output

List of vertices.

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

tovrep(P::VPolygon{N}) where {N<:Real}

Build a vertex representation of the given polygon.

Input

• P – polygon in vertex representation

Output

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

constraints_list(P::VPolygon{N}) where {N<:Real}

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.

translate(P::VPolygon{N}, v::AbstractVector{N}) where {N<:Real}

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.

remove_redundant_vertices(P::VPolygon{N};
                          [algorithm]::String="monotone_chain") where {N<:Real}

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.

remove_redundant_vertices!(P::VPolygon{N};
                           [algorithm]::String="monotone_chain") where {N<:Real}

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.