Jump to content
  • Advertisement
Sign in to follow this  
noaktree

Find a vector in a list

This topic is 4886 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

Hi everyone, What's the fastest way to find a 3d vector in a list of 3d vectors? The list can be sorted in any way. Thanks, Neil

Share this post


Link to post
Share on other sites
Advertisement
Find based on what criteria? What kind of list? What programming language? How is your 3D vector defined?

Share this post


Link to post
Share on other sites
Quote:
Find based on what criteria? What kind of list? What programming language? How is your 3D vector defined?
Find the vector closest to a given vector. Any kind of list would be fine. C++. And let's say we define the vector as a struct with three floats or perhaps an array of 3 floats.

Actually the vectors could be stored in any data structure really.

Share this post


Link to post
Share on other sites
Probably the easiest way would be to iterator through the list and take the dot product of each vector with the given vector. Then return the vector with the largest dot product.

Share this post


Link to post
Share on other sites
Quote:
Probably the easiest way would be to iterator through the list and take the dot product of each vector with the given vector. Then return the vector with the largest dot product.
Yes but then as the list grows so does the number of operations O(n) will not do.

If I could find a way to sort vectors into a binary sort tree or something similar. But then how do I compare the vectors? That is how do I say one vector is > or < another vector?

And besides the distance formula would work better than the dot product I think. Dot product returns the cos(angle) between the two vectors.

Share this post


Link to post
Share on other sites
Make a BSP tree with the points in it. The planes to use to split space can be computed from the points themselves. You can have one point per leaf (probably inefficient in terms of memory use) or you can have some constant number of points per leaf. Either way, it should be O(log(n)) to search. In the case where you have one point per leaf, the splitting plane can simply be the plane that is orthagonal to the line between two points and lies in between them.

To search, you have to recursively find which side of the tree the point you are searching for lies. Any vectors found on that side of the tree will be closer to your point than those found on the other side. Once you reach a leaf (and it contains more than one vector), you simply have to use linear search to find the closest vector.

edit: made first para clearer.

Share this post


Link to post
Share on other sites
The problem with the BSP method is that I would have to regenerate the tree everytime I added another vector, right? I may be adding new vectors quite often.

Share this post


Link to post
Share on other sites
Well, there's an alternative way. One could make the BSP tree as points are being inserted (rather than rebuilding it repeatedly). Basically, when you insert a point, you find the region of the BSP where the point belongs and put it in that region. If the region exceeds the maximum number of points, then you divide the region into two. However, an important caveat is that your points have to be evenly distributed in space, or you end up with a really unoptimized tree. Or, may be you could try and augment the BSP tree to be self balancing :)

SporadicFire

Share this post


Link to post
Share on other sites
Thanks SporadicFire I'll look into it as a possible solution.
And thank you SiCrane for asking the right questions and for that Space Pirate Amazon Ninja Catgirls link in your journal. [grin]

Share this post


Link to post
Share on other sites
I might suggest using a skip list. Basically, implement the list to include nodes with extra pointers so that you can iterate through the list more quickly.

The easiest explanation would be if you had a list of one-dimensional sorted vectors. You want to find out if your vector = suppose that the value is equal to 1,213 - is in the list, but you don't want to have to iterate all the way through the first possibly 1,200 elements. You could implement links for every hundred values, so you just skip to the twelfth hundred-value link, if its empty, you know there aren't any 1,200s so you can return false, otherwise, you just iterate through the much smaller space.

For 3D vectors, you would probably have to have a matrix of these pointers so that you could go to the 4th X-pointer and 5th Y-pointer to find something at (40.0, 50.0, 0.0) - I can't see you needing more than 2 dimensions worth unless you had a LOT of vectors within each coordinate separation.

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.

GameDev.net is your game development community. Create an account for your GameDev Portfolio and participate in the largest developer community in the games industry.

Sign me up!