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

Structures

FlipGraphs.TriangulatedPolygon — Type
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.

Constructors

FlipGraphs.triangulated_polygon — Function
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.

Graphs.nv — Method
nv(g::TriangulatedPolygon) :: Int

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

Graphs.ne — Method
ne(g::TriangulatedPolygon) :: Int

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

Graphs.vertices — Method
vertices(g::TriangulatedPolygon) :: Vector{Int}

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

Graphs.has_vertex — Method
has_vertex(g::TriangulatedPolygon, v::Integer)

Return true if v is a vertex in g.

Graphs.edges — Method
edges(g::TriangulatedPolygon{T}) :: Vector{SimpleEdge{T}} where T<:Integer

Compute and return a list of all the inner 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.

FlipGraphs.edges_inner — Method
edges_inner(g::TriangulatedPolygon{T}) :: Vector{SimpleEdge{T}} where T<:Integer

Compute and return a list of all the edges in g. These are exactly the flippable 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.

FlipGraphs.edges_outer — Method
edges_outer(g::TriangulatedPolygon{T}) :: Vector{SimpleEdge{T}} where T<:Integer

Compute and return a list of all the outer edges in g. These are exactly the non-flippable 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.

Graphs.has_edge — Method
has_edge(g::TriangulatedPolygon, s::Integer, d::Integer)

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

FlipGraphs.is_inner — Method
is_inner(g::TriangulatedPolygon, e::Edge)

Return true if e is an inner edge in the TriangulatedPolygon.

FlipGraphs.is_outer — Method
is_outer(g::TriangulatedPolygon, e::Edge)

Return true if e is an outer edge in the TriangulatedPolygon.

Graphs.neighbors — Method
neighbors(g::TriangulatedPolygon, v::Integer) :: Vector{Int32}

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

FlipGraphs.is_identical — Method
is_identical(g1::TriangulatedPolygon, g2::TriangulatedPolygon)

Return true if 'g1' and 'g2' are the same triangulated polygon.

FlipGraphs.rotate! — Method
rotate!(g::TriangulatedPolygon, i::Integer)

Rotate g by i steps anticlockwise.

A rotation by nv(g) would simply yield g again

FlipGraphs.mirror! — Method
mirror!(g::TriangulatedPolygon)

Mirror g along the middle axis passing through g.

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

FlipGraphs.degrees — Method
degrees(g::TriangulatedPolygon) :: Vector{Int32}

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

FlipGraphs.relative_degree — Method
relative_degree(g::TriangulatedPolygon, u::Integer, V::Vector{<:Integer}) :: Vector{<:Integer}

Count the number of edges in g going from u to a vertex in V.

FlipGraphs.relative_degrees — Method
relative_degrees(g::TriangulatedPolygon, U::Vector{<:Integer}, V::Vector{<:Integer}) :: Vector{<:Integer}

Count, for each vertex in U, the number of incident edges, which are also incident to an edge in V.

FlipGraphs.adjacency_matrix — Method
adjacency_matrix(g::TriangulatedPolygon) :: Matrix{Int32}

Compute the adjacency matrix for the triangulated graph g.

FlipGraphs.diameter — Method
diameter(g::TriangulatedPolygon)

Compute the diameter of the TriangulatedPolygon g.

Flip an edge

FlipGraphs.is_flippable — Method
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.

FlipGraphs.flip! — Method
flip!(g::TriangulatedPolygon, src::Integer, dst::Integer) :: TriangulatedPolygon

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

FlipGraphs.flip — Method
flip(g::TriangulatedPolygon, src::Integer, dst::Integer) :: TriangulatedPolygon

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

FlipGraphs.flip! — Method
flip!(g::TriangulatedPolygon, e::Edge) :: TriangulatedPolygon

Flip the edge e in the triangulated convex polygon g.

FlipGraphs.flip — Method
flip(g::TriangulatedPolygon, e::Edge) :: TriangulatedPolygon

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

FlipGraphs.flip_get_edge! — Function
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.