Find a vector in a list
Author
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
Find based on what criteria? What kind of list? What programming language? How is your 3D vector defined?
Author
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.
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.
Author
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.
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.
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.
Author
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.
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
SporadicFire
Author
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]
And thank you SiCrane for asking the right questions and for that Space Pirate Amazon Ninja Catgirls link in your journal. [grin]
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.
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.
This topic is closed to new replies.
Advertisement
Popular Topics
Advertisement