The best possible explanation of both algorithms; The clear and exact visual representation of the processes, made it easier to understand. The explanation was quite precise and to the point.
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
Wel done! Your videos are the clearest explanations of the big picture of every algorithm. They are kept simple but complete and without understatements.
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!!!
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?
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.
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 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. 😇
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 RUclips 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.
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.
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 =)
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
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?
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.
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!
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
@@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!
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!
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 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!
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.
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!
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!
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!
how come the name of these algorithms are so cool
This is by far the best explanation on Jarvis and Graham scan algorithm yet precise
Thanks for the good word!
The best possible explanation of both algorithms; The clear and exact visual representation of the processes, made it easier to understand. The explanation was quite precise and to the point.
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.
Nice Explanation of convex hull & its algorithms, till now I seen.
Thank you🙏
This is the best explaination of Graham Scan algorithm on youtube. Thanks a lot!
Thanks for the compliment!
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.
one of the best channel, explanation is simple and precise.
Thanks! 😃
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!
Great Video! It makes my time save from boring 1 hour lecture of my university professor.
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?
Here is really need to have people who do their job with their best effort like you.
Thank you and cheers!
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.
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 =)
THANKYOU for explaining something so complex in such simple words.
this is so much better than my professor, I believe all professor should use animation for visualization of algorithms just like you did!
This is the best explanation i could find on the internet 👏
Cheers!
By far the best explanation of these two algorithms.
So far, this is the best explanation of the algorithm I've seen!
Thank you, I love teachers like you. Amazing
Thank you for the good words!
wonderful explanation of 2 algos in mins.
Thanks a lot. Needed to implement Graham Scan algorithm for Computer Science home work
Clear like crystal.
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. 😇
Super simple explanation, thank you!
You are very welcome!
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!
thank you. clearly explained
Great explanation! Thank you very much!
You are very welcome! And thanks for the compliment!
Amazing explanation !
Most clear explanation ! Thanks a lot
Glad you liked it
Please make video on Chan's algorithm. Your videos & explanations are very good & concise.
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 RUclips 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.
@@beypazariofficial Right, right, I just hope that the auto-translation improves with time. Thanks for your feedback, I do appreciate it
I would like to know the further explanation of this in your channel ... Very easy and simple understanding Sir
Very well explained in very efficient matter! Thanks a lot!
You are very welcome and thanks for the compliment!
Extremely well explained... Gonna share ..
Woohoo! That's what I like to hear! Thanks!
Thank you sir ... One of the explained vedio of this topic i have seen so far
Such a great video. Purely recommended.
Appreciated!!
👏
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.
Great video! Thanks for the explanation.
what an amazing video for this topic.
Thanks for the compliment!
Excellent explanation
Such a great video and very well explained. Thanks a lot.
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!
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 =)
very beautifully explained.
Most underrated video!!! Like to dislike ratio of 477:1...best
Thanks for the compliment!
This was soooo awesome!!!! You explained it soo well!
Thanks for the compliment! Glad to hear that it made sense
Thank you for great descriptions!
you have explained explained beautifully. Gained one subscriber👍
Welcome and thanks for the compliment!
Very intiuitive and well explained ! Thank you very much professor !
awesome explanation
Glad it was helpful!
great explanation
*HATS OFF, SIR!*
Cheers!
amazing video. great explanation. keep going!
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!!!
You deserve more subscribers ! Kudos
Thanks! Hopefully with time the word will get around =)
awesome explanation ,good job man
Glad you liked it!
It just so simple algorithm also very powerful.. I just surprised. Thanks a lot!
Great explanation 👍
Glad you liked it
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?
No, it will do less iterations of searching for the next point. It stops when it gets back to the first point
Sir, amazing work keep it up!!!!!!!!!!!!
well explained
AWESOME VIDEOS THANK YOU!
You are very welcome! Cheers!
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.
excellent sir
Thanks!
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!
Que gran explicación muy fácil de entender
Great video. Can you also please explain the method by Timothy Chan?
it's also very important in thermodynamics for Gibbs energy
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!
wow what an explanation
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
nicely explained TYSM
Thank you very much!
Great Video.
Love you man❤❤💯💯
Gaayyy
wow You are awesome!
Thanks for the compliment! More episodes are in the making. Stay tuned!
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!
inspiring！
Very good
Thanks
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
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?
Amazing..never expected in this short time.. Is there any playlist for algorithm only?
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.
Thank You!
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!
Great thanks!
Thanks a lot
Respect +100
Thanks!
Wonderful
Glad to hear it!
is the cross product faster than the trig on x86 chips? what about on cuda cores? has anyone benchmarked this with optimizations?
Please explain Timothy algorithm
Thanks
You are welcome!
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
tks u a lot
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 =)