Use math to solve problems in Unity with C#

10. Triangulation

Here you will learn everything about how to triangulate a polygon and random points. Remember to use the data structures from the first page, such as Vertex and Triangle, and everything should be in x-z-space (Create a new Vertex object with a Vector3 as its position and where y = 0).

Triangulate a convex polygon

Triangulating a convex polygon is very easy, so we start with that. This algorithms assumes that the vertices you want to triangulate are sorted along the hull of the polygon. If they are not sorted you can use a convex hull algorithm to sort them!

public static List<Triangle> TriangulateConvexPolygon(List<Vertex> convexHullpoints)
{
	List<Triangle> triangles = new List<Triangle>();

	for (int i = 2; i < convexHullpoints.Count; i++)
	{
		Vertex a = convexHullpoints[0];
		Vertex b = convexHullpoints[i - 1];
		Vertex c = convexHullpoints[i];

		triangles.Add(new Triangle(a, b, c));
	}

	return triangles;
}

And this is the result:

Triangulation of convex polygon

Triangulate a concave polygon

Triangulating a concave polygon is similar to triangulating a convex polygon. There are several algorithms you can use, but we are here going to use an algorithm called ear clipping. It is explained in this pdf: Triangulation by Ear Clipping. The idea is that we identify the polygon's ears (an ear is simply a triangle), and then we cut ears from the polygon until only one triangle is left, and then we have triangulated the polygon.

This assumes you can clamp a list, knows how to tell if a triangle is oriented clockwise, and if a point is in a triangle. If not, you can find the algorithms here: A collection of useful algorithms.

//This assumes that we have a polygon and now we want to triangulate it
//The points on the polygon should be ordered counter-clockwise
//This alorithm is called ear clipping and it's O(n*n) Another common algorithm is dividing it into trapezoids and it's O(n log n)
//One can maybe do it in O(n) time but no such version is known
//Assumes we have at least 3 points
public static List<Triangle> TriangulateConcavePolygon(List<Vector3> points)
{
	//The list with triangles the method returns
	List<Triangle> triangles = new List<Triangle>();

	//If we just have three points, then we dont have to do all calculations
	if (points.Count == 3)
	{
		triangles.Add(new Triangle(points[0], points[1], points[2]));

		return triangles;
	}



	//Step 1. Store the vertices in a list and we also need to know the next and prev vertex
	List<Vertex> vertices = new List<Vertex>();

	for (int i = 0; i < points.Count; i++)
	{
		vertices.Add(new Vertex(points[i]));
	}

	//Find the next and previous vertex
	for (int i = 0; i < vertices.Count; i++)
	{
		int nextPos = MathUtility.ClampListIndex(i + 1, vertices.Count);

		int prevPos = MathUtility.ClampListIndex(i - 1, vertices.Count);

		vertices[i].prevVertex = vertices[prevPos];

		vertices[i].nextVertex = vertices[nextPos];
	}



	//Step 2. Find the reflex (concave) and convex vertices, and ear vertices
	for (int i = 0; i < vertices.Count; i++)
	{
		CheckIfReflexOrConvex(vertices[i]);
	}

	//Have to find the ears after we have found if the vertex is reflex or convex
	List<Vertex> earVertices = new List<Vertex>();
	
	for (int i = 0; i < vertices.Count; i++)
	{
		IsVertexEar(vertices[i], vertices, earVertices);
	}

	

	//Step 3. Triangulate!
	while (true)
	{
		//This means we have just one triangle left
		if (vertices.Count == 3)
		{
			//The final triangle
			triangles.Add(new Triangle(vertices[0], vertices[1], vertices[2]));

			break;
		}

		//Make a triangle of the first ear
		Vertex earVertex = earVertices[0];

		Vertex earVertexPrev = earVertex.prevVertex;
		Vertex earVertexNext = earVertex.nextVertex;

		Triangle newTriangle = new Triangle(earVertex, earVertexPrev, earVertexNext);

		triangles.Add(newTriangle);

		//Remove the vertex from the lists
		earVertices.Remove(earVertex);

		vertices.Remove(earVertex);

		//Update the previous vertex and next vertex
		earVertexPrev.nextVertex = earVertexNext;
		earVertexNext.prevVertex = earVertexPrev;

		//...see if we have found a new ear by investigating the two vertices that was part of the ear
		CheckIfReflexOrConvex(earVertexPrev);
		CheckIfReflexOrConvex(earVertexNext);

		earVertices.Remove(earVertexPrev);
		earVertices.Remove(earVertexNext);

		IsVertexEar(earVertexPrev, vertices, earVertices);
		IsVertexEar(earVertexNext, vertices, earVertices);
	}

	//Debug.Log(triangles.Count);

	return triangles;
}



