Fast Distance Comparison Algorithm

Hey, this is a quick post about quickly comparing the distance of two points (2D or 3D). In this article, I’ll be using Roblox Lua for demonstration, but this method ought to work in many different languages. The goal is to find a fast way to answer the questions:

• Is a point within a certain distance of another point?
• Which of these two points are closest to this point?

The Boring Context

Pst. You can skip to the next heading, but not if you didn’t pay attention in geometry.

Most readers will already be aware of the Pythagorean theorem, which is taught in high-school or in early undergrad classes in college. It simply states that the sum of the squares of two sides of a right triangle is equivalent to the square of the length of the hypotenuse of that triangle. Or, put simply, a^2+b^2=c^2 (where a and b are the side lengths and c is the hypotenuse).

It is from this theorem that we get the distance formula by simply taking the square root of both sides (so we get c by itself). So all-in-all, the distance of two points (again, either 2D or 3D) is found by calculating the difference between two points’ components. Square the results, and find the sum. The last step is taking the square root of the result, which is the expensive computation.

If only there were a way to avoid the expensive square root computation!

Taking the Shortcut

One of the best ways to solve a problem is to realize when you’re looking for information you don’t need. It may be trivial to realize that the following functions are both strictly increasing:

• f(x) = x
• f(x) = x • x

But this is where the fast distance comparison algorithm comes in: If we simply don’t take the square root when calculating the distance, we’ll get the distance squared. As the actual distance between two points grows or shrinks, the square of that will also grow/shrink accordingly. If we have a known distance to check against, we can easily calculate its square (by just multiplying it by itself, a much cheaper operation than square root).

Implementation in Roblox Lua

You can apply this to any language.

-- Two points
pointA = Vector2.new(2, 1)
pointB = Vector2.new(5, 5)
-- And the distance to compare to
distance = 6

First, calculate the offset of the points. (Note that the order in this subtraction doesn’t matter. This is because the results’ components will be squared anyway, thus losing the sign)

local offset = pointB - pointA

Then, we want to find c squared. Calculate the sum of the components’ squares:

local cSquared = offset.X*offset.X + offset.Y*offset.Y

Here’s the clever part! Instead of taking the square root of this to get the points’ actual distance, we instead square the distance we’re comparing to!

if cSquared <= distance*distance then
    print("The points are within " .. distance .. " units")
else
    print("The points are farther than " .. distance .. " units apart")
end

There we have it. No slow square root calculations, and it works just as accurately.

But what if I want the actual distance?

You can still get it by taking the square root of cSquared. You just don’t need to calculate that if you’re only comparing two distances. In Roblox Lua, you can use Vector3’s magnitude property (which is calculated the first time you need it). But if you really want to be spoon-fed the Lua code for that, I’m happy to do that:

local actualDistance = math.sqrt(cSquared)

-- Or, put all in one line
local cSquared = (pointB.X-pointA.X)^2 + (pointB.Y-pointA.Y)^2

-- These are expensive. Don't do these unless you really need it:
local actualDistance = math.sqrt(cSquared)
local actualDistance = (pointB - pointA).magnitude

Can this be made faster by checking taxicab distance*?

*Taxicab distance, sometimes called Manhattan distance, is the distance between two points but only travelling parallel to an axis, like you’re taking a taxicab in NYC.

In most implementations, no. The extra calculation of the taxicab distance in the comparison tends to slow things down even in optimal cases. HOWEVER, if you’re still calculating square roots when comparing distances, it can be very worthwhile if you expect a large portion of your cases to be caught by the taxicab check. Otherwise you’re just adding more work and making things even slower.

That’s all, folks!

You can ask me questions about this via Twitter and I’ll be happy to answer them!