Delaunay triangulations are closely connected to Voronoi diagrams. Named after the Soviet-era mathematician Boris Delaunay, the Delaunay triangulation of a set of points is the set of triangles that connect all the points together to form a web, with each triangle having the largest possible internal angles. In any triangulation, the smallest angle is always maximized (Wolfram, Wikipedia).
These triangulations are incredibly useful for just about as many things as Voronoi diagrams, from CAD and 3D modeling to video game development. They provide simple ways to create a discrete surface over any set of points, and ensure that the triangles produced are the largest possible with few if any thin angles.
Image credit: Wikipedia
A Delaunay triangulation is a triangulation of all the points in P such that all the circumcircles of each triangle are empty.
Image credit: DataGenetics
Image credit: DataGenetics
Delaunay triangulations are only unique for circles that touch only three points.
The avoidance of sliver triangles proves extremely helpful for computer graphics and 3D modeling, as larger-angled triangles behave better in physics simulations and surface texturing than thinner ones.
Resources
Weisstein, Eric W. "Delaunay Triangulation." From MathWorld--A Wolfram Web Resource. https://mathworld.wolfram.com/DelaunayTriangulation.html
“Delaunay Triangulation.” Wikipedia, Wikimedia Foundation, 13 Dec. 2020, https://en.wikipedia.org/wiki/Delaunay_triangulation
"Voronoi Tessellations." DataGenetics, 01 May 2017, https://datagenetics.com/blog/may12017/index.html
コメント