Interactive Voronoi Diagram

This was part of a final project for CS 324E at UT Austin, taken Spring 2017.




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 | )

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! :)

Source Code

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