# Convex Polygons

We have an algorithm available for computing the Delaunay triangulation of a convex polygon:

DelaunayTriangulation.triangulate_convexFunction
triangulate_convex(points, S;
IntegerType::Type{I}=Int,
EdgeType::Type{E}=NTuple{2,IntegerType},
TriangleType::Type{V}=NTuple{3,IntegerType},
EdgesType::Type{Es}=Set{EdgeType},
TrianglesType::Type{Ts}=Set{TriangleType},
rng::AbstractRNG=Random.default_rng(),
compute_centers=false,
delete_empty_features=false) where {I,E,V,Es,Ts}

Given some points and a counter-clockwise list of indices S for points in points that define a convex polygon, triangulates it with Chew's algorithm.

Arguments

• points::P: The set of points.
• S: A counter-clockwise list of vertices defining a convex polygon from the corresponding points in points.

Keyword Arguments

• IntegerType::Type{I}=Int: The integer type to use for indexing.
• EdgeType::Type{E}=NTuple{2,IntegerType}: The type to use for representing edges.
• TriangleType::Type{V}=NTuple{3,IntegerType}: The type to use for representing triangles.
• EdgesType::Type{Es}=Set{EdgeType}: The type to use for representing collections of edges.
• TrianglesType::Type{Ts}=Set{TriangleType}: The type to use for representing collections of triangles.
• representative_point_list = get_empty_representative_points(IntegerType, number_type(points)): The representative point list to use.
• rng::AbstractRNG=Random.default_rng(): The RNG to use.
• add_ghost_triangles=true: Whether to add the ghost triangles at the end of the triangulation.
• add_convex_hull=true: Whether to populate the convex hull field of tri with S at the end of the triangulation.
• compute_centers=true: Whether to recompute the RepresentativePointList at the end of the triangulation.
• delete_empty_features=true: Whether to delete any empty neighbourhoods and adjacencies at the end of the triangulation.

Outputs

Returns a Triangulation of the convex polygon.

The function takes as input some set of points $\mathcal P$ and a corresponding sequence of indices $\{v_1, \ldots, v_n\}$, in counter-clockwise order, defining some convex polygon and returns the polygon's Delaunay triangulation. Note that the keyword arguments here differ from triangulate. Here is an example of triangulate_convex in action.

using DelaunayTriangulation
using CairoMakie
p1 = [10.0, 12.0]
p2 = [7.0, 11.0]
p3 = [8.0, 6.0]
p4 = [10.0, 3.0]
p5 = [14.0, 5.0]
p6 = [15.0, 10.0]
p7 = [13.0, 12.0]
pts = [p1, p2, p3, p4, p5, p6, p7]
S = collect(1:7)
tri = triangulate_convex(pts, S)
fig, ax, sc = triplot(tri; plot_convex_hull=false)