Delaunay Triangulation

Рет қаралды 96,034

4 жыл бұрын

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!

Пікірлер: 47

@HoaDucPham 3 жыл бұрын

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 2 жыл бұрын

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 4 жыл бұрын

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 3 жыл бұрын

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.

@dalskiBo 3 жыл бұрын

Lovely video, thanks SCIco.

@tanzeelhassan2934 3 жыл бұрын

Just wow, the video is awesome!

@mwprogrammer 2 жыл бұрын

Thanks for low key saving my exam.

@dalskiBo 3 жыл бұрын

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

@Undead34 2 жыл бұрын

Thank you, i love this video

@sajedehkebriti3548 3 жыл бұрын

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

@ian.ambrose Жыл бұрын

Beautiful video.

@nataliazhang4309 2 жыл бұрын

Thanks! Nice video!

@bln3615 3 жыл бұрын

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

@seunghunlee2598 4 жыл бұрын

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

@ricardopieper11 4 жыл бұрын

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

@ricardopieper11 4 жыл бұрын

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 3 жыл бұрын

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

@muhammadbilalshahid8010 2 жыл бұрын

Awesome, Thanks.

@amolsamota9104 3 жыл бұрын

Great work

@stynod7422 2 жыл бұрын

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

@delicate6930 2 жыл бұрын

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

@louise1021 Жыл бұрын

Amazing!!!

@AlhambraDream 3 жыл бұрын

this is awesome

@temesegenabuhay9408 3 жыл бұрын

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

@Alkis05 3 жыл бұрын

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

@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 7 ай бұрын

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.