Talk:Euclidean distance

Is that formula for approximating the distance using only integers wrong? Surely if dx and dy are the same (eg, at a 45-degree angle) then dx + dy - 2×min(dx,dy) will always be 0, and the approximation will always be 100% error?

Yea, it was wrong and has been changed. StuRat 16:40, 21 September 2005 (UTC)

I think it is worth noting that the Euclidean metric used to be called Pythagorean metric. At least there should be a page title Pythagorean metric that redirects here. 127

Sure, go ahead and add it. StuRat 20:07, 21 October 2005 (UTC)

fast 2d calculation values

A fast approximation of 2D distance based on an octagonal boundary can be computed as follows. Let $dx=|p_{x}-q_{x}|$ (absolute value) and $dy=|p_{y}-q_{y}|$. If $dy>dx$, approximated distance is $0.41dx+0.941246dy$.

where do 0.41 and 0.941246 come from? --Abdull 12:59, 21 February 2006 (UTC)

Well. 0.41 sounds like an approximation of sqrt(2). I don't know where the other coefficient comes from or why it's necessary to have 6 decimal place accuracy (while 0.41 only has a two decimal place accuracy). StuRat 19:57, 21 February 2006 (UTC)

Those coefficients come from a certain optimal interpolation, which I have calculated some years ago. It goes like this: dy >= dx, therefore dy = a*dx (where a is greater or equal to 1). Distance d is then equal to dx * sqrt(1 + a^2). Now, when you plot the square-root expression for a>=1, it strongly resembles a plain straight line. And those mysterious coefficients are just the description of the optimal interpolation line (b = 0.41 + 0.94*a). Then, d =~ dx * (0.41 + 0.94*a). The last step is a realization that a is in fact dy/dx and performing an appropriate simplification. (One point is missing here, the criteria of interpolation optimality. Frankly, I have forgotten, what condition I have actually used: whether least area between the curve and line, or maximum distance minimization. I have to find the paper and recall it :-)). --BB 09:54, 22 February 2006 (UTC)