Convex Polygons

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

triangulate_convex(points, S;
    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.


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


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)