Archived

This topic is now archived and is closed to further replies.

DevLiquidKnight

Distance forumla without square roots?

Recommended Posts

Guest Anonymous Poster
Don''t apply square root unless you absolutely need the actual distance. For comparisons just use the squared value.

Share this post


Link to post
Share on other sites
AFAIK, you can''t evaluate the distance without the square root. However, there are many tricks to avoid square root operations:
- When comparing distances, compare the squared distances to avoid sqrt altogether
- Try to keep your vector normalized. For example, the cross product of two normalized vectors is a normalized vector, so it does not need to be normalized again
- You can use "Manhattan distance" to roughly approximate the distance between two points. Make a Google search; it''s a simple concept
- You could also expand the sqrt yourself using a Taylor series, and use only the first terms to get a decent approximation
- Remember that premature optimization is the root of all evil. Nowadays, square roots are not that expensive (IIRC, some processors have a dedicated sqrt instruction). Always profile your code.

HTH,

Cédric

Share this post


Link to post
Share on other sites
Being dumb/factious, but if you switch metric spaces you could have any distance function you wanted :-). Ok, that was a dumb joke, I''ll stop now :-)....
Jesse...

Share this post


Link to post
Share on other sites
Guest Anonymous Poster
"- Try to keep your vector normalized. For example, the cross product of two normalized vectors is a normalized vector, so it does not need to be normalized again"

This is true for perpendicular unit vectors.

Share this post


Link to post
Share on other sites
Right, sorry. Bad Cedric.

Anyway, what''s with all the sqrt threads this week? Stupid search function... Can''t blame the newbies anymore...

Cédric

Share this post


Link to post
Share on other sites
quote:
Original post by laeuchli
Being dumb/factious, but if you switch metric spaces you could have any distance function you wanted :-). Ok, that was a dumb joke, I''ll stop now :-)....
Jesse...



I do all my distance calculations in N


Documents [ GDNet | MSDN | STL | OpenGL | Formats | RTFM | Asking Smart Questions ]
C++ Stuff [ MinGW | Loki | SDL | Boost. | STLport | FLTK | ACCU Recommended Books ]

Share this post


Link to post
Share on other sites
Out of curiosity, Fruny, what is N-shmock?

How do you do those shmock-infinity things anyway? You always have a nice looking summation symbol, while we, lowly earthlings, have to use ASCII art. Unfair!

¦²

I can use charmap, but it's really long to find the symbol.

C¨¦dric

EDIT: No, apparently, using charmap only messes up my post

Σ

Success! Ty, OrangyTang
[edited by - cedricl on October 19, 2002 12:00:12 PM]

[edited by - cedricl on October 19, 2002 2:04:27 PM]

[edited by - cedricl on October 19, 2002 2:04:45 PM]

[edited by - cedricl on October 19, 2002 2:05:00 PM]

[edited by - cedricl on October 19, 2002 2:05:46 PM]

[edited by - cedricl on October 19, 2002 2:06:16 PM]

Share this post


Link to post
Share on other sites
Surely you could convert the manhatten distance to the distance via trig? Although that would add the use of sine/cosine ∴ may not be any faster..

√ does seem to be a popular topic recently.. Oh, and Σ is html code & # 9 3 1 ;

Share this post


Link to post
Share on other sites
quote:
Original post by cedricl
Out of curiosity, Fruny, what is N-shmock?



As a general rule :
||x||m; = ( Σk=0..n |xk|m )1/m

||x|| = maxk=0..n |xk|

quote:

How do you do those shmock-infinity things anyway?



Standard HTML character codes : http://www.w3.org/TR/REC-html40/sgml/entities.html.

& = &
∞ = ∞
Σ = Σ

And so on.

quote:
You always have a nice looking summation symbol, while we, lowly earthlings, have to use ASCII art. Unfair!


Take me to your leader. Resistance is futile, you will use ISO C++.

Documents [ GDNet | MSDN | STL | OpenGL | Formats | RTFM | Asking Smart Questions ]
C++ Stuff [ MinGW | Loki | SDL | Boost. | STLport | FLTK | ACCU Recommended Books ]


[edited by - Fruny on October 19, 2002 3:39:08 PM]

Share this post


Link to post
Share on other sites