An Overview of Voronoi Diagrams and Triangulation

deleanayandvoronoi_edited.png

What is a Voronoi Diagram?

Voronoi diagrams can be applied to and used in most science and engineering fields, anything from art and UI to robotics and astrophysics (Lynch, Wikipedia) - almost any circumstance where you have a discrete set of data and care about distance. Visually they are maps of surfaces divided into regions, where all the points within a region are closest to a known site. The voronoi diagram on the right partitions a set of point as shown by the colored cells such that each point is only in one cell.

voronoi_edited.png

What is Delaunay Triangulation?

Delaunay triangulations are closely connected to Vornoi diagrams. Given any list of points, its Delaunay triangulation is the set of triangles that connect all the points together to form a web. The catch? The smallest angle in each triangle must be maximized. The diagram on the left shows the Delaunay triangulation in the blue.

deleanayandvoronoi.gif

Read More...

Interactive Tools

desmos.png
other.png

Visualize and play with Fortune’s Algorithm

Create your own Voronoi diagram