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 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.
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 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
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.
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!
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 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.
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.
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
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.
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.
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".
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.
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.
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
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 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...)
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.
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.
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”
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.
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.
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))
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.
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.
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
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?
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.
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.
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."
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 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
That would not necesarilly give a convex hull. Also, how do you decide ho many far away points you choose.' Take an example where all points lye in the unit circle. and two points sit 2,2 and 3,4 the resulting shape will wrap all points, but Could have an indentation
Is there an algorithm that determines for any closed path of points (concave or convex) whether another specified point is inside or outside of that path?
Yes. The easiest one to understand is the even-odd test. Make a line from a point "really far away" to the test point. Check to see if this line intersects with any of the lines in the closed path. If the number of collisions is even, the point is outside the path, if it is odd, the point is inside the path. This works because every time the line enters or exits the shape, it intersects with the path leading to a pattern of outside-inside-outside-inside-...etc. The test line can't extend into or out of the shape without intersecting a line, and it likewise can't intersect a line in the path without extending into or out of the shape.
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.
The way you interact , the way u express ur intrest in coding, your logical thinking inspires me
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!
Mulțumim!
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
Explanation is sooo engaging....
I recommended this way back in early 2018 on the topics GitHub, glad to see it done 😊
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!
Someone please make a compilation of all of Dan's adorable fumbles including but not limited to "Graham's Scam" 😂
Always love seeing a new coding train video in my inbox!! Great video, found it really interesting!
This guy gives me motivation to be calm during problems
This is exactly what I need for my project thank you
Just had a class on geometric algorithms last semester, but needless to say, your presentation is way more exciting and clear.
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!
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.
Thank you for always giving a good lecture on a new topic.
Fantastic topic! Never knew this existed.
I love these coding challenges
Bro this video is highly underrated! Thank you!!
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 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
the enthusiasm tho wow I want to be this excited about coding too
new coding challenge? let me stop whatever i was doing
He is such a character, i love it
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.
Best coding teacher ever
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!
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 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.
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.
looking forward to the computational geometry series...i stumbled across delauney triangulation on gamedev once
Amazing energy!!!
omg... i wish i could be smart like you
your vids are gold.
Omg you are the best coding teacher in my life!!
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
Great job. Simple yet very useful program.
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
We need more of this, plz
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.)
Would love to see a sketch with the conrec algorithm!
have you done a Delaunay Triangulation challenge, I'd like to see it?
14:09 how is the cross product negative ? it should be positive as we are moving in counter clockwise direction from vector a to vector b
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 ? ;)
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".
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.
A geometer in my heart is squealing like a child at the moment. Thank you.
Bro love and respect for you
I love your challenges
I'd love to see you take a crack at some 2d boolean algorithms, like the Vatti clipping algorithm
At 0:22 on the top right one point is actually out of the hull :)
Great video 👍 how about vertex cover coding challenge?
I watched the live version 😂
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.
I think you should do video on minimum spanning tree alg visualisation someday
I did a while back! ua-cam.com/video/BxabnKrOjT0/v-deo.html
I thought he was trolling, but maybe not. This happens in other channels with hundreds of episodes... 8-)
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
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 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...)
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.
best teacher
Could you do a concave hull algorithm video?
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!
It will be great if you can post a tutorial on the Alpha-shape method as well.
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”
can you cover a concave hull algorithm as well?
Could you use this to make Travelling Salesman in future video?
Amazing video, but what do you mean by higher dimensions at 1:19 ? Is it 3D or something else?
prob the 10th dimension lol
Yes, you can have a "convex hull" in 3D which would be the convex surface that holds a collection of points in 3D space. . and so on and so forth!
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.
Another interesting computational geometry problem: find the empty, convex polygon (subset) with the largest area, given a set of points
It was a very quick introduction :D
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
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
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.
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!
This is far too advanced for me right now, but wow that wikipedia gif is cool!
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
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
In the last version looks like You can exclude all the points which are already inside boundary.... that would be great optimisation.
But in the first example of the Gram Scan, there is one point outside the convex hull....
Can you make a vigenere cipher coding challenge?
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.
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?
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.
You asked for it. I'd like to see you do a Delaunay triangulation video.
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.
Thank you
when will more computational algorithms come back?
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."
excellent vid! but why so fast?
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!
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
For a new challenge: How about getting your position by triangulation of signals from cell towers or satellites as a simulation?
Coding Challenge Suggestion: Delaunay's Triangulation
so... a way to make it a little more efficient would be to not check the points inside the shape... I wonder how you would do that...
I really hope to see a video on polygon triangulation.
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
Could you get the position of the center of the canvas and wrap around all the points that are most far away from the center?
That would not necesarilly give a convex hull.
Also, how do you decide ho many far away points you choose.'
Take an example where all points lye in the unit circle. and two points sit 2,2 and 3,4 the resulting shape will wrap all points, but Could have an indentation
Is there an algorithm that determines for any closed path of points (concave or convex) whether another specified point is inside or outside of that path?
Yes. The easiest one to understand is the even-odd test. Make a line from a point "really far away" to the test point. Check to see if this line intersects with any of the lines in the closed path. If the number of collisions is even, the point is outside the path, if it is odd, the point is inside the path.
This works because every time the line enters or exits the shape, it intersects with the path leading to a pattern of outside-inside-outside-inside-...etc. The test line can't extend into or out of the shape without intersecting a line, and it likewise can't intersect a line in the path without extending into or out of the shape.
Instead of saying leftmost, perhaps the *rest* of the pts are counter-clockwise-most (ccm)?
Great point!
@@TheCodingTrain it confused me, a little bit, that's all. I'm too literal