Man you are amazing and the way you teach coding makes you wonder is it actually this simple and fun...I learnt a lot from you especially learning p5js was a big tool under my belt ...really thanks...keep doing the good work
This is mine: editor.p5js.org/IvanPedrero/full/rID2WvsCB You can create your points by clicking on the screen and then see the algorithm work... Thanks for the video! Really good explanation!
Just a small correction; You said that the cross product is an operation between two vectors that are on the same plane, which is correct, but redundant. Given any two vectors, there exists a plan that contains them. In fact, they define that plane uniquely, as long as they are not linearly dependant (multiples of one another). Just saying.
How about a tutorial on 3D scanning with a pc webcam in p5... point cloud generation... Delaunay triangulation... STL representation?? You are the best. Keep up the good work!
Man you are amazing and the way you teach coding makes you wonder is it actually this simple and fun...I learnt a lot from you especially learning p5js was a big tool under my belt ...really thanks...keep doing the good work
That single "sort" call would already have a complexity of O(n log n) (assuming quick sort). Just finding the left most point would only require O(n). There's actually a nice divide and conquer method. First find the extremes in both axis (left most, right most, top most, bottom most). This can be done in O(n) in a single loop through all points. Now we can connect the 4 points to form a quadrilateral. A nice features of those 4 lines is, that all points that are outside that line are only relevant for this line segment. So we can actually filter all points into 5 groups. One for each line segment (all points on the outside of that segment) as well as the points enclosed in that quadrilateral. Those enclosed points don't need to be checked ever again. We splitted the outer points into 4 seperate groups. Next we just iterate through the points for one segment and find the outer most point simply by calculating the dot product between the segments normal vector and the connecting vector from one of the end points to each point in that group. We know that the outer most point is also part of the convex hull. So we can split the original segment into two segments with the new point being the connecting point. Now just repeat for those sub segments. Once there are no points outside all segments, that's the convex hull. The number of points will cut down rapidly this way. Unlike the gift wrapping solution in this video, this approach extends quite nicely into 3d. The min / max points in 3d form an octahedron. So we have 8 triangle faces which form seperation planes. Since it's possible that in the worst case you get 2 initial hull points from the min / max (it's possible that the top and left most point is the same point. Same for the bottom right point), it's usually simpler to assume just a single edge for the start. Same for the 3d case. However we can calculate the point that is furthest from the initial line to form the first cutting plane / triangle in 3d.
I'm glad you mentioned inefficiency. But brute force is fine for first pass demo. I once wrote a dialup BBS router the task of which was to pass messages through several steps of 'free/local' calls, to connect systems that were normally 'long distance.' Imagine the array of dots, a message can enter the system at any edge point, and traverse the array of dots to any other point. The intent was to do that with the fewest number of calls. There was an array of fixed data, that needed human maintenance, that said which phone numbers were local to which others. Tons of fun to write.
I have an idea for a computational geometry challenge: a 2D concave hull algorithm - surely this is more useful day-to-day anyway? You want to pass through all the boundary points and generate a shape with the minimum area.
I began watching the vid and when I realised what it's about, I did it myself in python and went along with watching you solve it. It's awesome how differently we achieved the same result. Big fan of your channel
Ironic, I was assigned to write jarvis' march in my algorithm's class, and i am looking up information algorithm and you just released a video! Thank you so much for doing it, I had a great understanding after i watched the video, and I had the confidence to write it up for my class afterwards. Cheers!
I love these animations. Would also like to see the divide and conquer convex hull animation as it would probably be cool in teaching people divide and conquer.
Haha this is pretty halarious! I am doing research and we need to extract contours of important areas in an image, and I have been looking for something like this! Literally just started looking yesterday! How serendipitous!
I tried to improved slightly the visual and the ease of use of the your code. You can find this there: editor.p5js.org/AfroDisco/sketches/-st9ZFxBS I also tried to use divide and conquer to reduce the complexity: editor.p5js.org/AfroDisco/sketches/nSWqjnOJU The approach is to compute the convex hull of subset of points (split along the X axis) and then computing the convex hull of all points inside these convex hulls. I also added some outputs to show the computational differences between both.
The shape created by adding "CLOSE" to endShape hints at a possible optimisation; if you can figure out what points are within that shape, you don't need to check them.
Cross product rule for (a x b): 1. Put your right hand perpendicular to the plane of the board. 2. Let vector a "go through" the palm of your hand and your thumb stick out perpendicular to the plane of the board 3. Visually inspect to see if the angle between vector a and vector b is less than 180 degrees 3a. If it is, curl your fingers over to vector b, proceed to step 4 3b. If is is not, rotate your forearm 180 degrees about its long axis, then return to step 3a 4. Your thumb is the direction of the resultant vector
I have a suggestion; sort the points around a central point by lowest to highest angle, build a starburst polygon, then check each vertex for the angle between the adjacent points, removing vertices with angles greater than pi/180 degrees. Loop through the vertices until there are no concavities
Any chance you can do a video on a Concave Hull algorithm? I'm a surveyor, and the ability to define the concave hull of a spatial dataset would be an awesome tool for our processing.
11:38: "a cross product is the product of vectors which are on the same plane" Two non-colinear vectors always define a plane, two colinear vectors always define a line, which is always contained in a plane; so two vectors are always on the same plane ;-) Sorry, that's only my math disorder syndrom at play...
I don't know how to program, but here's my idea for this sort of algorithm: Create the first line as usual and then from the 2nd point extend the line infinitely and rotate it clockwise (or anticlockwise, depends on the orientation of first line) until you hit another point. Connect 2nd and said point and repeat
Sir, First of all, I am a big big big fan of your challenge videos. As asked by you, I would love to see you program "Vornoi Diagram and Decaulay Triangulation Problem".
This is sweet ! I was just trying to implement a version of Graham Scan in p5 and was having some difficulties with angle calculation the other day and today you made this !
Graham scan is nice. First you sort it, then just go through with it. This algo isn't Graham scan, though. Maybe next video? Also, you can eliminate most points just by scanning a rectangle and deleting the points inside. Bob Sedgwick Algorithm book describes the process. That's how I learned it, BTW.
FWIW, the rule for remembering the cross products a x b is that you put the side of your right hand on a and make the palm look in the direction of b. Where your thumb points is the result.
one of the way you can improve that is removing points that are already contained within the convex hull from the set to be tested. And my first instinct would have been to go with dot products and find the max of dot(normalized(new-current), normalized(current-previous)) with exception for the first point where current-previous is replaced with (0,1). This also lets you test for enclosure within the current hull by using dot(normalized(new-current), normalized(first-current))
Well, the coolest thing about the DeLaunay triangulation is not the circle thing, it's that it is optimal in avoiding thin long triangles which look ugly. In this sense, it is mathematically the most beautiful triangulation of a given set of points.
This is a nice explanation of the Gift-Wrapping-Algorithm, but it has one big flaw. By sorting the points first a O(n log(n)) time complexity is added, which makes this algorithm very slow. While it seems this algorithm is slower than the graham scan, in many cases it is acutally a lot faster, because sorting takes a lot of time. The sort should be replaced by a simple for loop to identify the leftmost point. In my tests the Gift-Wrapping-Algorithm was always faster than the Graham Scan at least to about 2500 points, then depending on the number of convex hull points found. One of the reasons may be, that sorting actually requires memory access, while just reading the points can take advantage of processor cache.
It seems as though a way to make this algorithm faster would be to somehow add all points inside the hull as being inside the hull and only checkpoints that are outside the hull. Once you connected the point you are checking to the start point it became clear that it is checking all the points that should be know to be inside the hull. The hard part would be how do you determine what is inside the hull and what is outside? But maybe one of the other algorithms do this.
Quite late, but somewhat related to this. Coding Challenge: Divide an arbitrary 2D polygon into triangles. + Polygon can be overlapping. + Inside is defined as uneven number of "linehops" from outside.
Simple optimization, you could exclude points which are already inside the temporary convex hull so you never check it again ! (It's actually using the definition of a convex polygon ;) )
I am finally working on triangulating a point set. I am picking points in my canvas and making triangles using the cross product to find points outside existing triangles (or inside; that'll be fun...)
Generating a random 3D shape, like a sphere, and getting 4 random points on the sphere and getting the area inside these 4 points. On youtube there is a video about this called “the hardest math problem on the hardest test”
People: "What does ADHD feel like?" Me: "I realised halfway through the video that he speaks English with the same accent as Kermit the frog, and now I can't listen to his words anymore."
I have a feeling that this could have been coded much cleaner had you used generator functions. The algorithm when written inside the generator algorithm would be pretty similar to the gift wrapping algorithm pseudo code you would find online, instead of being "scattered around" in setup and draw. any time a draw happens, you ask for the next value from the generator. The generator could return the new state of the points each time. Neat video though :)
I keep getting people recommending generator functions to me! I've actually never used one, something I definitely need to learn. Thank you for the tip!
For more computational geometry you could try animating a Voronoi Diagram. Eg: en.wikipedia.org/wiki/Voronoi_diagram#/media/File:Voronoi_growth_euclidean.gif
Hi, really late observation but I think you are calculating the cross product of the vector from the origin to the points, not the actual ones you are drawing. It's surprising that it actually works.
Idea: a code that tells you the number of pairs in a scatter plot given a maximum separation allowed for two points to be considered 'pairs'. Uses for this would be if - say - you have a plot with stars' positions and you ran this code for increasing angular separations, keeping track of the total number of pairs per angular separation. As you increase the maximum distance allowed, the more pairs you will see. If you were then to make a log plot (log angular separation vs log number of pairs) you would - in a completely random distribution - have a line of constant slope. However, if in your data set you had systems of gravitationally bound binary stars, you would instead see a bump at lower angular separations above the constant slope line caused by the random distribution. Astrophysicists use this method all the time to find populations of wide binaries in large datasets. However, with large datasets doing this inefficiently can be a disaster, which is why i think its an interesting coding problem.
Isnt the definition of convex just, hat you can connect evry 2 points with a straight line and the line will be in your shape completely? and concave being just non-convex
Would it be possible to connect all the dots with a non-self-intersecting spiral? Obviously I would not be a true spiral and would likely be quite misshapen but I think you get the idea.
Hi! Can you also please add some real-world use cases of the algorithms you cover in coding challenges? I really like to see you code but it would be great to know where it can be applied.
Actually, the cross product is the other way round. Still doesn't matter. I really do love computational geometry, and I really look forward to seeing more algorithm visualizations in p5.js!
For all interested in a nicely animated version of the probably most efficient of the algorithms, Chan's Algorithm: github.com/AntonioNoack/ChansAlgorithm (written for a seminar at university by me)
So the three well known algorithms seem to be Jarvis march (gift wrapping), Graham's scan and Chan's algorithm which kind of combines the former two. Is there anything else more efficient that I have overlooked?
Find the code and share your version! thecodingtrain.com/CodingChallenges/148-gift-wrapping.html
Thanks for the gift codes!
Man you are amazing and the way you teach coding makes you wonder is it actually this simple and fun...I learnt a lot from you especially learning p5js was a big tool under my belt ...really thanks...keep doing the good work
This is mine: editor.p5js.org/IvanPedrero/full/rID2WvsCB
You can create your points by clicking on the screen and then see the algorithm work... Thanks for the video! Really good explanation!
Just a small correction; You said that the cross product is an operation between two vectors that are on the same plane, which is correct, but redundant. Given any two vectors, there exists a plan that contains them. In fact, they define that plane uniquely, as long as they are not linearly dependant (multiples of one another). Just saying.
With your knowledge of JavaScript, how is it possible that the new site did not keep the old links?! Currently, none of the old links work anymore? :)
The vibe itself pulled me towards your video. And the teaching, as always, next level.
Dude, your videos are too great for youtube.
How about a tutorial on 3D scanning with a pc webcam in p5... point cloud generation... Delaunay triangulation... STL representation?? You are the best. Keep up the good work!
The way you interact , the way u express ur intrest in coding, your logical thinking inspires me
Someone please make a compilation of all of Dan's adorable fumbles including but not limited to "Graham's Scam" 😂
Man you are amazing and the way you teach coding makes you wonder is it actually this simple and fun...I learnt a lot from you especially learning p5js was a big tool under my belt ...really thanks...keep doing the good work
That single "sort" call would already have a complexity of O(n log n) (assuming quick sort). Just finding the left most point would only require O(n).
There's actually a nice divide and conquer method. First find the extremes in both axis (left most, right most, top most, bottom most). This can be done in O(n) in a single loop through all points. Now we can connect the 4 points to form a quadrilateral. A nice features of those 4 lines is, that all points that are outside that line are only relevant for this line segment. So we can actually filter all points into 5 groups. One for each line segment (all points on the outside of that segment) as well as the points enclosed in that quadrilateral. Those enclosed points don't need to be checked ever again. We splitted the outer points into 4 seperate groups. Next we just iterate through the points for one segment and find the outer most point simply by calculating the dot product between the segments normal vector and the connecting vector from one of the end points to each point in that group. We know that the outer most point is also part of the convex hull. So we can split the original segment into two segments with the new point being the connecting point. Now just repeat for those sub segments. Once there are no points outside all segments, that's the convex hull. The number of points will cut down rapidly this way.
Unlike the gift wrapping solution in this video, this approach extends quite nicely into 3d. The min / max points in 3d form an octahedron. So we have 8 triangle faces which form seperation planes.
Since it's possible that in the worst case you get 2 initial hull points from the min / max (it's possible that the top and left most point is the same point. Same for the bottom right point), it's usually simpler to assume just a single edge for the start. Same for the 3d case. However we can calculate the point that is furthest from the initial line to form the first cutting plane / triangle in 3d.
Thanks for this explanation!
I recommended this way back in early 2018 on the topics GitHub, glad to see it done 😊
One of my lecturers mentioned using the convex hull to enclose cancerous tissue inside bone. Thanks for helping me visualise it!
If you create something using the algorithm please share!
This is exactly what I need for my project thank you
This guy gives me motivation to be calm during problems
Explanation is sooo engaging....
looking forward to the computational geometry series...i stumbled across delauney triangulation on gamedev once
Always love seeing a new coding train video in my inbox!! Great video, found it really interesting!
Thank you for always giving a good lecture on a new topic.
I'm glad you mentioned inefficiency. But brute force is fine for first pass demo. I once wrote a dialup BBS router the task of which was to pass messages through several steps of 'free/local' calls, to connect systems that were normally 'long distance.' Imagine the array of dots, a message can enter the system at any edge point, and traverse the array of dots to any other point. The intent was to do that with the fewest number of calls. There was an array of fixed data, that needed human maintenance, that said which phone numbers were local to which others. Tons of fun to write.
I have an idea for a computational geometry challenge: a 2D concave hull algorithm - surely this is more useful day-to-day anyway? You want to pass through all the boundary points and generate a shape with the minimum area.
the enthusiasm tho wow I want to be this excited about coding too
Fantastic topic! Never knew this existed.
I love these coding challenges
I began watching the vid and when I realised what it's about, I did it myself in python and went along with watching you solve it. It's awesome how differently we achieved the same result. Big fan of your channel
Nice work! You can submit a link to the coding train website if you like! github.com/CodingTrain/website/wiki/Community-Contributions-Guide
Ironic, I was assigned to write jarvis' march in my algorithm's class, and i am looking up information algorithm and you just released a video! Thank you so much for doing it, I had a great understanding after i watched the video, and I had the confidence to write it up for my class afterwards. Cheers!
I love these animations. Would also like to see the divide and conquer convex hull animation as it would probably be cool in teaching people divide and conquer.
new coding challenge? let me stop whatever i was doing
Just had a class on geometric algorithms last semester, but needless to say, your presentation is way more exciting and clear.
Haha this is pretty halarious! I am doing research and we need to extract contours of important areas in an image, and I have been looking for something like this! Literally just started looking yesterday! How serendipitous!
awesome, glad to hear!
Bro this video is highly underrated! Thank you!!
I tried to improved slightly the visual and the ease of use of the your code. You can find this there: editor.p5js.org/AfroDisco/sketches/-st9ZFxBS
I also tried to use divide and conquer to reduce the complexity: editor.p5js.org/AfroDisco/sketches/nSWqjnOJU
The approach is to compute the convex hull of subset of points (split along the X axis) and then computing the convex hull of all points inside these convex hulls.
I also added some outputs to show the computational differences between both.
This is so great! Would you mind submitting a link to the coding train website?
github.com/CodingTrain/website/wiki/Community-Contributions-Guide
Best coding teacher ever
The shape created by adding "CLOSE" to endShape hints at a possible optimisation; if you can figure out what points are within that shape, you don't need to check them.
hehe that what I thought too. but how can you figure out what points are in that shape without "checking them" first ? ;)
Cross product rule for (a x b):
1. Put your right hand perpendicular to the plane of the board.
2. Let vector a "go through" the palm of your hand and your thumb stick out perpendicular to the plane of the board
3. Visually inspect to see if the angle between vector a and vector b is less than 180 degrees
3a. If it is, curl your fingers over to vector b, proceed to step 4
3b. If is is not, rotate your forearm 180 degrees about its long axis, then return to step 3a
4. Your thumb is the direction of the resultant vector
I have a suggestion; sort the points around a central point by lowest to highest angle, build a starburst polygon, then check each vertex for the angle between the adjacent points, removing vertices with angles greater than pi/180 degrees. Loop through the vertices until there are no concavities
He is such a character, i love it
Omg you are the best coding teacher in my life!!
Any chance you can do a video on a Concave Hull algorithm? I'm a surveyor, and the ability to define the concave hull of a spatial dataset would be an awesome tool for our processing.
omg... i wish i could be smart like you
your vids are gold.
11:38: "a cross product is the product of vectors which are on the same plane"
Two non-colinear vectors always define a plane, two colinear vectors always define a line, which is always contained in a plane; so two vectors are always on the same plane ;-)
Sorry, that's only my math disorder syndrom at play...
I don't know how to program, but here's my idea for this sort of algorithm:
Create the first line as usual and then from the 2nd point extend the line infinitely and rotate it clockwise (or anticlockwise, depends on the orientation of first line) until you hit another point. Connect 2nd and said point and repeat
Sir, First of all, I am a big big big fan of your challenge videos.
As asked by you, I would love to see you program "Vornoi Diagram and Decaulay Triangulation Problem".
A geometer in my heart is squealing like a child at the moment. Thank you.
Amazing energy!!!
This is sweet ! I was just trying to implement a version of Graham Scan in p5 and was having some difficulties with angle calculation the other day and today you made this !
Graham scan is nice. First you sort it, then just go through with it. This algo isn't Graham scan, though. Maybe next video? Also, you can eliminate most points just by scanning a rectangle and deleting the points inside.
Bob Sedgwick Algorithm book describes the process. That's how I learned it, BTW.
@@simpletongeek Oh, thanks for the reference!
yOu MeaN GrAhAM ScaM
FWIW, the rule for remembering the cross products a x b is that you put the side of your right hand on a and make the palm look in the direction of b. Where your thumb points is the result.
Great job. Simple yet very useful program.
one of the way you can improve that is removing points that are already contained within the convex hull from the set to be tested.
And my first instinct would have been to go with dot products and find the max of dot(normalized(new-current), normalized(current-previous)) with exception for the first point where current-previous is replaced with (0,1).
This also lets you test for enclosure within the current hull by using dot(normalized(new-current), normalized(first-current))
Great tips! Feel free to submit a variation with your ideas to thecodingtrain.com/CodingChallenges/148-gift-wrapping.html
I think you should do video on minimum spanning tree alg visualisation someday
I did a while back! ruclips.net/video/BxabnKrOjT0/видео.html
I thought he was trolling, but maybe not. This happens in other channels with hundreds of episodes... 8-)
Well, the coolest thing about the DeLaunay triangulation is not the circle thing, it's that it is optimal in avoiding thin long triangles which look ugly. In this sense, it is mathematically the most beautiful triangulation of a given set of points.
I'd love to see you take a crack at some 2d boolean algorithms, like the Vatti clipping algorithm
best teacher
This is a nice explanation of the Gift-Wrapping-Algorithm, but it has one big flaw. By sorting the points first a O(n log(n)) time complexity is added, which makes this algorithm very slow. While it seems this algorithm is slower than the graham scan, in many cases it is acutally a lot faster, because sorting takes a lot of time. The sort should be replaced by a simple for loop to identify the leftmost point. In my tests the Gift-Wrapping-Algorithm was always faster than the Graham Scan at least to about 2500 points, then depending on the number of convex hull points found. One of the reasons may be, that sorting actually requires memory access, while just reading the points can take advantage of processor cache.
Thanks for this very important feedback!
It seems as though a way to make this algorithm faster would be to somehow add all points inside the hull as being inside the hull and only checkpoints that are outside the hull. Once you connected the point you are checking to the start point it became clear that it is checking all the points that should be know to be inside the hull. The hard part would be how do you determine what is inside the hull and what is outside? But maybe one of the other algorithms do this.
We need more of this, plz
Bro love and respect for you
have you done a Delaunay Triangulation challenge, I'd like to see it?
Mulțumim!
Quite late, but somewhat related to this. Coding Challenge: Divide an arbitrary 2D polygon into triangles.
+ Polygon can be overlapping.
+ Inside is defined as uneven number of "linehops" from outside.
I love your challenges
Simple optimization, you could exclude points which are already inside the temporary convex hull so you never check it again ! (It's actually using the definition of a convex polygon ;) )
Indeed, great suggestion!
Great video 👍 how about vertex cover coding challenge?
I watched the live version 😂
I am finally working on triangulating a point set. I am picking points in my canvas and making triangles using the cross product to find points outside existing triangles (or inside; that'll be fun...)
Another interesting computational geometry problem: find the empty, convex polygon (subset) with the largest area, given a set of points
Generating a random 3D shape, like a sphere, and getting 4 random points on the sphere and getting the area inside these 4 points. On youtube there is a video about this called “the hardest math problem on the hardest test”
People: "What does ADHD feel like?"
Me: "I realised halfway through the video that he speaks English with the same accent as Kermit the frog, and now I can't listen to his words anymore."
Would love to see a sketch with the conrec algorithm!
You asked for it. I'd like to see you do a Delaunay triangulation video.
I have a feeling that this could have been coded much cleaner had you used generator functions. The algorithm when written inside the generator algorithm would be pretty similar to the gift wrapping algorithm pseudo code you would find online, instead of being "scattered around" in setup and draw. any time a draw happens, you ask for the next value from the generator. The generator could return the new state of the points each time. Neat video though :)
I keep getting people recommending generator functions to me! I've actually never used one, something I definitely need to learn. Thank you for the tip!
At 0:22 on the top right one point is actually out of the hull :)
Coding Challenge Suggestion: Delaunay's Triangulation
It was a very quick introduction :D
For more computational geometry you could try animating a Voronoi Diagram. Eg: en.wikipedia.org/wiki/Voronoi_diagram#/media/File:Voronoi_growth_euclidean.gif
Hi, really late observation but I think you are calculating the cross product of the vector from the origin to the points, not the actual ones you are drawing. It's surprising that it actually works.
Idea: a code that tells you the number of pairs in a scatter plot given a maximum separation allowed for two points to be considered 'pairs'. Uses for this would be if - say - you have a plot with stars' positions and you ran this code for increasing angular separations, keeping track of the total number of pairs per angular separation. As you increase the maximum distance allowed, the more pairs you will see. If you were then to make a log plot (log angular separation vs log number of pairs) you would - in a completely random distribution - have a line of constant slope. However, if in your data set you had systems of gravitationally bound binary stars, you would instead see a bump at lower angular separations above the constant slope line caused by the random distribution. Astrophysicists use this method all the time to find populations of wide binaries in large datasets. However, with large datasets doing this inefficiently can be a disaster, which is why i think its an interesting coding problem.
This is far too advanced for me right now, but wow that wikipedia gif is cool!
It occurs to me that this is probably the underlying code used by AR to take a point cloud and turn it into a collection of planes.
In the last version looks like You can exclude all the points which are already inside boundary.... that would be great optimisation.
Isnt the definition of convex just, hat you can connect evry 2 points with a straight line and the line will be in your shape completely? and concave being just non-convex
Would it be possible to connect all the dots with a non-self-intersecting spiral? Obviously I would not be a true spiral and would likely be quite misshapen but I think you get the idea.
It will be great if you can post a tutorial on the Alpha-shape method as well.
Hi! Can you also please add some real-world use cases of the algorithms you cover in coding challenges? I really like to see you code but it would be great to know where it can be applied.
Great suggestion!
But in the first example of the Gram Scan, there is one point outside the convex hull....
Thank you
Actually, the cross product is the other way round. Still doesn't matter. I really do love computational geometry, and I really look forward to seeing more algorithm visualizations in p5.js!
haha, oops.
No left point! ONLY CENTER IMAGE START NOW!!!
You can use Chan Algorithm it will perform way better
For all interested in a nicely animated version of the probably most efficient of the algorithms, Chan's Algorithm:
github.com/AntonioNoack/ChansAlgorithm (written for a seminar at university by me)
Nice work! You can submit a link to the coding train website if you like!
github.com/CodingTrain/website/wiki/Community-Contributions-Guide
For a new challenge: How about getting your position by triangulation of signals from cell towers or satellites as a simulation?
You could do Triangulations next
Yes, I hope to!
0:15 but both demonstrations show some points outside of the convex hull. Is it not a complete implementation or does it have some bugs?
I think it has some bugs I didn't notice! I will have to revisit that code (which is different than the code I wrote in this challenge.)
Oh no. did i just missed the live stream of this Coding Challenge?
It was this one! ruclips.net/video/rnJgb-mYPEI/видео.html
@@TheCodingTrain oh, thanks!
Couldnt you just put a string around all the points and tighten it? Idk how the logic would work but i think the outcome would be the same
please do Delaunay triangulation it'll be interesting
I have a question for you: what's the average number of points in the convex hull of a random point cloud of size n?
computational geometry idea: straight skeleton
Can you make a vigenere cipher coding challenge?
Why is he claiming that he came with the "Gift Wrapping" algorithm? LOL!
So the three well known algorithms seem to be Jarvis march (gift wrapping), Graham's scan and Chan's algorithm which kind of combines the former two. Is there anything else more efficient that I have overlooked?
Just found that this wikipedia article answers my question: en.m.wikipedia.org/wiki/Convex_hull_algorithms
I really hope to see a video on polygon triangulation.
I thought there is someone else when it came to timeline 8:39 hahahahahahahahahaa
круто!)