Triangulations of Convex Polygons

In order to better understand triangulations, flips and flip graphs, it can be helpful to start simple. If you take any number of points and iteratively connect them with straight edges that do not cross each other until you can no longer add an edge that does not cross any other edge, what you'll get is a (geometric) triangulation.

To get from one triangulation of a set of points to another, you may choose an inner edge and flip it. If you look at any inner edge, the two triangles adjacent to it form a quadrilateral, with the edge as one of its diagonals. To flip an edge, all we have to do is replace it with the other diagonal. As we don't want to have straight edges that cross each other, a flip can only be done if the quadrilateral is convex and no three of its corners lie on the same line. As we are interested in taking this theory to closed surfaces, where we will no longer have the restriction of edges being straight, we will only consider triangulations of points in convex general position. In this case, a triangulation in the geometric sense is equivalent to a triangulation of points on the border of a disc or a maximal outerplanar graph.

We do not care where exactly the points are located; however, in order to keep in line with the geometric sense and have a simple visualization, we will consider these points to be the vertices of a convex polygon (i.e. points in convex position).


struct TriangulatedPolygon <: AbstractGraph{Int32}

A structure representing a triangulation of a convex polygon.

TriangulatedPolygon implements the AbstractGraph interface from Graphs.jl. It is therefore possible to use it with other packages that work with Graphs.jl.

Vertices are not explicitly stored in TriangulatedPolygon. Only the total number of vertices is stored. They are implicitly labeled by the integers from 1 up to the total number of vertices.
Edges are stored as an adjacency list.


triangulated_polygon(n::Integer) :: TriangulatedPolygon

Create a triangulated convex n-gon.

Vertices are named from 1 to n in an anticlockwise manner. The inside is triangulated in a zig-zag pattern.

As an example, the output of triangulated_polygon(9) would be a graph that corresponds to the following triangulation of a 9-gon:

Graph Methods

The following methods overload some of the main functions from the Graphs.jl package.

nv(g::TriangulatedPolygon) :: Int

Return the number of vertices/points in the triangulated convex polygon g.

ne(g::TriangulatedPolygon) :: Int

Return the number of edges in the triangulated convex polygon g.

vertices(g::TriangulatedPolygon) :: Vector{Int}

Create a list of all the vertices in the triangulated convex polygon g.

edges(g::TriangulatedPolygon) :: Vector{SimpleEdge{Int32}}

Compute and return a list of all the edges in g.

Edges are not directed. It is, however, necessary for computations to define a source and a target. For TriangulatedPolygon, the source will be the incident vertex with the smaller id.

has_vertex(g::TriangulatedPolygon, v::Integer)

Return true if v is a vertex in g.

has_edge(g::TriangulatedPolygon, s::Integer, d::Integer)

Return true if g has an edge going from vertex s to vertex d.

neighbors(g::TriangulatedPolygon, v::Integer) :: Vector{Int32}

Return the list of all the vertices in g that are adjacent to v.

If you want to extrude some more information from a TriangulatedPolygon object, the following functions might be useful:

degrees(g::TriangulatedPolygon) :: Vector{Int32}

Compute a list of the degrees of every single vertex in g.

adjacency_matrix(g::TriangulatedPolygon) :: Matrix{Int32}

Compute the adjacency matrix for the triangulated graph g.

Flip an edge

is_flippable(g::TriangulatedPolygon, src::Integer, dst::Integer) :: Bool

Return whether or not the edge can be flipped.

Note that for a triangulation of a convex polygon, the inner edges are always flippable, while the outer edges cannot be flipped.

flip!(g::TriangulatedPolygon, src::Integer, dst::Integer) :: TriangulatedPolygon

Flip the the edge incident to src and dst in the triangulated convex polygon g.

flip(g::TriangulatedPolygon, src::Integer, dst::Integer) :: TriangulatedPolygon

Return the TriangulatedPolygon obtained from g by flipping the the edge incident to src and dst.

flip!(g::TriangulatedPolygon, e::Edge) :: TriangulatedPolygon

Flip the edge e in the triangulated convex polygon g.

flip(g::TriangulatedPolygon, e::Edge) :: TriangulatedPolygon

Return the triangulated polygon obtained by flipping the edge e in g.

flip_get_edge!(g::TriangulatedPolygon, src::Integer, dst::Integer) :: Tuple{Int32, Int32}

Flip the edge incident to the vertices src and dst and return the new endpoints of the flipped edge.