The Ultimate Euclidean distance - American History Information Guide and Reference

(Redirected from Euclidean metric)

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).

Contents

1 Definition

2 Two-dimensional distance

2.1 Approximation

3 Three-dimensional distance

4 See also

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):
plots[display](
  plots[implicitplot](fasthypot(x,y) > 1, 
                      x=-1.1..1.1, 
                      y=-1.1..1.1,
                      numpoints=4000),
  plottools[circle]([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}$

Your American History Reference Guide! - Euclidean distance

Euclidean distance

Definition

Two-dimensional distance

Approximation

Three-dimensional distance

See also

Your American History Reference Guide!
- Euclidean distance