Thursday, 25 August 2011

Approximate Distance between Two Points

Is there an approximate way to calculate distance between two points?

Normally I would use
    D = sqrt( dx^2 + dy^2 ).

But I didn't want to use sqrt().

Note: I have assumed that dx and dy are always positive by using absolute values.

Consider a case where dx >= dy:

After normalizing by dividing dx and dy by dx,

    D' = D / dx = sqrt( 1 + (dy/dx)^2 )

Plotting this from 0 to 1 shows a flat-ish curve. It could be approximated by a straight line or, as I have done, by a quadratic.

    D' = Ax^2 + B

Plugging in two extreme points (0,1) and (1,sqrt(2))

When x=0, D'=1 therefore B=1

And when x=1, D'=sqrt(2) therefore A=sqrt(2) - 1 (about 0.4142)

So, for dx>=dy (and dx!=0)

    D = 0.4142 * dy^2 / dx + dx

And for dx<dy (and dy!=0),

    D = 0.4142 * dx^2 / dy + dy   (dx and dy are swapped)

Average error seems to be less than 1% - good enough for what I want and simple.

By using different 'tuning' points, better accuracy can be achieved

Another approach (using a linear approximation I suspect) can be found here.