Jump to content
  • Advertisement
Sign in to follow this  
Alturis

Find squared length of path without using square root?

This topic is 553 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

I was looking to find out if anyone knows of an optimal method to find the squared distance of a path defined by a series of 3D points?

Given an arbitrary array of vectors, find the squared sum of the distance between each points and its previous point I mean.

To my knowledge in order to do this you have to sum up all the distances and then square the result. But was wondering if there was a tricky way to do this only using the squared distance between each of the points.

 

Share this post


Link to post
Share on other sites
Advertisement
You mean the length of the path squared? Unfortunately you can't avoid the square roots.

Share this post


Link to post
Share on other sites

You can't get the exact value of the squared sum of all the lengths just from the squared lengths, but you CAN get some nice bounds, if that helps.

 

For any a1, a2, ..., an >= 0, the lower bound

(a1 + a2 + ... + an)^2 >= a1^2 + a2^2 + ... + an^2

holds.

 

Furthermore, if you can guarantee that a1^2, a2^2, ..., an^2 are all greater than or equal to 1, then additionally the upper bound

(a1 + a2 + ... + an)^2 <= a1^2 + a2^2 + ... + an^2 + 2*a1^2*a2^2 + 2*a1^2*a3^2 + ... + 2*a1^2*an^2 + 2*a2^2*a3^2 + ...

also holds.

 

In case you have trouble following all those coefficients and exponents and stuff, the latter term (after the "+ an^2 + ") is

for i in [1,n]
  for j in [i+1,n]
    sum += 2 * ai^2 * aj^2

The good part about that upper bound condition is that you can easily make sure it holds by scaling the grid accordingly. It's an O(n^2) operation, but so is calculating the upper bound.

 

Hope that helps a bit!

Share this post


Link to post
Share on other sites
Sign in to follow this  

  • Advertisement
×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

We are the game development community.

Whether you are an indie, hobbyist, AAA developer, or just trying to learn, GameDev.net is the place for you to learn, share, and connect with the games industry. Learn more About Us or sign up!

Sign me up!