Voronoi Diagrams and Delaunay Triangulation

Download Source Code (88 Kb)

Drag the points of the Voronoi diagram with the mouse and see how the diagram changes in real time!

The Voronoi diagram is Named after the mathematician
M. G. Voronoi who explored this geometric construction in 1908. However,
as early as in 1850 another mathematician, G. L. Dirichlet, studied the
problem. Accordingly the Voronoi diagram is sometimes named Dirichlet tessellation.

The Voronoi diagram of a set of points P is a set of polygonal areas W. For each point pi, a polygonal area w(pi) is defined such that every point contained in this polygonal area is closer to the point pi than to any other point in P. The Voronoi polygon of a point can be constructed by clipping the area with a line that bisects the lines between this point and its surrounding points.

The Delaunay triangulation is close related to the Voronoi diagram. The triangulation is named after B. Delaunay, who first made use of this dual relationship. If the Voronoi diagram is used as a basis, the Delaunay triangulation can be constructed by drawing the lines between the points in adjacent polygons i.e. those which share a common edge. The result is a triangular network.