euclidean distance

In mathematics the Euclidean distance or Euclidean metric is the "ordinary" distance between the two points that one would measure with a ruler, which can be proven by repeated application of the Pythagorean theorem. By using this formula as distance, Euclidean space becomes a metric space (even a Hilbert space).

Definition

The Euclidean distance for two points x = (x₁,...,x_n) and y = (y₁,...,y_n) in Euclidean n-space is defined as

d(x,y):=\sqrt{(x_1-y_1)^2 + (x_2-y_2)^2 + \cdots + (x_n-y_n)^2} = \sqrt{\sum_{i=1}^n (x_i-y_i)^2}

Two-dimensional distance

For two 2D points P=px,py and Q=qx,qy, the distance is computed as

\sqrt{(px-qx)^2 + (py-qy)^2}

Approximation

A fast approximation of 2D distance based on an octagonal boundary can be computed as follows. Let dx = |px-qx| (absolute value) and dy = |py-qy|. If dy≥dx, approximated distance is 0.41dx+0.941246dy. (If dy<dx, swap these values.) The difference from the exact distance is between -6% and +3%; more than 85% of all possible differences are between -3% to +3%.

The following Maple code implements this approximation and produces the plot on the right, with a true circle in black and the octagonal approximate boundary in red:

 fasthypot :=    unapply(piecewise(abs(dx)>abs(dy),                      abs(dx)*0.941246+abs(dy)*0.41,                     abs(dy)*0.941246+abs(dx)*0.41),           dx, dy): 
 hypot := unapply(sqrt(x^2+y^2), x, y): plotsdisplay(    plotsimplicitplot(fasthypot(x,y) > 1,                        x=-1.1..1.1,                        y=-1.1..1.1,                       numpoints=4000),   plottoolscircle(0,0, 1),   scaling=constrained,thickness=2 
 );

Other approximations exist as well. They generally try to avoid the square root, which is an expensive operation in terms of processing time, and provide various error:speed ratio. Using the above notation, dx + dy - 2×min(dx,dy) yields error in interval 0% to 12%. (Attributed to Alan Paeth.)

Three-dimensional distance

For two 3D points P=px,py,pz and Q=qx,qy,qz, the distance is computed as

\sqrt{(px-qx)^2 + (py-qy)^2 + (pz-qz)^2}