When do we flip an edge to get a Delaunay triangulation? This video visualizes an algorithm called Flip Edges which is the simplest (but slowest) Delaunay triangulation algorithm. But this rule is true for all Delaunay algorithms. The basic idea is that we go through all edges and ask if we should flip this edge:
1. The current edge in the video is the black edge going between two corners in a triangle.
2. This current edge belongs to a triangle and the corners in this triangle are also on the edge of a circle.
3. There's also a triangle on the "opposite" side of the current edge. These two triangles share two corners. The corner in this opposite triangle (the corner not being shared) is the important test point. If this corner is within the circle formed by the corners in the other triangle, then we should flip the edge.
(There's also a rule that the two triangles should together form a convex shape or we can't flip the edge)
Tutorial: www.habrador.com/tutorials/ma...
If you are interested in the source code, it's available here in my open source Computational Geometry Unity library: github.com/Habrador/Computati...
You can also follow me on twitter: / eriknordeus
#unity #unity3d #MadeWithUnity #OpenSource #geometry #triangulation #mathematics #visualization #algorithm #delaunay
1 мар 2020
