Gift Wrapping Algorithm (Convex Hull)
Вставка
- Опубліковано 6 чер 2024
- Seeing as how Christmas is around the corner, I thought you guys might enjoy a quick video on how to wrap a rather intangible gift: a random distribution of points.
This was actually an incredibly fun code to write / I love Chan's algorithm. It's one of the most beautifully simple yet clever ideas I have seen in a while. Of course, I say that about every algorithm, so who knows when I'm telling the truth!
Anyway, thanks again for popping in and watching / I'll see you next time!
The music came from Josh Woodward (sped up 1.5 times):
www.joshwoodward.com/
Please feel free to follow me on Twitter:
/ leiosos
Twitch (where I do all the simulations):
/ leioslabs
My second youtube channel (where I put the streams):
ua-cam.com/channels/Ff6.html...
or Github:
github.com/leios
The code I used is available here:
github.com/leios/simuleios/tr...
(sorry it's so messy)
Also, discord:
/ discord - Наука та технологія
![ПОЛНАЯ ИСТОРИЯ ЭКЗОРЦИЗМА [Топ Сикрет]](http://i.ytimg.com/vi/qBySr6Bt0B8/mqdefault.jpg)
A random distribution of points! Just what I've always wanted!
Hey guys, I published this video and then immediately went to sleep (sorry!), but it was seriously a bunch of fun to program, and I would love to make videos like this some more!
Anyway, let me know what you think / I hope you guys are having a wonderful day!
This video was a gift to my mind! It takes skill to explain three algorithms so well and succinctly as you did, and that's one great gift to have ;)
Haha, you are awesome! =)
Draw Curiosity nice to see a fellow biologist on this channel! :-)
When I figured out this video , I was legitimately stunned how wonderfully you explained.
Thank you Sir
My biggest gift for today is that I found this channel
Phenomenal video, easy, engaging and to the point !
Trying to learn convex sets and this really helped with the intuition thanks :)
This dude had an intro a story and still managed to explain 3 algorithms in under 3 minutes. Crazy
Wowww. You just solved my never ending confusion in 2 minutes. Thanks a lot!! \m/
Visualizations help sometimes! =_
Thank you for the explanation of Graham. I'd understood Jarvis and the Chan approach, but not that step in the middle.
Cool, supper cool!!! we can use these algorithm to improve the efficiency of image object recognition.
Woah! That's cool! I hope it works! =)
Thanks for explaining Chan's algorithm
LOVE THIS! THANK YOU!
This was one of my favorite episodes to make! I'm glad you liked it!
@Michael Darrow Haha, he probably was!
Quick question. For Graham Scan, what does "removing any vertex that points outward" refer to? I think it should be "removing any vertex that points inward". (My understanding inward = points toward the center of the hull; outward= points out from the center of the hull). Thanks
Interesting video. When looking at each distribution of random points, people are able to 'wrap' them, so the visual system must be doing some kind of algorithm too. I wonder how the human brain solves this problem, and whether that can be used to make more efficient algorithms.
Actually, I have been wondering something similar. In addition, is there a good machine learning approach to this? It's incredibly interesting to think about!
Unfortunately the human brain works fundamentally differently from how a computer does. A CPU is a massively serial processing machine, capable of billions of serial calculations per second, with limited parallel processing. Your brain, on the other hand, has limited serial processing, capable of perhaps 100 calculations per second on a single 'thread,' but makes up for that limitation with a massively parallel processing strategy. With an estimated 100 billion neurons, each firing on average once per second, you get an initial napkin-math estimate of around 100 billion calculations per second across the brain.
Your brain has another trick up its sleeve, though. Each neuron can project to thousands of other neurons, and the signal of one neuron can increase or attenuate the signal from other neurons at a single synapse. Therefore each single synapse can also be considered to be a calculation. And there are somewhere on the order of 10^15 (one quadrillion) synapses in the human brain.
Furthermore, a CPU is a general-purpose calculator, with algorithms being contained in instructions fed from memory. The brain, on the other hand, has the majority of (known) algorithms stored simply in its circuit architecture. The retina, for instance, has a specifically designed architecture that does much of the initial 'heavy lifting' of visual processing, without the need for any kind of instructions or memory. Therefore, to have a CPU approach a problem the same way the human brain does, it would either have to inefficiently emulate parallel processing (as is the case in neural network algorithms) or have a completely new architecture that emphasizes massive parallel processing.
You could use GPUs for the parallel calculation aspect, they're better than CPUs
It feels a bit like those linear regression problems, i think neural networks could work fine on this, but i'm not an expert
I love these dots!
Woo! I'm glad!
Im somewhat embarrassed about how much I've thought about this problem specifically :)
Jarvis algorithm was a little hard to implement, the notion of max angle leads to orientation and lots of nuances that are a little annoying around angles and computing, but I am glad i finally was able to implement it, just so if anyone want to do it too, try to stick to the law of cosines and use clockwise orientation determination to know if you want the inside or outside angle, arctan was a mess
I have no idea what this is used for but it seems pretty legit mate lol
Actually, the hulls are used a lot in a number of different places, although it's not obvious where and why. One example is in robotics. The robot has a complicated obstacle course to run through and needs an optimal path around everything. That path will end up being a convex hull around the random points.
Any idea about the complexity of those three methods? I can see from the last example that Graham found the convex hull quicker than the others.
Chan's: O(nlogh)
Graham: O(nlogn)
Jarvis: O(nh)
n -- number of points
h -- size of hull
Chan's should be faster than both. The animations are not indicative of performance.
Very nice
Nice gift, even more special since it's random, so no one got the same gift as the other (or nearly no one) XD
Haha, I'm glad you liked it!
Excellent
Best explanation!!!!!
What about expanding polytope algorithm?
Sweet treat for the brain.
Yeah, I really liked these algorithms! They were super fun to implement!
I love it
I had to do it for on a project, and I found another way to make a convex hull:- join the dots of the min, the max of x and y.
- then for each line of the polygon calculate the max distance to it and add it to the polygon.
After some iteration, you got the convex hull.
After doing some research, I'm not the first to use this method, it's called quickhull and have O(nlogn) efficiency.
Yeah! Quickhull is amazing! We didn't get to it here, but it's definitely on the list for the AAA.
The other cool thing is that this method can be generalized in a n-dimension space
But I thought it was tricky for >3D, right? I remember running into it a few days ago for knot theory algorithms...
Leiosos, I don't know I didn't test it already
If you can find an outermost point in the set, can't you just then rotate it all in one direction and keep selecting the outermost point until you find the first one again, and then unite them all?
You'd end up with an infinite turn problem. You'd have to figure out how much to turn. 1 degree? 5 degree? 0.0001 degree? Too little it takes a very long time and too large and you miss 1/2 the points.
Not to mention that every time you rotate by, say 0.5 degree, you have to calculate the sin and cos then apply that calculation to every point, every iteration.
Yeah, this is one of the problems, I think. Basically, these algorithms guarantee you will find the convex hull by using a discrete method. Unfortunately, they are not as intuitive as our continuous minds want them to be (which is super cool, when you think about it).
KingFredrickVI Not really. Simply rotate clockwise by say 1 degree. If it doesn't pass another point, rotate by another degree, otherwise if just one point has been crossed, you have located the next point in the wrapping. If you have crossed more than one, go anticlockwise by half a degree etc.
Seeing the algorithm considering points in the middle just makes my head hurt and my brain scream that this is so inefficient
And how do you determine if a point has been "crossed"?
Also, if a better algorithm is really that simple, do you think the mathematicians mentioned in the video, with multiple awards and honors, couldn't come up with it?
Thank you
I love it. :3
Thanks! I'll see what other algorithmic gifts I can find lying around...
Just one question, you've said that chan's algorithm is the most efficient one, but in the video The graham's algorithm ends early.
Is this because of the diferent distributions or was it intencional?
Also, would be nice if you mention the asymptotic analysis, just for a numerical reference of how better one is then another.
By "was it intencional" I mean, did you chose some special case in with it would do better for some reason?
Yeah, we have 2/3 of these in the algorithm archive: www.algorithm-archive.org/chapters/computational_geometry/gift_wrapping/jarvis_march/jarvis_march.html
I am working on getting a better description of these.
Basically Chan's is faster because it uses the graham scan where it is useful (large number of points), and it uses the jarvis march where it is useful (small number)
Can you explain why the hybrid algorithm is faster than either of the two previous algorithms by themselves?
Jarvis March is best when there is a small number of particles, Graham Scan is best when there is a large number, so we use Graham scan when there's a large number of particles so that we can read a small number of particles into the Jarvis March. I hope that makes sense.
Thanks for replying. But I wonder why would you want to read a small number of particles into the Jarvis March when you can just solve the problem outright using purely the Graham Scan?
If you have a million cases of small number of particles, you're gonna want to use the fastest one on small number of particles.
I’m gonna try ordering a Graham Scan at Denny’s
How did that go?
Why is Chad's algorithm better? Wouldn't it be easier to use Jarvis algorithm as Chad's algorithm has Jarvis algorithm within it
gustorn but why?
Yeah, I ended up just ignoring the complexity cases. I should make a video explaining them in more depth and then link to that video from now on. I just need a way to make the cases much easier to understand.
These algorithms do a lot of checking the wrong points... What if you just found the right point first time?
Start with the leftmost point, draw a line from it to the top of the space, then rotate it clockwise about the leftmost point by an angle. If there are no points to the left of the line, repeat the rotation. If there are more than one point to the left of the line, divide the angle by 2 and rotate the line about the leftmost point anticlockwise, and repeat the check. If there is exactly one point to the left of the line, that's the right point. Continue on from there, drawing the line with the slope equal to the line drawn from the first point to the second point.
There'd probably be some shortcut you could take if multiple points were on the same line of the convex hull.
Surely I'm not the first to think of this?
This won't work on higher dimensions than 2D. Convex hulls problems arise in high dimensional data. This is more of a toy example.
So, that implementation seems to work fine in a physical model, but computationally, it is precisely the same as the Jarvis march (unless I misunderstood).
The march is a comprehensive check over every point, right? My method is a search, somewhat akin to a binary search.
Someone made the point of higher dimensions being a problem, but I'm not sure I believe that; represent the rotation of the bisection as a matrix instead, and give the bisection n-1 dimensions, where n is the amount of dimensions in the search space. Instead of searching for one point, you'd search for n-1 points, (so a 3D space would have you building a triangle), one at a time. Once you find one point, you rotate around the shape you've built up to that point until you hit the total of n-1, then pick an edge off which to build the next shape and carry on.
I'unno, it _feels_ like there's something in this.
The problem lies within determining wether a point is on the "left" or "right" side of the line.
Graham's seems like the most efficient.
Chan's is literally graham's when it's most efficient and jarvis's when it's most efficient. That's why it's *slightly* better.
thank you TTwTT
your welcome!
What about quickhull?
Oh yeah. Love that one. We intend to put it in the algorithm archive after quicksort.
when will you send me my dots?
first algorithm was O(n2) runtime. the scan was O(nlogn). I believe the last one is at best O(n sqrt(n)) and averages to O(nlogn) runtime, but there are ways to get an average O(nsqrt(n)) runtime complexity which is provably the best you can achieve for gift wrapping.
Simplest one is divide the region into sqrt(n) sections of sqrt(n) points each. You can do this in n*sqrt(n) time by selecting a random sqrt(n) points via blue noise and using a voronoi diagram to seperate the regions. Then for each of these sqrt(n) regions the problem recurses. Once you get down to regions of 5 points or less, use the scan method to wrap them, then recurse out and wrap again until you've wrapped the full thing.
The cost here is n*sqrt(n) for the voronoi seperation. Then everything else after doesn't contribute to runtime complexity. the recursive step adds sqrt(n) * sqrt(n) sqrt(sqrt(n)) which is really n^(5/4), which is less than the n^(3/2) and does not contribute to the runtime complexity. Using the general rule that on average for a collection of n points, the hull surrounding it will contain on average sqrt(n) points (intuition being perimeter vs area), the scan which was before nlogn will now take sqrt(n)logn, which is also less than nlogn and thus doesn't contribute to runtime complexity.
There are certainly more effecient ways to impliment giftwrapping with O(nsqrtn) runtime, but this is the simplest one to explain I think
U desirve a subscribe just for your voice . Plus for explenatin you are giving to us
I am glad you liked the video!
Sir ap urdu lecture b provide kr dayn gift wraping
Do this in 3d
too short
Why not just start with the leftmost point and a vertical line, then gradually rotate the line about that point clockwise until it intersects with another point, then continue to rotate about the new point until you intersect a new point and continue until you have gone all the way round . You're welcome.
I think the main problem with this implementation is recognizing what intersects with what. I can imagine that would be costly computationally.