Use Linear Algebra to solve problems in Unity with C#

8. Find the convex hull of random points

What if you have several random points and want to find the smallest shape that's enclosing these points. This shape is called a convex hull, and there are several algorithms you can use to find this convex hull. You can find them here: Convex hull algorithms. We are here going to use Graham's scan algorithm. It works like this:

Basic idea behind Graham sort algorithm

So what's going on? Step 1 is to sort all vertices to figure out which one has the smallest x coordinate. Then step 2 is to measure the angle from this x coordinate to all other vertices. And then we sort these angles from smallest to largest. Now we have two points on the convex hull: the vertex with the smallest x coordinate and the vertex with the smallest angle to the smallest x coordinate.

The remaining part of Graham's scan algorithm is difficult to explain with words, so you should watch this video to understand what's going on: Convex Hull Algorithm Presentation. But the basic idea is that we continue to check vertices with larger and larger angles to the smallest x coordinate while checking if the triangle formed by the latest three vertices is clockwise or counter-clockwise. If the triangle is clockwise, we have to step back while removing the second-to-last vertex until the triangle is again counter-clockwise.

To make all this work in Unity you need a plane with a collider attached to it and a sphere. The first script will just let you create spheres when you click with a mouse button:

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

//Add objects to a scene with mouse click, stores the objects transforms in a list
public class AddObjects : MonoBehaviour 
{
    public GameObject toAddObj;

    private List<Transform> activeObjects = new List<Transform>();

    private ConvexHull convexHullObj = new ConvexHull();


	void Start() 
	{
        //Add the object that's already in the scene
        activeObjects.Add(toAddObj.transform);
	}
	
	

	void Update() 
	{
        //Add object with mouse click
        if (Input.GetMouseButtonDown(0))
        {
            RaycastHit hit;
            
            if (Physics.Raycast(Camera.main.ScreenPointToRay(Input.mousePosition), out hit))
            {
                //Add an object at this position
                GameObject newObj = Instantiate(toAddObj) as GameObject;

                newObj.transform.position = hit.point;

                activeObjects.Add(newObj.transform);
            }
        }


        //The list with all object coordinates
        List<Vector3> objectCoordinates = new List<Vector3>();

        for (int i = 0; i < activeObjects.Count; i++)
        {
            objectCoordinates.Add(activeObjects[i].position);
        }


        //Create the convex hull if we have at least a triangle
        if (objectCoordinates.Count > 2)
        {
            List<Vector3> convexHullCoordinates = convexHullObj.GenerateConvexHull(objectCoordinates);

            //Display the convex hull with a line
            convexHullObj.DisplayConvexHull(convexHullCoordinates);
        }
    }
}

The other script will create the convex hull with Graham's scan algorithm, and it will also display the result with a line. Make sure you are in scene-view if you want to see the line!

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

public class ConvexHull
{
    //Generate a convex hull with Graham's Scan algorithm
    public List<Vector3> GenerateConvexHull(List<Vector3> unSortedList)
    {
        List<Vector3> convexHullList = new List<Vector3>();

        //Step 1 - Find the vertice with the smallest x coordinate
        //Init with just the first in the list
        float smallestValue = unSortedList[0].x;
        int smallestIndex = 0;

        //Check if we can find a smaller value
        for (int i = 1; i < unSortedList.Count; i++)
        {
            if (unSortedList[i].x < smallestValue)
            {
                smallestValue = unSortedList[i].x;

                smallestIndex = i;
            }
        }

        //Remove the smallest coordinate from the list and add it to the list 
        //with convex hull vertices because this vertex is on the convex hull
        convexHullList.Add(unSortedList[smallestIndex]);

        unSortedList.RemoveAt(smallestIndex);


        //Step 2 - Sort the vertices based on angle to start vertex
        Vector3 firstPoint = convexHullList[0];
        //Need a direction to get an angle with Vector3.Angle()
        Vector3 startVec = (firstPoint + new Vector3(0f, 0f, -1f)) - firstPoint;

        //Important that everything is in 2d space
        firstPoint.y = 0f;
        startVec.y = 0f;

        //Sort from smallest to largest angle
        unSortedList = unSortedList.OrderBy(n => Vector3.Angle(startVec, new Vector3(n.x, 0f, n.z) - firstPoint)).ToList();

        //Reverse because it's faster to remove vertices from the end
        unSortedList.Reverse();


        //Step 3 - The vertex with the smallest angle is also on the convex hull so add it
        convexHullList.Add(unSortedList[unSortedList.Count - 1]);

        unSortedList.RemoveAt(unSortedList.Count - 1);


        //Step 4 - The main algorithm to find the convex hull
        //To avoid infinite loop
        int safety = 0;
        while (unSortedList.Count > 0 && safety < 10000)
        {
            //Get the vertices of the current triangle abc
            Vector3 a = convexHullList[convexHullList.Count - 2];
            Vector3 b = convexHullList[convexHullList.Count - 1];

            Vector3 c = unSortedList[unSortedList.Count - 1];

            unSortedList.RemoveAt(unSortedList.Count - 1);

            convexHullList.Add(c);

            //Is this a clockwise or a counter-clockwise triangle ?
            //May need to back track several steps in case we messed up at an earlier point
            while (isClockWise(a, b, c) && safety < 10000)
            {
                //Remove the next to last vertex because we know it aint on the convex hull
                convexHullList.RemoveAt(convexHullList.Count - 2);

                //Get the vertices of the current triangle abc
                a = convexHullList[convexHullList.Count - 3];
                b = convexHullList[convexHullList.Count - 2];
                c = convexHullList[convexHullList.Count - 1];

                safety += 1;
            }

            safety += 1;
        }

        return convexHullList;
    }


    //Is a triangle in 2d space oriented clockwise or counter-clockwise
    private bool isClockWise(Vector3 a, Vector3 b, Vector3 c)
    {
        float signedArea = (b.x - a.x) * (c.z - a.z) - (b.z - a.z) * (c.x - a.x);

        if (signedArea > 0)
        {
            return false;
        }
        else
        {
            return true;
        }

        //There's also the case when abc is a line (signedArea = 0), but ignore that here!
    }


    //Display in which order the vertices have been added to a list
    //by connecting a line between all vertices
    public void DisplayConvexHull(List<Vector3> verticesList)
    {
        float height = 0.1f;
        
        for (int i = 0; i < verticesList.Count; i++)
        {
            Vector3 start = verticesList[i] + Vector3.up * height;

            //Connect the end with the start
            int endPos = i + 1;

            if (i == verticesList.Count - 1)
            {
                endPos = 0;
            }

            Vector3 end = verticesList[endPos] + Vector3.up * height;

            Debug.DrawLine(start, end, Color.blue);
        }
    }
}

It should look like this in Unity:

Convex hull animated gif