Distance between points.

[slacky]

Well, as I had nothing else to do I figured I could give a short "tutor" about measuring the distance between points, and how different implementations works. It's not a lot of reading and shit, mostly just straight forward.

 

I'm going to walk trough the few methods that are normal to use in different context's.

 

 

=================================================

 

 

Euclidean distance:

This is the `line of sight` version of distance, which uses Pythagorean theorem. Stretch out your arm, and turn 360 degrees, no matter direction, you always reach `so far`. Euclidean distance will always return a floating-point value due to a call to square-root.

 

Math formula: dist(q,p) = sqrt((px-qx)^2 + (py-qy)^2)

Pascal implementation:

function Euclidean(pt1,pt2:TPoint): Double;
begin
 Result := Sqrt(Sqr(pt1.x - pt2.x) + Sqr(pt1.y - pt2.y));
end;

 

Thoughts:

It's a bit slow for performance applications, mostly due to complecities of computing square root. This can be be avoided to a degree with Squared Euclidean distance. Take for example if your just computing difference between two Euclidean distances, and it's just too slow with Sqrt, then you can do this without any losses:

function SqEuclidean(pt1,pt2:TPoint): Double;
begin
 Result := Sqr(pt1.x - pt2.x) + Sqr(pt1.y - pt2.y);
end;

Now the resulting number will differ as we are not calculating the square root, but it's a faster algorithm for comparing, which is almost always the case.

 

Edit: Replaced Power(.., 2) with Sqr():

Sqr(pt1.x - pt2.x) is the same as Power((pt1.x - pt2.x), 2), but in compiled code Sqr(x) translates to the same as x*x, a IMUL or FMUL instruction, which is faster then whatever long asm code Power translates to.

 

To use Squared Euclidean as a distance test, it's needed to square the radius on the other side of the comparison-operator (<,=,>), example:

function InRadius(pt1,pt2:TPoint; Distance:Extended): Double;
begin
 Result := Sqr(pt1.x - pt2.x) + Sqr(pt1.y - pt2.y) <= Sqr(Distance)
end;

 

 

 

=================================================

 

 

City Block

.. or as some might know it as: Manhattan distance. This is much more friendly to performance. Now think about the pixels on the screen, you can see that it's IMPOSSIBLE to draw a straight 45 degree line, there will be a gap between each point/pixel, it's like walking in the City, you cant drive over the buildings, you need to drive around. This algorithm walks around each pixel/building (unlike Euclidean, which flies over am in a straight line).

 

Math formula: dist(q,p) = |px - qx| + |py - qy|

Pascal implementation:

function Manhattan(pt1,pt2:TPoint): Double;
begin
 Result := abs(pt1.x - pt2.x) + abs(pt1.y - pt2.y);
end;

 

Thoughts:

As it's a different algorithm, its uses are not always the same as Euclidean-distance. The result area of a distance of EG. `8` can be visualized as a tilted square at 45 degrees, with far fewer points (or pixels if you like) within the same distance compared to Euclidean, and Chebyshev (see next).

 

 

 

=================================================

 

 

Chebyshev distance

This is one I find my self using very often. It's a quick way to measure distance, it's also the simplest to understand by just looking at it. This time you can imagine a chessboard (assuming you know the game), the King can walk one step in any direction, including one step at 45 degrees: That is Chebyshev distance = 1.

 

Math formula: dist(q,p) = max(|px - qx|, |py - qy|)

Pascal implementation:

function Chebyshev(pt1,pt2:TPoint): Double;
begin
 Result := max(abs(pt1.x - pt2.x), abs(pt1.y - pt2.y));
end;

 

Thoughts:

It's similar to Manhattan distance. It also results in a square, but you can think of it as aligned with the horiz. and vertical axes. The amount of points within an area of the distance `8` contains many more points than ether of the other methods.

 

 

 

=================================================

 

 

Now that's those... But I bet you can't yet visualize the result, so I will give you this image just to demonstrate the result after using each algorithm to draw each there area/block given a distance of 5:

This picture also shows you that the distance in vertical and horizontal directions are the same no matter algorithm.

 

 

PS: I can only hope that the pascal examples work, haven't touched pascal in quite some time, and I'm not able to test it now... This is also the result of me not having anything better to do.

Edited July 9, 2016 by slacky

[shadowrecon]

Very nice! Ive used many functions that rely points for many different things and never quite understood some of it, but this has cleared up a few randoms things! +Like!

[FHannes]

Neither Manhatten or Chebyshev distances are very accurate though, they're more useful in heuristic algorithms than any application where you actually require a distance.

[slacky]

@Freddy, whether they are accurate or not depends on the usage. Also "accurate" is a misleading word in this case, as they are 100% accurate, they're just other algorithms which acts differently, and in many cases that might be the result you are after.

 

"they're more useful in heuristic algorithms"

- In case they are there to replace Euclidean distance; and do a job not fit for am, then yes, but that's not often the case, and squared euclidean is better fit then.

Edited November 12, 2013 by slacky
Cuz I can.

[Janilabo]

This is pretty cool topic, slacky! Nice job man, nice job.