Convex Hull Algorithm - Graham Scan and Jarvis March tutorial

given a set of points on a two-dimensional plane a convex hull is a geometric object a polygon that encloses all of those points the vertices of this polygon maximize the area while minimizing the circumference here's the convex hull of this particular set of points note that if some additional points were to be included then the covering area is reduced while the circumference is increased likewise if some of the vertices of the convex hull are omitted then the resulting polygon won't cover all of the points in the set welcome to stable sort the convex hull has a wide variety of applications ranging from image recognition in robotics to even finding an animal's home range in ethology and in this episode we're going to look at two different algorithms for calculating it the first one is called Graham scan while the second is Jarvis March both of them are fairly simple conceptually but there are a few implementation pitfalls that I will point out Graham scan algorithm starts by first looping over all the points to select the one with the lowest y-coordinate this is the bottom most point and assuming low collinear points is therefore guaranteed to be one of the vertices of the convex hull of course it could just as well pick the topmost or the leftmost or the rightmost point but by convention it picks the bottom most then it sorts the remaining points ordering them by the angle that they make relative to the bottom most point and the horizontal you could see that the angles would range from 0 to 180 degrees given that the reference point is the bottom most one in a set finally the algorithm looks over those points in sorted order effectively scanning in the counterclockwise direction each point is placed on a stack but only if it makes a line with the kernel clockwise turn relative to the previous two points on the stack if that is not the case then the previous point is popped off the stack the algorithm continues popping points of the stack until the resulting turn is Conner clockwise in this example points 2 & 3 were placed on a stack because at the time the connecting lines were making Conner clockwise turns but point four creates a clockwise turn so we roll back popping off point three and then also point two until the resulting line is again making a counterclockwise turn point-five creates a counterclockwise turn so it's placed on the stack point six is then placed on a stack since it could potentially be part of the convex hull we don't know yet but point seven creates a clockwise turn so we'll pop point six off of the stack and so on until we finally get back to the starting point let's talk about some of the implementation details that you'll need to handle first of all to determine if it's a clockwise turn or not you could use trigonometry to calculate the angles in degrees and then compare them but we don't really care what the actual angles are we just want to know if it's a clockwise turn or not to do just that and save a few CPU cycles in a process we can make use of a cross product if you don't recall the cross product of two vectors V and W calculates the signed area of the parallelogram that is formed if you connect the two vectors like so if V is on the right of W then the cross product ends up positive but if B is on the left of W then it's negative technically for the math purists out there the cross product is a perpendicular vector whose length equals the area of the parallelogram while the sign tells the direction in which it is pointing but for our purposes we just want to know the sign of the operation here are a couple of examples to illustrate how to go about calculating it along with a few lines of code that takes to implement it as you can see it's a very simple calculation this formula could also be used to sort the points the only thing to be caches off is handling points that are collinear since we only want to keep the peripheral points make sure that your comparator orders the points from left to right when the slope of a line is positive and in Reverse when the slope is vertical or negative this is a little tricky especially when dealing with floating point coordinates so take a look at the source code linked in the description the first step of finding the lowest point on the y axis takes order n since it just needs to iterate over every point so during the points in place takes order n log n while the main algorithm takes another order n number of operations since each point is pushed and popped off of the stack at most once therefore the overall running time of Grand scan is order n log n driven by the sort phase now that we've covered the Graham scan algorithm we can talk about its cousin the job is March which is actually a little simpler it also starts off by finding the lowest point on the y-axis for the first vertex but then instead of doing any kind of sorting it just loops through all the points again in a brute-force way to find a point that makes the smallest color clockwise angle in reference to the previous vertex it simply repeats the situation through all the points until all the vertices are determined and it gets back to the starting point more formally the running time of Jarvis March is order n multiplied by H where H is the number of vertices of course if the number of vertices is large such as when you have all the points along the perimeter then the running time turns for the ugly of order N squared by the way the function for finding the point with the smallest counterclockwise angle is exactly the same as the one used previously that makes use of the cross product as a little bonus dealing with collinear points is also a little easier because here you just need to pick the point that is furthest away distance wise without needing to worry about the slope of the line both job is March and Graham scan were invented in early 70s but in 1996 a young scientist at the age of 20 by the name Timothy Chan came up with an improved algorithm that runs in order n log H to keep the length of this video in check I won't go into the details today but there is a link to his paper in the description if you'd like to see an explanation of it on this channel please do let me know in the comments I'll put together an episode if there's enough interest but that's it for this video I hope you enjoyed it if you did please click that thumbs up button and thank you for watching

Channel: Stable Sort

Views: 23,402

Rating: 4.9851441 out of 5

Keywords: algorithm, computer science, programming tutorial, coding tuturial, gift wrapping algorithm

Id: B2AJoQSZf4M

Length: 7min 24sec (444 seconds)

Published: Sun Apr 19 2020