In the previous video, we learned about the Jarvis-March algorithm, an algorithm to find the convex hull of a set of points. But the downside of it was its time complexity, O of n times h, where n is the total number of points and h the number of points on the hull. Because n times h is close to n squared when h is close to n, which is quite slow. Today, we will see another algorithm that solves the same problem but more efficiently, the Graham's Gaunt algorithm. Quick reminder, the convex hull of a set of points is the smallest convex polygon that contains all the points inside it.
Convex polygon means that all interior angles are less than or equal to 180 degrees. Okay, imagine that we have this set of points, we start by finding the bottom most point the one with the smallest y coordinate, let's name it P zero. Now we have a polar angle between P zero and each other point.
What do we do is that we saw them according to the polar angle. Here is the first one, then the second one, then third one, and so on. Basically, we sort points according to their polar angle with the bottom most point.
From here, we can start working will traverse the sorted points. We start by putting the first two points on the whole. And from here, for each remaining point, we check the orientation of the before last point on the whole, the last point on the whole and the actual point.
For example, with this one, the orientation is counterclockwise, we can dock they put it on the whole, it becomes a new last point. Next point. Here the orientation is not counterclockwise. It means that the last point shouldn't be on the whole, we remove it. Now the orientation is counterclockwise, we can insert the actual point.
Next point counterclockwise with darkly insert. Next point counterclockwise with darkly insert. Next point, the orientation is clockwise, we pop the last point. The orientation is still clockwise, we pop the last point.
And here the orientation became counterclockwise, we can insert the actual point. Basically, we keep popping until the orientation of before last last endpoint becomes counterclockwise. In other words, we remove all the points we inserted before the don't need to be on the whole. Let's continue next point, the orientation is clockwise with pop, the orientation is now counterclockwise we can insert next point counterclockwise we insert next point counterclockwise we insert. Next point counterclockwise we insert next point clockwise we pop clockwise we pop still clockwise we pop and now counterclockwise we insert and the process continues like that until we finish traversing points We finished traversing the points we got the convex hull.
What we did here is that we use the stack to store the points that are actually on the whole, then for each new point, we keep popping until we have a counterclockwise rotation between the before last point, the point on top of the stack and the actual point. By doing so, we have counterclockwise rotations only, which produces the convex hull of the set of points. Before being able to implement the solution, we must know two things how to calculate the polar angle and how to find the rotation of three points.
For the polar angle, we use arc tangent, a trigonometric function. And for the orientation, we talked about it in the previous video that you should watch by the way. because we also used it in the Jarvis March algorithm.
Basically, we just calculate the slope of the line that passes from P one and P two, the slope of the line that passes from P two and P three and we compare. Now we can start writing our solution. We start by finding P zero, the bottom most left most point, we write min points where the comparison key is the y coordinate the x coordinate. After it, we saw the points were four point P, the keys, the polar angle between P zero and P, then the distance between P zero and P to say that if two points have the same polar angle, the one that is closer to P zero comes before the other one. Now we can start working.
We'll first create Hall, which is the stock that will contain points on the whole than whichever's points. Remember that for each point, we keep popping while certain condition is still true. That condition is not having a counterclockwise orientation between the before last point, the last point as actual point in code, the before last point is how of minus two, the before last element, the last one is how of minus one, the last element, the one on top of the stack, and the actual point is points of I, we also need to make sure that there are at least two elements in the stack.
Otherwise, we don't have a before last element. In code, we write while length of hull is greater than or equal to two, and the orientation of half minus two half minus one and points of I is not one. One means counterclockwise, we pop.
After we finish popping, we just push the actual point on the stack and we continue as we were doing in the example. After traversing all the points, we just return the whole. And that's how the Graham's kind of algorithm works.
For the top complexity, finding P zero costs of n because we just traverse points. So only the points cost of analog and because calculating the polar angle is an old one, then we have a loop that is traversing the endpoints. Here, even if we have an inner loop, but the total number of iterations done by the while loop is an because every point is pushed and popped only once and we have endpoints.
So in total, this loop cost to n, we get t of n is equal to O of n plus of analog n plus two n, which gives an O of analog n time complexity. And for the space complexity, we got off and because of the whole. Okay, now we've seen two convex hulls algorithms, but it would be good to see an application of convex hulls. This is why in the next video, we will see how can a robot find the shortest path to go between two points by avoiding a polygon obstacle.
See you in the next video.