For two 2D points P=[px,py] and Q=[qx,qy], the distance is computed as
A fast approximation of 2D distance based on an octagonal boundary can be computed as follows. Let dx = pxqx (absolute value) and dy = pyqy. 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.)
For two 3D points P=[px,py,pz] and Q=[qx,qy,qz], the distance is computed as
Search Encyclopedia

Featured Article
