# Path Finding – Convex Hull Part 1

This is part 1 of a series on path finding.

The gaming industry has developed so many algorithms that are very applicable to the world of robotics.

The developers of early games had to conquer many kinds of issues to bring their virtual bad guys to life. One of these issues was path finding, because the baddies have to run around obstacles to attack the player. Sometimes these obstacles are quite complicated; the obstacles might be U shaped, or form long winding paths. Game developers had to come up with sophisticated algorithms to get their bad guys through virtual obstacle courses. Robust path finding is essential for autonomous navigation in real world robotics.

This blog series will explain some algorithms used in path finding.

### The Scenario

Let’s pretend an army tank needs to travel to a safe spot. Let’s call the safe spot LZ. :shrug:

The tank needs to get to LZ but there are some obstacles (the green polygons).

### The Steps

- Remove concave points by creating a
*convex hull*around the obstacles - Create a
*visibility graph*for every point - Run a searching algorithm over the visibility graph to find the shortest way to the LZ

### Creating A Convex Hull

The first step is to create a convex hull around each of the obstacles. The convex hull is the polygon with all of the concave points removed. Imagine wrapping the polygons in gift wrap and the gift wrap is hugging the outer points but hiding the inner points – that’s what the convex hull looks like. The convex hull is found using gift wrapping algorithms.

This step is a good way to trim down the number of points that must be search through in the later steps. It’s best to just remove concave points altogether because they will never be on the shortest path between two points. You could probably tell that intuitively.

Here is a Javascript implementation of the gift wrapping algorithm

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 |
// this function if a point if on the left side of the line defined by a and b function isLeft(a, b, point) { return ((b[0] - a[0]) * (point[1] - a[1]) - (b[1] - a[1]) * (point[0] - a[0])) > 0; } function buildConvexPolys() { convexPolys = []; for (let p in polygons) { console.log("polygon: " + p); var poly = polygons[p]; var convexPoly = []; // find left-most point (lowest x value) // because this is an extremity it is guaranteed to be on the hull var pointOnHull = poly[0]; for (let r in poly) { if (pointOnHull[0] < poly[r][0]) { pointOnHull = poly[r]; } } var endPoint; var i = 0; do { convexPoly[i] = pointOnHull; // assign the end point, to be updated as we loop over the polygon points endPoint = poly[0]; for (let j = 0; j < poly.length; j++) { // if end point is pointOnHull // OR convexPoly[i] is on the left of the line from endPoint to poly[j] if ((endPoint === pointOnHull) || (isLeft(convexPoly[i], endPoint, poly[j]) === true)) { endPoint = poly[j]; } } pointOnHull = endPoint; i += 1; } while (endPoint != convexPoly[0]) convexPolys.push(convexPoly); } } |

### Alternatives To Gift Wrapping

The gift wrapping algorithm is simple and robust but is not the fastest. Consider using this alternative approach if the polygon does not self-intersect and all the points are in order.

- Iterate over each point
- if the angle formed between this point and the next MINUS the angle between this point and the last is GREATER THAN 180 degrees (PI), remove this point

The Wikipedia has a list of Convex hull algorithms – LINK