Euclidean distance
The Euclidean distance of two points x = (x1,...,xn) and y = (y1,...,yn) in Euclidean n-space is computed as
It 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).
Two-dimensional distance
For two 2D points P=[px,py] and Q=[qx,qy], the distance is computed as
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, aproximated 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 Waterloo 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
Referenced By
Ball (mathematics) | Closeness | Distance | Distance function | Euclid's postulates | Euclidean | Euclidean geometry | Euclidian | Fifth Postulate | Linear Algebra/Normed Vector Space | List of geometry topics | Magic (software) | Magnitude | Manhattan distance | Metric space | Metric spaces | Normed vector space | Open (topology) | Open ball | Open set | Open subset | Proximity | Pseudometric | Pseudometric space | Real tree | Rectifiable curve | Self-organizing map | Self organizing map | Similar | Similar (linear algebra) | Similarity (mathematics) | Taxicab geometry | Traveling salesman problem | Travelling salesman problem | Unit Circle
|
