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.

[ashaswathi]

Excellent and concise explanation. Kudos to you

[mikelosmikes]

Tragic music in the background, tragic explanation..

[sanjanakomateswar]

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?

[dalskiBo]

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

[stynod]

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

[prosperitystar]

I think this algorithm will have to do O(N²) operations to build a triangulation

[msssivadas]

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

[seunghunlee]

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

[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.

[temesegenabuhay]

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

[bln]

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

[husseinjafarinia]

I think Joker's gonna attack in the end

[nickvaleontis]

Interesting video but man the music is horrible for such topic

[Rajgrv]

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

[tanzeelhassan]

Just wow, the video is awesome! <3

[paradigmnnf]

And what is the idea of this background music?

[sajedehkebriti]

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

[lovegarbage]

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