The

**Euclidean distance**of two points

*x*= (

*x*

_{1},...,

*x*

_{n}) and

*y*= (

*y*

_{1},...,

*y*

_{n}) in Euclidean

*n*-space is computed as

Table of contents |

2 Three-dimensional distance |

## 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.41*dx*+0.941246*dy*.
(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%.

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