Talk:Euclidean distance

From Wikipedia, the free encyclopedia

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)

Where it says "The technique has been rediscovered numerous times throughout history, as it is a logical extension of the Pythagorean theorem.", are they talking about repeated use of the pythagorean theorem to prove the pythagorean theorem? The statement seems disjointed. 80.2.17.86 (talk) 23:15, 14 March 2008 (UTC)

Contents 1 fast 2d calculation values 2 Comparing against a distance 3 Two-dimensional distance 4 Approximations 5 Euclid

[edit] 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)

One more addition, IIRC, the optimality criterium comes from error-factor formula sqrt(1+a^2)/(0.41+0.941246*a). --BB

Some years ago I developed a similar distance approximation algorithm using three terms, instead of just 2, which is much more accurate, and because it uses power of 2 denominators for the coefficients can be implemented without using division hardware. The formula is: 1007/1024 max(|x|,|y|) + 441/1024 min(|x|,|y|) - if ( max(|x|.|y|)<16min(|x|,|y|), 40/1024 max(|x|,|y|), 0 ). Also it is possible to implement a distance approximation without using either multiplication or division when you have very limited hardware: ((( max << 8 ) + ( max << 3 ) - ( max << 4 ) - ( max << 1 ) + ( min << 7 ) - ( min << 5 ) + ( min << 3 ) - ( min << 1 )) >> 8 ). This is just like the 2 coefficient min max algorithm presented earlier, but with the coefficients 123/128 and 51/128. I have an article about it at http://web.oroboro.com:90/rafael/docserv.php/index/programming/article/distance --Rafael

Perhaps we need a whole new article on distance approximations. Can you give me an example of a place where min and max functions are available but multiplication and division are not ? StuRat 16:10, 18 May 2006 (UTC)

[edit] Comparing against a distance

If you want to know whether objects A and B are at distance c or less, you can compare ((Ax - Bx)^2 + (Ay - By)^2 + (Az - Bz)^2) with c^2, and similarly for other numbers of dimensions. This avoids the square root entirely. If c is a constant, then c^2 can be precomputed as well. -- Myria 06:18, 21 July 2006 (UTC)

True, but this is already implied by the section that talks about how distances can be compared while skipping the square root operation. StuRat 05:37, 29 July 2006 (UTC)

Where is that section? I think it was accidentally removed with the approximations, put it back. Comparing distances without using the square root is a simple but very important fact in software/hardware development since the square root is a very expensive operation. Raising the awareness of such a simple fact has a positive contribution to technology and thus humanity which nowadays suffers from slow, overbloated and resource-hungry software. Wikipedia is not only about abstract mathematical concepts.--PE (talk) 11:27, 14 May 2008 (UTC)

[edit] Two-dimensional distance

I corrected the formula for the distance in circular coordinates. --EarthJoker 12:25, 23 July 2007 (UTC)

[edit] Approximations

Why is the approximation section here? Euclidean metrics are very simple concepts, and I don't think you'd find anything about approximation in 99% of the textbooks that cover the topic. It seems like the audience for that material is different from the audience for the rest of the article. At the very least, there should be a reference here, or some explanation as to why it works.

Also, I moved the approximation sections to the end of the page because it seems important to at least see the 3D version before this is discussed. Triathematician (talk) 01:16, 20 December 2007 (UTC)

As you can see in the first section of this talk page, the approximation section looks like unsourced original research, so I guess that it can be safely removed altogether. Afaic, go ahead. DVdm (talk) 13:55, 20 December 2007 (UTC)

[edit] Euclid

Does this have anything to do with Euclid? If so, should it be mentioned or at least 'See also'ed? Bitwiseb (talk) 17:46, 4 April 2008 (UTC)