//Check if a vertex if reflex or convex, and add to appropriate list
private static void CheckIfReflexOrConvex(Vertex v)
{
	v.isReflex = false;
	v.isConvex = false;

	//This is a reflex vertex if its triangle is oriented clockwise
	Vector2 a = v.prevVertex.GetPos2D_XZ();
	Vector2 b = v.GetPos2D_XZ();
	Vector2 c = v.nextVertex.GetPos2D_XZ();

	if (Geometry.IsTriangleOrientedClockwise(a, b, c))
	{
		v.isReflex = true;
	}
	else
	{
		v.isConvex = true;
	}
}



//Check if a vertex is an ear
private static void IsVertexEar(Vertex v, List<Vertex> vertices, List<Vertex> earVertices)
{
	//A reflex vertex cant be an ear!
	if (v.isReflex)
	{
		return;
	}

	//This triangle to check point in triangle
	Vector2 a = v.prevVertex.GetPos2D_XZ();
	Vector2 b = v.GetPos2D_XZ();
	Vector2 c = v.nextVertex.GetPos2D_XZ();

	bool hasPointInside = false;

	for (int i = 0; i < vertices.Count; i++)
	{
		//We only need to check if a reflex vertex is inside of the triangle
		if (vertices[i].isReflex)
		{
			Vector2 p = vertices[i].GetPos2D_XZ();

			//This means inside and not on the hull
			if (Intersections.IsPointInTriangle(a, b, c, p))
			{
				hasPointInside = true;

				break;
			}
		}
	}

	if (!hasPointInside)
	{
		earVertices.Add(v);
	}
}

And this is the result:

Triangulation of concave polygon

Triangulate random points

Let's say you have points in the plane you want to triangulate. According to Wikipedia, there are three algorithms you can use: Triangle Splitting Algorithm, Incremental Algorithm, and Delaunay Triangulation Algorithm. We are in this section going to cover the first two.


Triangle Splitting Algorithm

The idea here is that we first find the convex hull of the points, then we use one of the above algorithms to triangulate the convex hull. Now we just add the points that are within the hull one-by-one. Each time we add a new point, we check which triangle it is in, then we split that triangle into three triangles. The result is not pretty but it is a valid triangulation, which is good in most cases!

This assumes you can can tell if a point is in a triangle. If not, you can find the algorithm here: A collection of useful algorithms.

using System.Collections;
using System.Collections.Generic;
using UnityEngine;

//Triangulate random points by first generating the convex hull of the points, then triangulate the convex hull
//and then add the other points and split the triangle the point is in
public static class TriangleSplittingAlgorithm
{
    public static List<Triangle> TriangulatePoints(List<Vertex> points)
    {
        //Generate the convex hull - will also remove the points from points list which are not on the hull
        List<Vertex> pointsOnConvexHull = HullAlgorithms.JarvisMarch(points);

        //Triangulate the convex hull
        List<Triangle> triangles = TriangulateHullAlgorithms.TriangulateConvexPolygon(pointsOnConvexHull);

        //Add the remaining points and split the triangles
        for (int i = 0; i < points.Count; i++)
        {
            Vertex currentPoint = points[i];
            
            //2d space
            Vector2 p = new Vector2(currentPoint.position.x, currentPoint.position.z);
        
            //Which triangle is this point in?
            for (int j = 0; j < triangles.Count; j++)
            {
                Triangle t = triangles[j];
            
                Vector2 p1 = new Vector2(t.v1.position.x, t.v1.position.z);
                Vector2 p2 = new Vector2(t.v2.position.x, t.v2.position.z);
                Vector2 p3 = new Vector2(t.v3.position.x, t.v3.position.z);

                if (Intersections.IsPointInTriangle(p1, p2, p3, p))
                {
                    //Create 3 new triangles
                    Triangle t1 = new Triangle(t.v1, t.v2, currentPoint);
                    Triangle t2 = new Triangle(t.v2, t.v3, currentPoint);
                    Triangle t3 = new Triangle(t.v3, t.v1, currentPoint);

                    //Remove the old triangle
                    triangles.Remove(t);

                    //Add the new triangles
                    triangles.Add(t1);
                    triangles.Add(t2);
                    triangles.Add(t3);

                    break;
                }
            }
        }

        return triangles;
    }
}

