# Polygon in vertex representation (VPolygon)

`LazySets.VPolygon`

— Type`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]
```

`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)

`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
```

`LazySets.an_element`

— Method`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.

`Base.rand`

— Method```
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`

.

`LazySets.vertices_list`

— Method`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.

`LazySets.tohrep`

— Method```
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.

`LazySets.tovrep`

— Method`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.

`LazySets.constraints_list`

— Method`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.

`LazySets.translate`

— Method`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.

`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.

`LazySets.remove_redundant_vertices`

— Method```
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.

`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.

Inherited from `ConvexSet`

:

Inherited from `AbstractPolyhedron`

:

Inherited from `AbstractPolytope`

:

Inherited from `AbstractPolygon`

: