Delaunay Triangulation

Creating quality meshes is a task common in computer graphics and numerical analysis like finite element methods. Among many others, one technique of much importance is the Delaunay triangulation.
In this video, we try to introduce you to the Delaunay triangulation and its computation by the Bowyer-Watson algorithm. This video focuses more on the computational part. So, let's enjoy the video!

[@HoaDucPham]

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.

[@sanjanakomateswar8191]

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.

[@SecondThread]

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?

[@leonardoherfianto897]

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.

[@tanzeelhassan2934]

Just wow, the video is awesome!

[@dalskiBo]

Lovely video, thanks SCIco.

[@dalskiBo]

Brilliant video, thanks for sharing; concise intro & unusually dark music.

[@mwprogrammer]

Thanks for low key saving my exam.

[@Undead34]

Thank you, i love this video

[@sajedehkebriti3548]

Awesome! Just come with other movies! It was really intuitive

[@bln3615]

Thank you, if you could do one also on building weighted diagrams that would be great.

[@ian.ambrose]

Beautiful video.

[@muhammadbilalshahid8010]

Awesome, Thanks.

[@nataliazhang4309]

Thanks! Nice video!

[@louise1021]

Amazing!!!

[@amolsamota9104]

Great work

[@AlhambraDream]

this is awesome

[@seunghunlee2598]

Hi! your video help to me, but I can't understand what is the standard for find new circumcircle (02:00)

[@ricardopieper11]

If you mean "how to find the circumcircle", wikipedia has the answer en.wikipedia.org/wiki/Circumscribed_circle (Circumcenter coordinates, cartesian coordinates)

[@ricardopieper11]

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.

[@jamesj2869]

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

[@stynod7422]

How do you know where to put the vertices of the super triangle??

[@delicate6930]

i just put the vericies at a number i knew was outside my domain

[@supergreatoli2]

I made a square containing all my points and then drew the equilateral triangle which circumscribes the square

[@NeZversSounds]

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.

[@robotlegs]

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.

[@temesegenabuhay9408]

is there any rule to draw the circumcircle for the triangle... Mr

[@Alkis05]

The only rule is for the circle to contain at least one vertex.

[@msssivadas10]

Voronoi diagrams can be computed using the same methods of finding Delaunay triangulation.

[@manuarteteco6153]

seriously? That is helpful, even tough I can't really see how right now

[@VADroidTS555]

@@manuarteteco6153 They share duality.

[@husseinjafarinia224]

I think Joker's gonna attack in the end

[@Rajgrv100]

Bro can you do a video about Frontal advancement method? I'm a mallu too :-) , nice video.

[@user-zk1hp1wp3s]

Scary sounds

[@jamesj2869]

code: geom.at (Fade2D code)

[@subject2749]

great video odd music choice though

[@roman_roman_roman]

Why music is so scary?...

[@lovegarbage]

The music added nothing apart from distraction. Why did you feel you had to do that?

[@sk-7523]

Great video, but why so scary music?

[@paradigmnnf]

And what is the idea of this background music?

[@AmanGupta-wb2xh]

code
?

[@jamesj2869]

The name is Fade2D

[@achibaba]

very bad explanation, waste of time. sorry

[@TauranusRex]

The music is way too dramatic :D

[@TheBeansChopper]

Stop the music, maybe talk instead ... also why stretch the video with unnecessary text

[@fkeyvan]

Annoying music

[@gandoreme]

very poor selection of music.