Week 3 Day 2 - Convex Hulls Part 1
2Today we talked about setting up a source management system (I typically use Git but Unreal Engine officially has blessed Perforce, which I'm not familiar with).
Then we talked about creating convex hulls. A convex hull algorithm takes a bunch of points as input and returns a convex hull (a polygon in which you can see all vertices from every point on the inside) as the result. We typically hold convex hulls as a series of line segments (or points if you want to not waste space) held clockwise (or counterclockwise - just be consistent). Then you can see if a point is inside the convex hull either with the line intersection test or by doing a cross product between the point and all lines in the hull.
There are several algorithms to make a convex hull. We're doing a version of Graham's Scan called the Andrew's Monotone Chain Algorithm (https://en.wikibooks.org/wiki/Algorithm_Implementation/Geometry/Convex_hull/Monotone_chain). Since it sorts the points it is an O(NlogN) algorithm, which isn't the fastest - Chan's Algorithm can do it in O(NlogH) time, where H is the number of lines in the Hull.
You do the algorithm twice, once from left to right to do the top half of the hull, and once from right to left doing the bottom half. You start with one line segment on a stack of line segments (holding the line from point A to point B) then repeatedly do the following:
1) Add a line segment from the last point we added to the hull to the stack
2) Check if the segment we just added will cause a left turn (which isn't allowed in a convex hull). If we did, we delete the last two segments (say D to E and E to F) and add a new segment connecting the first point of the last one and the second point of the current one (i.e. D to F). Then repeat to see if a left turn occured.
3) When we add the last point we are done with the upper half of the hull.
Then repeat going the other way (right to left) to do the bottom half of the hull.