Interactive Voronoi Diagram



About

This is an interactive Voronoi diagram (more information on Wolfram MathWorld and Wikipedia). A modified version of this code is also used in the header above the navigation buttons on the main pages of my website.

I think it is particularly interesting to see how using different metrics affects the result. I recommend adding a few points (click the canvas) before looking at the result of different metrics (press 'n').

In this demonstration, I have implemented 3 different metrics. The table below describes them. Here, I define the point \mathbf{a} = (x_1, y_1) as the point of interest (represented by black dots on the above display), and \mathbf{b} = (x_2, y_2) as any other point on the plane.

Name
Measurement
Manhattan distance
\lVert \mathbf{b} - \mathbf{a} \rVert_1 = \left | x_2 - x_1 \right | + \left | y_2 - y_1 \right |
Euclidean distance
\lVert \mathbf{b} - \mathbf{a} \rVert_2 = \sqrt{(x_2 - x_1)^2 + (y_2 - y_1)^2}
Chebyshev distance
\lVert \mathbf{b} - \mathbf{a}\rVert_\infty = \max( \left | x_2 - x_1 \right |, \left | y_2 - y_1 \right | )

I chose these three because they use the L_1, L_2, and L_{\infty} norms, respectively, which are pretty much the only norms I've ever used. I may add more later.

Instructions

Alternatively, you can press '1' to use the Manhattan distance, '2' to use the Euclidean distance, '0' to use the Chebyshev distance, 'n' to toggle through all metrics, and 'r' to clear the display.

Comments

This page was linked on Agile Scientific's blog post The norm: kings, crows and taxicabs by Matt Hall. Welcome, new visitors! :)

The primary reason I made this was to see the effect of using different metrics on the generated diagram (particularly in application to nearest neighbor interpolation). As a result, I use a relatively greedy pixel-by-pixel traversal to generate the figure, as opposed to some of the more elegant and efficient algorithms to generate Voronoi diagrams, which seemed to be difficult to implement for multiple metrics. However, since this is only a toy example, the method I use should be sufficient.

Source Code

You can get the source code here (ZIP file, 20 kB). You will need the Processing software package to run the program.