Different Measures of Distance

Posted on August 25, 2016
Tags: geometry

How far is it from one place to another? How does that change if you’re on a flat plane? What if that plane has discrete distances, like a checkerboard, or Civ map, or pixels on a screen?

If we’ve got two points, how far do you have to move to get from one to the other?

Euclidean Distance

The shortest distance between two points

The shortest distance between two points

This is the go-to of distance calculations. If you’re talking about continuous, uniform planar (2d) space1, Euclidean distance is the shortest distance between two points.

In the most general sense, the way you get this distance is by measuring it. If you’re lucky enough to be using Cartesian coordinates, then you can calculate the distance based on the distance between the two coordinate points. For our purposes, I’m going to use \(a\) and \(b\), located at \((x_1, y_1)\) and \((x_2, y_2)\).

Pythagoras figured out how to calculate the length of the hypotenuse of a right triangle. The fun part is that, with Cartesian coordinates, any pair of points can now define a right triangle. Just take one point with an x coordinate from one point and a y coordinate from the other, and the triangle itself can be defined as \(((x_!, y_1), (x_1, y_2), (x_2, y_2))\)2.

At that point, it becomes pretty easy. The length of the two sides is just the absolute value of the difference between their x and y coordinates. So, \(|x_1 - x_2|\) and \(|y_1 - y_2|\). Those are easy to plug into the Pythagorean equation to get the distance between the points (\(d\)):

\[d = \sqrt{ |x_1 - x_2|^2 + |y_1 - y_2|^2 }\]

In code, this might look something like:

def eucliddistance(x1, y1, x2, y2):
    xdist = abs(x1 - x2)
    ydist = abs(y1 - y2)
    return math.sqrt( (xdist ** 2) + (ydist ** 2) )

This all seems a bit unnecessary, though, right? Cartesian coordinates are universal. They’re how we think about points. All of our screens are Cartesian planes, and even our 3d worlds are Cartesian. Done and done.

Still, I think it’s good to appreciate how we got here. Why? Because it doesn’t work for our purposes.

A Euclidean distance Voronoi diagram

A “point”, to Euclid, is infinitesimal – it has no size, nor shape. And a Euclidean plane is continuous – there is no “smallest distance” you can move.

Pixels, and graph squares, on the other hand, take up space. And if you want to get from \((0,0)\) to \((7,14)\) on a discrete plane, there’s no such thing as moving 15.56247….. That’s the nature of a discrete space – everything’s an integer. And the other fun bit is that you can’t move in arbitrary directions. On a square grid, you’ve only got 8 directions to go, at most.

It is also, frankly, a bit costly to calculate. Square roots are a bit more complicated than adding and subtracting.

Still, Euclidean distance is the definition of distance. And though we can’t use it to determine distance of movement, we can still use it for comparative purposes.

Voronoi Diagrams

For illustration purposes, I’ve decided to use Voronoi diagrams. Voronoi diagrams are a way of splitting up planes around a set of sites, such that all points in the plane are associated with the closest site.

The simplest, slowest possible way to generate such a diagram is to iterate over each pixel in an image, calculate the distance between that pixel and each site, sort the sites by distance, and assign that site to the pixel. So I coded that up. I’ve put that code up on github. Nothing fancy going on, I assure you.

By looking at the Voronoi diagrams for the same set of sites, using different distance measures, we can get an appreciation for how those measures vary, and what their characteristics are.

Manhattan Distance

A taxicab distance Voronoi diagram

The island of Manhattan is densly populated, and densely built. For our purposes, though, it’s also, notably, laid out like a grid. If you want to get two blocks up and two blocks over, you’re going to have to move four total block lengths to get there. And that’s a pretty straightforward distance measure.

It’s also known as taxicab distance, rectilinear distance, and a bunch of other things. And it’s the simplest calculation we’re going to be making. Just add the lengths of each side of our triangle:

\[d = |x_1 - x_2| + |y_1 - y_2|\]

In code, it might look like this:

def taxidistance(x1, y1, x2, y2):
    return (abs(x1 - x2) + abs(y1 - y2))

If you’re on a checkerboard grid, and you are limited in movement to only the four cardinal directions, this is how you’re going to measure getting from place to place. If you want to get from \((0,0)\) to \((7,14)\) in a taxi, you’re going to go 21 squares, which is a fair bit further than 15.56.

If you take a look at the Voronoi diagram derived from taxi distance, you’ll see that the shapes have changed from straight-edged polygons to odd, almost art-deco-like shapes. In particular, some of the places where there were very long, thin cells in the Euclidean version have changed to blocky, angled, and often much distorted versions.

Civ Distance

A Civ distance Voronoi diagram

If Manhattan distance is what you reckon with when you can only move in the four cardinal directions, what do you do when you can move in all 8 possible directions? Up until the most recent edition, the Civilization games had exactly that scenario3. So let’s call this the Civ distance.

Calculating this one is also easy. Instead of adding the sides together, you just take the length of the longest side.

How’s that work, exactly? Well, if you’re going from \((0,0)\) to \((7,14)\), you go at an angle for 7 squares (moving twice as fast as taxicabs). At that point, you’re at \((7,7)\), and it’s a straight shot to \((7,14)\) only 7 squares away. Just 14 squares total.