And this is the result before we add the interior points:

Triangulation of random points before splitting

And this is the final triangulation:

Triangulation of random points splitting


Incremental Algorithm

According to Wikipedia, we should sort the points according to x-coordinates. The first three points determine a triangle. Consider the next point in the ordered set and connect it with all previously considered points which are visible to the point. Continue this process of adding points until all has been processed.

The trick here is how can we say an edge is visible to a point? What I came up with is that we should find the center of an edge belonging to a triangle and connect this center point with the point we want to add. If this edge doesn't intersect another edge, then it's visible. This assumes you can can tell if two lines are intersecting. If not, you can find the algorithm here: A collection of useful algorithms.

using System.Collections;
using System.Collections.Generic;
using UnityEngine;
using System.Linq;

//Sort the points along one axis. The first 3 points form a triangle. Consider the next point and connect it with all
//previously connected points which are visible to the point. An edge is visible if the center of the edge is visible to the point.
public static class IncrementalTriangulationAlgorithm
{
    public static List<Triangle> TriangulatePoints(List<Vertex> points)
    {
        List<Triangle> triangles = new List<Triangle>();

        //Sort the points along x-axis
        //OrderBy is always soring in ascending order - use OrderByDescending to get in the other order
        points = points.OrderBy(n => n.position.x).ToList();

        //The first 3 vertices are always forming a triangle
        Triangle newTriangle = new Triangle(points[0].position, points[1].position, points[2].position);
        
        triangles.Add(newTriangle);

        //All edges that form the triangles, so we have something to test against
        List<Edge> edges = new List<Edge>();

        edges.Add(new Edge(newTriangle.v1, newTriangle.v2));
        edges.Add(new Edge(newTriangle.v2, newTriangle.v3));
        edges.Add(new Edge(newTriangle.v3, newTriangle.v1));

        //Add the other triangles one by one
        //Starts at 3 because we have already added 0,1,2
        for (int i = 3; i < points.Count; i++)
        {
            Vector3 currentPoint = points[i].position;

            //The edges we add this loop or we will get stuck in an endless loop
            List<Edge> newEdges = new List<Edge>();

            //Is this edge visible? We only need to check if the midpoint of the edge is visible 
            for (int j = 0; j < edges.Count; j++)
            {
                Edge currentEdge = edges[j];

                Vector3 midPoint = (currentEdge.v1.position + currentEdge.v2.position) / 2f;

                Edge edgeToMidpoint = new Edge(currentPoint, midPoint);

                //Check if this line is intersecting
                bool canSeeEdge = true;

                for (int k = 0; k < edges.Count; k++)
                {
                    //Dont compare the edge with itself
                    if (k == j)
                    {
                        continue;
                    }

                    if (AreEdgesIntersecting(edgeToMidpoint, edges[k]))
                    {
                        canSeeEdge = false;

                        break;
                    }
                }

                //This is a valid triangle
                if (canSeeEdge)
                {
                    Edge edgeToPoint1 = new Edge(currentEdge.v1, new Vertex(currentPoint));
                    Edge edgeToPoint2 = new Edge(currentEdge.v2, new Vertex(currentPoint));

                    newEdges.Add(edgeToPoint1);
                    newEdges.Add(edgeToPoint2);

                    Triangle newTri = new Triangle(edgeToPoint1.v1, edgeToPoint1.v2, edgeToPoint2.v1);

                    triangles.Add(newTri);
                }
            }


            for (int j = 0; j < newEdges.Count; j++)
            {
                edges.Add(newEdges[j]);
            }
        }


        return triangles;
    }



    private static bool AreEdgesIntersecting(Edge edge1, Edge edge2)
    {
        Vector2 l1_p1 = new Vector2(edge1.v1.position.x, edge1.v1.position.z);
        Vector2 l1_p2 = new Vector2(edge1.v2.position.x, edge1.v2.position.z);
        
        Vector2 l2_p1 = new Vector2(edge2.v1.position.x, edge2.v1.position.z);
        Vector2 l2_p2 = new Vector2(edge2.v2.position.x, edge2.v2.position.z);

        bool isIntersecting = Intersections.AreLinesIntersecting(l1_p1, l1_p2, l2_p1, l2_p2, true);

        return isIntersecting;
    }
}

And this is the final triangulation:

Triangulation of random points incremental

If you want to produce triangulations that look better you have to learn the Delaunay triangulation algorithm, which is the topic of another section of this tutorial.