Convex Hull Algorithm - Graham Scan and Jarvis March tutorial
Vložit
- čas přidán 27. 07. 2024
- Given a set of points on a 2 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.
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.
The Convex Hull has a wide variety of applications, ranging from image recognition in robotics to determining animal’s home range in ethology. And in this tutorial we are going to look at how to calculate the Convex Hull using two different algorithms. The first one is called “Graham Scan” while the second is called “Jarvis March”, also known as "gift wrapping algorithm". Both of them are conceptually fairly simple, but there are a few tricky implementation pitfalls that I will point out.
Graham Scan algorithm (en.wikipedia.org/wiki/Graham_...) starts by first looping over all of the points to select the one with the lowest Y coordinate. This is the bottom most point and, assuming no collinear points, is therefore guaranteed to be one of the vertices of the Convex Hull. Of course, it could just as well pick the top most 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 can see that the angles would range from 0 to 180 degrees, given that the reference point is the bottom most one in the set.
Finally, the algorithm loops 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 a counterclockwise turn relative to the previous 2 points on the stack. If that is not the case, then the previous point is popped off the stack. The algorithm continues popping points off of the stack until the resulting turn is counterclockwise.
Graham Scan Java source code:
bitbucket.org/StableSort/play...
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 calculate the degrees of the angles using trigonometry 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 the process, we can make use of a cross product.
If you don’t recall, the cross product of two vectors V & 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 V is on the left of W, then it’s negative.
Now that we covered the Graham Scan algorithm, we can talk about its cousin, the Jarvis March (en.wikipedia.org/wiki/Gift_wr..., which is actually a little simpler. It also starts off by finding the lowest point on the y-axis for its 1st vertex.
But then, instead of doing any kind of sorting, it just loops through all of the points again in a brute force way to find the point that makes the smallest counterclockwise angle in reference to the previous vertex. It simply repeats this iteration through all of the points until all of the vertices are determined and it gets back to the starting point.
Jarvis March source code in Java:
bitbucket.org/StableSort/play...
Looping through every point for each vertex may seem like a lot more inefficient, but the algorithm terminates as soon as it finds all of the vertices. This means that if the number of vertices is small, in particular, less than log of n, then it’ll perform better than the Graham Scan algorithm.
More formally, the running time of Jarvis March is O(n * h) where h is the number of vertices.
Of course, if the number of vertices is large, such as when all of the points are along the perimeter, then the running time turns for the ugly of O(n^2).
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 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.
Timothy Chan’s paper for divide and conquer algorithm:
link.springer.com/content/pdf...
Written and narrated by Andre Violentyev
Both Jarvis March and Graham Scan algorithms are very well explained. Amazingly, in less that 8 minutes! Thanks and keep up the good work!
Thanks, will do!
This is by far the best explanation on Jarvis and Graham scan algorithm yet precise
Thanks for the good word!
A big big thanks to you for explaining it in such a simple way. Didn't think it'd be this simple. Thank You!
Wel done! Your videos are the clearest explanations of the big picture of every algorithm. They are kept simple but complete and without understatements.
So far, this is the best explanation of the algorithm I've seen!
Nice Explanation of convex hull & its algorithms, till now I seen.
Thank you🙏
Incredible how you can explain these fairly complex subjects with such simplicity. I am glad that I found your channel! Very good content.
Thanks for such a wonderful compliment!
By far the best explanation of these two algorithms.
This is the best explaination of Graham Scan algorithm on youtube. Thanks a lot!
Thanks for the compliment!
What an incredibly good explanation, you really thought about which segments of the explanation are harder to understand and explained them really well, thank you so much for the video!
Thank you for such a wonderful compliment! I tried implementing the algorithms and then explained the sections that I myself found harder to deal with. Glad to hear that you found it helpful =)
I found this channel a few months ago and was stunned. Everything is well-explained, much better than in my classes. I've learned a lot. Thank you so much!!!
Thanks for the good word!
one of the best channel, explanation is simple and precise.
Thanks! 😃
THANKYOU for explaining something so complex in such simple words.
Such a great video. Purely recommended.
Appreciated!!
👏
i watched my professors recording of about an hour just for graham scan and still didn't understand a single thing and this good sir here taught me both algorithms in 7 minutes , respect
Same bro. i have exam tomorrow and i watched my class lecture but i couldn't understand.
Glad to know that the video was helpful!
For all of you guys, classroom teachers are idiots.
Thank you, I love teachers like you. Amazing
Thank you for the good words!
I can guarantee this was the best ever explanation of this Algorithms.
When will you make more videos ?
If possible, make such videos on all Algorithms from CLRS book, sequentially. 😇
Such a great video and very well explained. Thanks a lot.
Cool video. There are applications for applying convex hull algorithms to self-driving cars - trying to learn about it! Thanks for the helpful demonstration.
Glad it was helpful! Both Graham Scan and Jarvis March could be used to calculate the Convex Hull just for image classification purposes. Especially since the number of points involved isn't huge. Self-driving cars want to quickly classify an object and roll with it.
this is so much better than my professor, I believe all professor should use animation for visualization of algorithms just like you did!
Very intiuitive and well explained ! Thank you very much professor !
Super simple explanation, thank you!
You are very welcome!
Great explanation, thank you!
Thank you for great descriptions!
Great video! Thanks for the explanation.
wonderful explanation of 2 algos in mins.
Thank you sir ... One of the explained vedio of this topic i have seen so far
Great explanation! Thank you very much!
You are very welcome! And thanks for the compliment!
Amazing explanation !
Very well explained in very efficient matter! Thanks a lot!
You are very welcome and thanks for the compliment!
Please make video on Chan's algorithm. Your videos & explanations are very good & concise.
amazing video. great explanation. keep going!
Great Video! It makes my time save from boring 1 hour lecture of my university professor.
This was soooo awesome!!!! You explained it soo well!
Thanks for the compliment! Glad to hear that it made sense
Thanks a lot. Needed to implement Graham Scan algorithm for Computer Science home work
Most clear explanation ! Thanks a lot
Glad you liked it
Here is really need to have people who do their job with their best effort like you.
Thank you and cheers!
This is the best explanation i could find on the internet 👏
Cheers!
thank you. clearly explained
Intresting. Looks like Convex Hulls aren't as complicated to find as I thought. Well explained! I'll give implementing the Graham Scan algorithm a shot.
Yeah, both Graham and Jarvis algorithms are not that complicated. But to make sure that various collinear points are handled correctly, I had to create a whole battery of test cases (same directory as the main source code: bitbucket.org/StableSort/play/src/master/src/com/stablesort/convexhull/ConvexHullTest.java). I hope this helps!
@@stablesort Thanks for the reply! I'll try to make sure that the collinear points are handled correctly. As for test cases, I mostly solve programming problems on Kattis. See open.kattis.com/problems/convexhull
Speaking of which, lets say that you already know which points are one the convex hull and not. How would you go about finding the order the points appear on the hull? Wouldn't you just have to make the convex hull again, including all collinear points while excluding points inside the hull, and record them along the way? See open.kattis.com/problems/convexhull2 if you're interested.
@@highruler2786 Thanks for link. That website seems to have a rich set of interesting problems.
Rerunning the algorithm on just the vertex points will certainly work. But I wonder if there is a more efficient way to ordering the points, given that we are guaranteed that they are valid vertices? I guess we can just use the sort() method from Graham Scan, with a total running time O(h log h), h=number of vertices. Is there a more efficient solution?
what an amazing video for this topic.
Thanks for the compliment!
Excellent explanation
I would like to know the further explanation of this in your channel ... Very easy and simple understanding Sir
Extremely well explained... Gonna share ..
Woohoo! That's what I like to hear! Thanks!
you have explained explained beautifully. Gained one subscriber👍
Welcome and thanks for the compliment!
You deserve more subscribers ! Kudos
Thanks! Hopefully with time the word will get around =)
great explanation
It just so simple algorithm also very powerful.. I just surprised. Thanks a lot!
awesome explanation ,good job man
Glad you liked it!
Very nice video!! I was very confused in these both cousins but this video made it understand. Please explain the "n log n" algorithm also it would be helpful as this video did. Thank you and keep it up!
Thanks for the compliment! The Graham Scan algorithm works in "n log n", due to the sorting of the points. The "n log h" algorithm, where h is the number of vertices, as developed by T. M. Chan, is on my list of topics to cover if there is enough interest out there. Thank you for casting a vote to have that topic covered. I believe you are the third person to ask for it =)
Sir, amazing work keep it up!!!!!!!!!!!!
One of the best videos I've watched on algorithms, thanks a lot. I have a question regarding to Jarvis March algorithm, in the video you mentioned that h is the number of vertices but I thought it should be the number of corners.
Most underrated video!!! Like to dislike ratio of 477:1...best
Thanks for the compliment!
*HATS OFF, SIR!*
Cheers!
Excellent explanation.. May Allah bless you for making this algorithms so easy to understand... please continue to make more videos
Glad to hear that you liked it!
awesome explanation
Glad it was helpful!
Thanks a lot! This is really great. Please make the episode on n logh algo as well. 🙏
Cool, thanks for the compliment. You are the first person to mention the "n log n" solution! I guess it took 473 views for someone to watch through the end of the video =) I am not sure when I'll have the time to make a video about that algorithm (I am currently in the process of making a couple of videos on a totally different topic) so for the current time being, please see Chan's paper that describes the algorithm
link.springer.com/content/pdf/10.1007/BF02712873.pdf
Or the wiki: en.wikipedia.org/wiki/Chan%27s_algorithm
@@stablesort Thanks for the links :)
Waiting for more from your channel!!!
nicely explained TYSM
Great explanation 👍
Glad you liked it
Thank you very much!
AWESOME VIDEOS THANK YOU!
You are very welcome! Cheers!
well explained
Great Video.
wow what an explanation
Great thanks!
Thank You!
I recommend you to put subtitles to each video so nonnative speakers can understand in a better way. thank you for the video, my teacher used it in his lecture for teaching us this algorithm.
Ha! That's wonderful to hear! By the way, I believe that CZcams automatically creates subtitles in various languages. You just have to click on CC button. Cheers!
@@stablesort thank you for your answer, i like your channel and what you are doing on youtube, but sometimes automatic subtitles are struggling with wrong word conversions.
@@bezelyesevenordek Right, right, I just hope that the auto-translation improves with time. Thanks for your feedback, I do appreciate it
Great video. Can you also please explain the method by Timothy Chan?
Amazing..never expected in this short time.. Is there any playlist for algorithm only?
Love you man❤❤💯💯
Gaayyy
Thanks a lot
excellent sir
Thanks!
it's also very important in thermodynamics for Gibbs energy
Very good
Thanks
wow You are awesome!
Thanks for the compliment! More episodes are in the making. Stay tuned!
Wonderful
Glad to hear it!
inspiring！
Great Explanation ever, Could you please come up and Explain Timothy Chan's Algo
Thanks for the compliment and thank you for casting a vote regarding Chan's algorithm. I am keeping track of all of the requests. Cheers!
Great explanation!
Found a bug though :P
At 4:38 when we handle collinear points in a vertical line, we should treat the order of these points differently.
For points like this shape ▛ , [[0, 0], [0, 1], [0, 2], [1, 2]]
[0, 0] is the P0, in the above shape, the vertical line contains [0, 0], [0, 1], [0, 2] , here [0, 1] > [0, 2], which is the same with the video.
But there's another case: ▜ , [[0, 0], [0, 1], [0, 2], [-1, 2]]
[0, 0] is also the P0, but in this case we scan the vertical line first, and here we need to put [0, 1] before [0, 2] which means [0, 1] < [0, 2].
Thanks for the discussion. I think the exact implementation matters quite a lot for the corner cases. Have you tried out the source code linked in the description? I could be wrong but I think I tried that type of a corner case at some point.
@@stablesort Yep, the source code impl is consistent with your video. it's really tricky to deal with the collinear issue here, so chose Monotone Chain, lol.
anyway, thank you for the clear explanation.
@@Novello42 Thanks! Glad to hear that it was helpful.
Thanks
I have a question in 6:00 (about Jarvis march running time). Why would the case of all points being in the perimeter be slower than a triangle surrounding all the other points? Doesn't the algorithm check all the points in every iteration, no matter what?
Can you suggest some problems/algorithms on which further research can be done to optimise it. Looking forward to pursue some research in Computational Geometry
Thanks for leaving a comment. The only one that I am aware of is Chan's algorithm: link.springer.com/content/pdf/10.1007/BF02712873.pdf
is the cross product faster than the trig on x86 chips? what about on cuda cores? has anyone benchmarked this with optimizations?
Please do make a video on Quick hull
Thanks for casting your vote, I do appreciate it. To be frank, out of almost 9,000 views, there have only been two request for it... While I do want to make a video covering the Quick Hull at some point, I'll probably first do a few other topics before coming back to it. But again, thank you, Madhur Malik for your input.
tks u a lot
Thanks this is useful. I am implementing several convex hull algorithms in Java right now and I for one would really appreciate a video on the O(n log h) algorithm. If I understand it, I might be able to program it too.
I'm curious, in your code you have two implementations of the march. One is supposed to be by angle and I think I understand that one, but I don't quite understand the other. Do you see any performance difference between the two?
There were definitely performance differences. I was actually using one implementation to test the other by generating large numbers of random points and comparing the two. Good luck!
@@stablesort Oh okay. Do you remember which algorithms was faster on average?
How can we sort the points with cross product when the cross product depends on both the length of the vectors and the angle between them? Do we divide the resulting cross product with the lengths of the vectors?
Thanks for raising the question. It's actually simpler than that. The cross product calculates the signed area formed by the two vectors. The area is positive or negative depending on which side the vectors are in reference to each other. And that's all that we need for sorting: that's the comparator function that you'd supply to the sorting algorithm. By the way, check out the source code linked in the description. I hope this helps!
Respect +100
Thanks!
By sorting the points, did you mean with respect to x coordinate or why coordinate ? , considering only 2D set of points.
In my examples I sorted by Y coordinate, so as to start at the bottom most point. But obviously this is just a convention - you can do it via the X coordinate just as well. Thanks for posting the question!
Will you be doing a video of Convex Hull in three dimensions (E^3) as mentioned in Chan's paper?
Thanks for the suggestion, that's a good idea! Truthfully though, if I were to revisit this topic, I'd just explain Chan's method of selecting two polygons, then connecting them up into a single polygon and how that ends up being faster in some circumstances =P
@@stablesort Are you working on something new as of now??
@@puneetkumarsingh1484 Yeah, I have a couple of topics that I am exploring little by little. The youtube channel is only a hobby for me, so I get to it if/when I have some free time. Speaking of which, I better get to it!
No
Please explain Timothy algorithm
4:26 The slope along 3-4-5-6 is vertical, but should we still sort them downward?
Well, you could implement it differently than as suggested. But it is a little tricky, so make sure to test your code really really extensively. What I found was that it's easiest to sort the vertical points going downward. Here is my source code:
bitbucket.org/StableSort/play/src/master/src/com/stablesort/convexhull/ConvexHullGrahamScan.java
@@stablesort Thank you so much for the prompt response! Your code does explain that clearly. Do you have a plan to make a video interpreting Timothy Chan's work in the near future? I really look forward to that if you do!
@@yt-lu To be honest, while T. Chan's algorithm is IMHO quite beautiful, it's not on the top of the list, but only because out of over 10K views that this video has received, there were only 3 requests for Chan's algorithm... So for the near future, I plan to spend the little of free time that I have on topics that may prove to be of more interest to greater number of viewers. By the way, if you have other topic suggestions, please do let me know! Cheers!
pls explain the new algorithm :)
Thanks for placing a vote! I believe at this point 4 people asked for Chan's algorithm (out of nearly 18K views....)
Why didn't we removed 5? In stack
which wone is better?
The answer to your question is at 6:01
video was so informative but you had to show how code all that concept one by one. then it will be easy for us
Thanks for the feedback. I try to keep the videos as short as possible, which inevitable results in leaving out some stuff. The good news is that there is a full implementation with comments linked in the description.
Graham Scan:
bitbucket.org/StableSort/play/src/master/src/com/stablesort/convexhull/ConvexHullGrahamScan.java
Jarvis March:
bitbucket.org/StableSort/play/src/master/src/com/stablesort/convexhull/ConvexHullJarvisMarch.java
I hope this helps!
The video was =) ......in your style
I hope you found it helpful =)
Lets say if i have to check a point whether it lies strictly inside any polygon (not on the boundaries of polygon ,i.e not in edges or vertices of polygon )
There's a link to the code in gfg ...bit it needs to be updated for the boundaries of polygon have to be consider outside of polygon....how to update and which part to be update
www.geeksforgeeks.org/how-to-check-if-a-given-point-lies-inside-a-polygon/
how to find the smallest counterclock angle amomg n points ??
Well, if you go by how Jarvis March does it, you just examine all of the available points. This could be done using the cross product, as explained in the video. There is a link in the description to a working source code, implemented in Java (here it is again):
bitbucket.org/StableSort/play/src/master/src/com/stablesort/convexhull/ConvexHullJarvisMarch.java
Essentially, you just keep track of the one point with the smallest angle found so far.
Alternatively, you could sort the points, as is done by Graham Scan algorithm:
bitbucket.org/StableSort/play/src/master/src/com/stablesort/convexhull/ConvexHullGrahamScan.java
Thanks
You are welcome!