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
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.
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!!!
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. 😇
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 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 TH-cam 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.
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
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 =)
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.
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?
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!
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.
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!
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!
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
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!
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!
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/
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
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!
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.
This is the best explaination of Graham Scan algorithm on youtube. Thanks a lot!
Thanks for the compliment!
one of the best channel, explanation is simple and precise.
Thanks! 😃
Nice Explanation of convex hull & its algorithms, till now I seen.
Thank you🙏
A big big thanks to you for explaining it in such a simple way. Didn't think it'd be this simple. Thank You!
This is the best explanation i could find on the internet 👏
Cheers!
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.
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 explanation! Thank you very much!
You are very welcome! And thanks for the compliment!
this is so much better than my professor, I believe all professor should use animation for visualization of algorithms just like you did!
Thank you, I love teachers like you. Amazing
Thank you for the good words!
Great Video! It makes my time save from boring 1 hour lecture of my university professor.
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 =)
Super simple explanation, thank you!
You are very welcome!
I would like to know the further explanation of this in your channel ... Very easy and simple understanding Sir
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. 😇
*HATS OFF, SIR!*
Cheers!
Wel done! Your videos are the clearest explanations of the big picture of every algorithm. They are kept simple but complete and without understatements.
Most clear explanation ! Thanks a lot
Glad you liked it
Thanks a lot. Needed to implement Graham Scan algorithm for Computer Science home work
Most underrated video!!! Like to dislike ratio of 477:1...best
Thanks for the compliment!
Extremely well explained... Gonna share ..
Woohoo! That's what I like to hear! Thanks!
wonderful explanation of 2 algos in mins.
Amazing explanation !
THANKYOU for explaining something so complex in such simple words.
By far the best explanation of these two algorithms.
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!
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!
So far, this is the best explanation of the algorithm I've seen!
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 TH-cam 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
Please make video on Chan's algorithm. Your videos & explanations are very good & concise.
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!!!
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.
Very well explained in very efficient matter! Thanks a lot!
You are very welcome and thanks for the compliment!
what an amazing video for this topic.
Thanks for the compliment!
Such a great video. Purely recommended.
Appreciated!!
👏
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 =)
Thank you sir ... One of the explained vedio of this topic i have seen so far
great explanation
thank you. clearly explained
you have explained explained beautifully. Gained one subscriber👍
Welcome and thanks for the compliment!
Such a great video and very well explained. Thanks a lot.
awesome explanation
Glad it was helpful!
This was soooo awesome!!!! You explained it soo well!
Thanks for the compliment! Glad to hear that it made sense
You deserve more subscribers ! Kudos
Thanks! Hopefully with time the word will get around =)
Excellent explanation
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 video! Thanks for the explanation.
amazing video. great explanation. keep going!
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.
Very intiuitive and well explained ! Thank you very much professor !
Thank you for great descriptions!
It just so simple algorithm also very powerful.. I just surprised. Thanks a lot!
Great explanation 👍
Glad you liked it
awesome explanation ,good job man
Glad you liked it!
it's also very important in thermodynamics for Gibbs energy
well explained
AWESOME VIDEOS THANK YOU!
You are very welcome! Cheers!
Sir, amazing work keep it up!!!!!!!!!!!!
wow what an explanation
Great video. Can you also please explain the method by Timothy Chan?
nicely explained TYSM
Great Video.
Amazing..never expected in this short time.. Is there any playlist for algorithm only?
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?
Thank you very much!
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
Very good
Thanks
excellent sir
Thanks!
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.
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?
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!
wow You are awesome!
Thanks for the compliment! More episodes are in the making. Stay tuned!
Wonderful
Glad to hear it!
Thank You!
Love you man❤❤💯💯
Gaayyy
Great thanks!
is the cross product faster than the trig on x86 chips? what about on cuda cores? has anyone benchmarked this with optimizations?
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
Why didn't we removed 5? In stack
Thanks a lot
Please explain Timothy algorithm
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!
inspiring！
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!
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....)
Respect +100
Thanks!
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!
tks u a lot
The video was =) ......in your style
I hope you found it helpful =)
which wone is better?
The answer to your question is at 6:01
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
Great explanation, thank you!
Thanks
You are welcome!