Voronoi Diagrams

Marchete
6,688 views

Open Source Your Knowledge, Become a Contributor

Technology knowledge has to be shared and made accessible for free. Join the movement.

Create Content

Voronoi Diagrams: Distance Functions

Voronoi Diagrams are heavily dependent of distance functions. Usually Euclidean distance is used on these diagrams while the Manhattan distance is preferred on grid-based maps. But what is a distance function?

In the real world, the distance from a point A to a point B is measured by the length of the imaginary straight line between these two points. That's the Euclidean distance. However, you can measure distances in other ways, for instance, using time. If it takes you 1 hour by car to travel from city A to city B, and it takes you 2 hours to travel from city A to city C, you can conclude that city B is closer, regardless of the actual geographical distance.

There are many ways to measure distance. Straight line, gas costs, travel time, etc. Distance functions are different ways to measure distances. In this course we are focusing on two basic distance functions: Euclidean and Manhattan.

Euclidean Distance

Euclidean distance, also called L² norm, measures distance using a straight line in an Euclidean space. In a 2D space it is the same thing as the Pythagorean formula:

d(a,b)=(xbxa)2+(ybya)2

The square root of the sum of the squared differences of movement on both axis. Here is an implementation of the Euclidean distance function used in a Voronoi Diagram. Try it out! You can see that the border between two sites is exactly equidistant to the two points (it's at the middle of the straight line between the two points).

Try Euclidean Voronoi Out
1
2
3
4
5
6
7
8
9
10
11
12
/*
Parameters:
a: With two components: a[0] and a[1], 'x' and 'y' coordinates
b: With two components: b[0] and b[1], 'x' and 'y' coordinates
Returns: Euclidean Distance value.
*/
function distancefunction(a, b) {
var dx = b[0] - a[0];
var dy = b[1] - a[1];
return Math.sqrt(dx * dx + dy * dy); // Euclidean distance formula
}
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

Manhattan Distance

Manhattan distance, also called L1 norm, measures distance on a grid (no diagonal movement is allowed). In a 2D space:

d(a,b)=|xbxa|+|ybya|

The absolute value of the sum of the differences of movement on both axis. Here is an implementation of the Manhattan distance function used in a Voronoi Diagram. Try it out! You can see that the border between two sites is exactly equidistant (according to the Manhattant distance) to the two points.

Try Manhattan Voronoi Out
1
2
3
4
5
6
7
8
9
10
11
12
/*
Parameters:
a: With two components: a[0] and a[1], 'x' and 'y' coordinates
b: With two components: b[0] and b[1], 'x' and 'y' coordinates
Returns: Manhattan Distance value.
*/
function distancefunction(a, b) {
var dx = b[0] - a[0];
var dy = b[1] - a[1];
return Math.abs(dx) + Math.abs(dy); // Manhattan distance formula
}
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

As you see, the Manhattan distance function returns a very different diagram.

Performance

If you maximize the viewer, you'll notice the rendering of the Voronoi Diagram is quite slow. This is because the naive algorithm is slow. Since we check for each pixel what site it is in, for p pixels and s sites, the time complexity of the algorithm is O(p * s).

In the following lessons we will review another algorithm which is faster when number of sites are high.

Open Source Your Knowledge: become a Contributor and help others learn. Create New Content