I understand it this way: for a given number of points, you draw a triangle whose circumference should cover all the points 1. You take your first point randomly, connect it to each vertex of the first triangle. 2. If a triangle contains a point within its circumference, then you delete that triangle by deleting an edge which connects the chosen point to the vertex of the first triangle. Otherwise, you keep the edge- and the point becomes the new vertex of a new polygon that we will do the same thing with the second point. 3. Keep doing that till you have the ultimate outer polygon that has vertices match the outer points and the tri-elements with vertices match the inner points. (*) easily see that we should take the initial points from the outer ones then work our way in.
How did you decide on what super-triangle to use? Seems a bit arbitrary, can any random size of triangle be used? Also, it seems like it is possible that there are point-sets which would cause points that are in the circumcircle no matter what. I read the Wikipedia briefly and I did not see it mention this, nor any controversies with using Delaunay, which I found odd. I am new to this so take it with a grain of salt though.
I think this algorithm is a inductive method, and this video is the one sub-method of this algorithm, and the magic of creating triangle is not only inductive but also deductive which is more important if you only see this video. (I think this is inductive because it first give points and then tell you inductive all lines from these points. deductive: some video direct using triangle to draw, first draw one and then add the second triangle which base on existing line and not overlapping other existed lines.)
Amazing video.Gave me a excellent understanding and visually explained.Thank you sooo much, it was difficult to gain this understanding as not much people have written or made of video about it so clearly.
If you mean "how to find the circumcircle", wikipedia has the answer en.wikipedia.org/wiki/Circumscribed_circle (Circumcenter coordinates, cartesian coordinates)
You can use it like I do here: editor.p5js.org/ricardopieper/sketches/M2lEVxA64 look at the circumscribedCircle function. This code actually has all the pieces you need to implement the algorithm in the video, together with relevant wikipedia sources.
How do we know that any edges in the 'Super Triangle" aren't relevant? It is possible for there to be some edges on the super triangle that connect to points not on the convex hull of the set of interest, isn't it?
Contruct the Super Triangle 1. find the centeroid from all points 2. create an axis heading to 3 angle (90, 210, 300) degree 3. find all max projection axis for all points that align to our 3 axis (use dot product) and scale it to 1,5 or bigger; 4. the step 3 will result 3 max projection point. 5. find intersection point of all 3 max projection point. 6. the intersection point is your super triangle.
From this presentation, which looks awesome, I gather that for this to work, the points need to be more or less evenly spaced, not truly random. I don't see how it could work with points that are forming clusters, it looks like they will be in circles of cluster's outside vertices.
It actually works better when they're random because you're less likely to encounter infinite-radius circles (i.e. 3 colinear points). As long as your super-triangle encloses all your points, the algorithm will find all of them.
I understand it this way:
for a given number of points, you draw a triangle whose circumference should cover all the points
1. You take your first point randomly, connect it to each vertex of the first triangle.
2. If a triangle contains a point within its circumference, then you delete that triangle by deleting an edge which connects the chosen point to the vertex of the first triangle.
Otherwise, you keep the edge- and the point becomes the new vertex of a new polygon that we will do the same thing with the second point.
3. Keep doing that till you have the ultimate outer polygon that has vertices match the outer points and the tri-elements with vertices match the inner points.
(*) easily see that we should take the initial points from the outer ones then work our way in.
Tragic music in the background, tragic explanation..
Excellent and concise explanation. Kudos to you
Brilliant video, thanks for sharing; concise intro & unusually dark music.
How did you decide on what super-triangle to use? Seems a bit arbitrary, can any random size of triangle be used? Also, it seems like it is possible that there are point-sets which would cause points that are in the circumcircle no matter what. I read the Wikipedia briefly and I did not see it mention this, nor any controversies with using Delaunay, which I found odd. I am new to this so take it with a grain of salt though.
I think this algorithm is a inductive method, and this video is the one sub-method of this algorithm, and the magic of creating triangle is not only inductive but also deductive which is more important if you only see this video. (I think this is inductive because it first give points and then tell you inductive all lines from these points. deductive: some video direct using triangle to draw, first draw one and then add the second triangle which base on existing line and not overlapping other existed lines.)
Amazing video.Gave me a excellent understanding and visually explained.Thank you sooo much, it was difficult to gain this understanding as not much people have written or made of video about it so clearly.
How do you know where to put the vertices of the super triangle??
i just put the vericies at a number i knew was outside my domain
I made a square containing all my points and then drew the equilateral triangle which circumscribes the square
The music choice is sensational
Hi! your video help to me, but I can't understand what is the standard for find new circumcircle (02:00)
If you mean "how to find the circumcircle", wikipedia has the answer en.wikipedia.org/wiki/Circumscribed_circle (Circumcenter coordinates, cartesian coordinates)
You can use it like I do here: editor.p5js.org/ricardopieper/sketches/M2lEVxA64
look at the circumscribedCircle function. This code actually has all the pieces you need to implement the algorithm in the video, together with relevant wikipedia sources.
Ricardo Pieper have you seen Fade2D code (in case) it is in C++. I want to ask some question if in case someone used it
How do we know that any edges in the 'Super Triangle" aren't relevant? It is possible for there to be some edges on the super triangle that connect to points not on the convex hull of the set of interest, isn't it?
Contruct the Super Triangle
1. find the centeroid from all points
2. create an axis heading to 3 angle (90, 210, 300) degree
3. find all max projection axis for all points that align to our 3 axis (use dot product) and scale it to 1,5 or bigger;
4. the step 3 will result 3 max projection point.
5. find intersection point of all 3 max projection point.
6. the intersection point is your super triangle.
Voronoi diagrams can be computed using the same methods of finding Delaunay triangulation.
seriously? That is helpful, even tough I can't really see how right now
@@manuarteteco6153 They share duality.
Beautiful video.
Thank you, i love this video
Lovely video, thanks SCIco.
From this presentation, which looks awesome, I gather that for this to work, the points need to be more or less evenly spaced, not truly random. I don't see how it could work with points that are forming clusters, it looks like they will be in circles of cluster's outside vertices.
It actually works better when they're random because you're less likely to encounter infinite-radius circles (i.e. 3 colinear points). As long as your super-triangle encloses all your points, the algorithm will find all of them.
Awesome, Thanks.
Thank you, if you could do one also on building weighted diagrams that would be great.
I think Joker's gonna attack in the end
Thanks! Nice video!
is there any rule to draw the circumcircle for the triangle... Mr
The only rule is for the circle to contain at least one vertex.
Just wow, the video is awesome!
Amazing!!!
I think this algorithm will have to do O(N²) operations to build a triangulation
Awesome! Just come with other movies! It was really intuitive
Bro can you do a video about Frontal advancement method? I'm a mallu too :-) , nice video.
Why music is so scary?...
this is awesome
Great work
And what is the idea of this background music?
Scary sounds
Great video, but why so scary music?
People being smart asses in a TH-cam comments section 🤭
great video odd music choice though
very bad explanation, waste of time. sorry
Interesting video but man the music is horrible for such topic
The music added nothing apart from distraction. Why did you feel you had to do that?
code: geom.at (Fade2D code)
why the funeral music? 🤣
code
?
The name is Fade2D
very poor selection of music.
The music is way too dramatic :D
Stop the music, maybe talk instead ... also why stretch the video with unnecessary text
Annoying music