Mathematically, it looks like this:

\[d = \max(|x_1 - x_2|, |y_1 - y_2|)\]

And in code, something like this:

def civdistance(x1, y1, x2, y2):
    return (max(abs(x1 - x2), abs(y1 - y2)))

Again, very simple. And 14 is actually shorter than 15.56. By taxi, up and over is a distance of two, by Euclid that same distance is 1.41 and change. But by Civ distance, that same span is only one. That, of course leads to some different distortions in the voronoi diagram. Where the taxicab Voronoi cells stretched up, down, left, and right, the Civ cells are stretching further in the diagonals.

Overall, Civ distance is truer to Euclid than taking the taxi, but it’s still a very different beast.

D&D Distance

Perhaps you’ve played some Dungeons & Dragons. Perhaps you’ve specifically played 3.5ed4. That game was notorious for its complex, tactical, grid-based combat system. Each square represented 5 feet of space, and each character had a limited amount of movement per turn.

A D&D distance Voronoi diagram

Now, it didn’t make sense to allow only movement in the four cardinal directions. That would, if nothing else, be incredibly frustrating for players trying to move their characters around the map.

They also didn’t want to allow willy-nilly Civ-style movement, since that would offer a clear advantage to anyone who wished to use the diagonals5.

Ultimately, they decided on an iterative process which was a bit more complex:

The net result is that, if you start out moving diagonally only, it’s 5 feet, then 15, then 20, then 30, then 35, then 45, etc. Translating feet to grid square units, it’s 1 unit, then 3, then 4, then 6, then 7, then 9.

That pattern, as it turns out, is the floor of 1.5 * the diagonal distance.

To generalize that to more than just the purely diagonal, we figure out how much we can go straight, then do the rest diagonal, and add them together:

\[d_1 = \max(|x_1 - x_2|, |y_1 - y_2|) - \min(|x_1 - x_2|, |y_1 - y_2|)\] \[d_2 = \lfloor 1.5 \times (\min(|x_1 - x_2|, |y_1 - y_2|))\rfloor\] \[d = d_1 + d_2\]

And in code, that looks like this6: ~ {.python} def dandddistance(x1, y1, x2, y2): mindist = min(abs(x1 - x2), abs(y1 - y2)) maxdist = max(abs(x1 - x2), abs(y1 - y2)) return ((maxdist - mindist) + (1.5 * mindist)) ~

Looking at the Voronoi diagram, this is easily the closest match to Euclid. And that’s not surprsing, really. When Euclid things up and over is 1.41 and change, taxicabs and Civ think it’s 2 and 1, respectively, D&D thinks it’s (about) 1.5, which is much, much closer to the continuous distance. To get from \((0,0)\) to \((7,14)\) by way of D&D distance is 17, which is pretty close to the 15.56 of Euclid, and without the distortions of Civ.

Of course, it’s a bit more complex to calculate than Civ or taxi, but it doesn’t require taking any square routes, which marks it as still computationally simpler than Euclid. And it’s grid-native. The designers of 3.5 did a good job finding a relatively simple approximation for distance.

Conclusion

And here we are at the end. Hopefully getting from point \(a\) to point \(b\) wasn’t too rough, and I know I learned a thing or two on the way.

Things get more complicated when you start measuring things in three dimensions. The D&D algorithm, particularly, is unlikely to scale well as you end up figuring out the appropriate values for each of the 26 different directions you can go. Maybe I’ll revisit this again.

And let’s not forget non-spatial distances! Hamming distance is particularly fun to think about. It has uses in small-scale AI tasks like autocorrect, as well as in very-large-dimension binary vector spaces7. I guess I’m saying that distances are fascinating things, and there’s so much more to talk about.

Thanks for bearing with me.


  1. It holds for 3d and higher-dimensional spaces, too.

  2. Or \(((x_!, y_1), (x_2, y_1), (x_2, y_2))\) if you’re feeling frisky

  3. For an even longer time, the king piece on a chessboard had the exact same abilities, which is why this is probably more commonly known as “chessboard distance”, or Chebyshev distance, after Pafnuty Chebyshev, a 19th-century Russian mathematician. But I’ve played more Civ than chess, frankly.

  4. Or its offshoot, Pathfinder; or, for that matter, any of the d20 games that also derived from that source

  5. When it came time to publish the 4th edition of D&D, however, they changed their mind on this. The complexity of the 3.5 distance calculation wasn’t worth the verisimilitude, so they moved to using Civ distances instead. This decision also led to the infamous square fireballs, but no system is perfect.

  6. You might notice that there isn’t a min or math.floor call in that code. There was, for a bit, but it was generating some strange artifacts, where strange striping was occurring. I suspect that’s due to an odd quantizing effect, but haven’t looked into it deeply. In the meantime, using the un-floored numbers produce a more coherent image.

  7. Obviously



    For some machine learning tasks, you end up representing different things in very large vector spaces (one dimension for each “feature” you are keeping track of). In many cases, binary features are more tractable and just as useful – for example, you might keep track of whether a certain word shows up in a document, rather than how many times it shows up. When those two situations coincide, Hamming distance becomes more palatable and tractable than Euclidean distance.]