# 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:

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
{

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

private ConvexHull convexHullObj = new ConvexHull();

void Start()
{
}

void Update()
{
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;

}
}

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

for (int i = 0; i < activeObjects.Count; i++)
{
}

//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

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

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

//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: