 |
|
|
|
|
|
| |
| |
|
|
|
|
| |
| |
|
|
Hi guys.
I'm guessing somebody here is likely to know the answer to this one...
I want a data structure that stores key/value pairs where the keys are
points in 3D space. In particular, I want to be able to *efficiently*
look up the N points nearest to any given location. (Hopefully it's also
fairly quick to add new points to the structure.)
The points don't have any particular arrangement. (They're certainly not
a regular grid - in that case, lookup would be quite simple.)
One algorithm I could use is to store a list of key/value pairs, and
sort the list by the distance between each key and the target point,
then read off the first few values in the list. This *works*, but it's
absurdly inefficient. (It's O(n log n) in the total number of entries.)
Does anybody know of something a little faster?
Post a reply to this message
|
|
| |
| |
|
|
|
|
| |
| |
|
|
Orchid XP v7 <voi### [at] dev null> wrote:
> I want a data structure that stores key/value pairs where the keys are
> points in 3D space. In particular, I want to be able to *efficiently*
> look up the N points nearest to any given location.
http://en.wikipedia.org/wiki/Nearest_neighbor_search
http://en.wikipedia.org/wiki/R-tree
http://en.wikipedia.org/wiki/Kd_tree
--
- Warp
Post a reply to this message
|
|
| |
| |
|
|
|
|
| |
| |
|
|
Orchid XP v7 wrote:
> Hi guys.
>
> I'm guessing somebody here is likely to know the answer to this one...
>
> I want a data structure that stores key/value pairs where the keys are
> points in 3D space. In particular, I want to be able to *efficiently*
> look up the N points nearest to any given location. (Hopefully it's also
> fairly quick to add new points to the structure.)
>
> The points don't have any particular arrangement. (They're certainly not
> a regular grid - in that case, lookup would be quite simple.)
>
> One algorithm I could use is to store a list of key/value pairs, and
> sort the list by the distance between each key and the target point,
> then read off the first few values in the list. This *works*, but it's
> absurdly inefficient. (It's O(n log n) in the total number of entries.)
> Does anybody know of something a little faster?
Something like a K-dimension or a P-R-Quad Tree? I like K-D trees
because they are just binary trees with a fancy insert and delete.The
basic idea if that the depth from the root of the tree determines which
of the dimension you organize that level by. Compare by X at root, Y at
the next depth, Z next, then back to X and so on.
Searching also gives you the option of radius searches, so you can get
all key/values withing Q distance of X,Y,Z.
An R-Tree might also do what you want, but I haven't programed one.
Post a reply to this message
|
|
| |
| |
|
|
|
|
| |
| |
|
|
Sabrina Kilian <"ykgp at vtSPAM.edu"> wrote:
> I like K-D trees
> because they are just binary trees with a fancy insert and delete.
Kd-trees are quite useful for many purposes. They are, for example,
sometimes used in real-time rendering because it can be used to speed
up certain operations. For example:
Assume that you have a very large amount of semi-transparent polygons
which you need to render. The problem with semi-transparent polygons is
that they must be rendered in back-to-front order. Rendering them in a
random order will result in an erroneous image.
Sorting the polygons to a back-to-front order with respect to the
current camera location at each frame is too inefficient because the
triangles would first need to be transformed according to the camera
parameters and then their distance to the camera would need to be
determined somehow (which is not always something unambiguous) and
then a O(nlogn) sorting algorithm would need to be applied.
However, this can be done much more efficiently. As a pre-processing
step all the triangles are stored in a Kd-tree. After that, each time
a new frame needs to be rendered, the Kd-tree can be relatively easily
traversed in an order which results in all the triangles being rendered
in a back-to-front order with respect to the location of the camera.
This traversal is O(n) regardless of the camera location, and it always
results in a perfect ordering of the triangles. No distances need to
be calculated and nothing needs to be sorted.
--
- Warp
Post a reply to this message
|
|
| |
| |
|
|
|
|
| |
| |
|
|
Warp wrote:
> http://en.wikipedia.org/wiki/R-tree
> http://en.wikipedia.org/wiki/Kd_tree
Both of these look potentially useful quite useful. (Certainly O(log n)
lookup sounds much more fun than O(n) lookup!) Both articles talk about
finding THE nearest point, but it looks easy to modify it to find
several nearby points.
It seems that in both cases, ensuring the tree is nicely balanced is
utterly critical to best performance. Since I'm going to be adding
points to the tree all the time, clearly I need to think carefully about
this part.
Anyway, I have some stuff to play with now... thanks.
Post a reply to this message
|
|
| |
| |
|
|
|
|
| |
| |
|
|
Orchid XP v7 nous apporta ses lumieres en ce 2007/11/03 18:20:
> Warp wrote:
>
>> http://en.wikipedia.org/wiki/R-tree
>> http://en.wikipedia.org/wiki/Kd_tree
>
> Both of these look potentially useful quite useful. (Certainly O(log n)
> lookup sounds much more fun than O(n) lookup!) Both articles talk about
> finding THE nearest point, but it looks easy to modify it to find
> several nearby points.
>
> It seems that in both cases, ensuring the tree is nicely balanced is
> utterly critical to best performance. Since I'm going to be adding
> points to the tree all the time, clearly I need to think carefully about
> this part.
>
> Anyway, I have some stuff to play with now... thanks.
A possible way to get a, more, balanced tree is to seed it with 3 dummy values.
One for the tree root, and 2 for the first branches, one to each "sides" of the
initial one. The first is set to the expected average value of the possible
points. The 2 next are chosen halfway between that value and the expected
extreme values.
Easier done when you know that all your samples will be contained within a given
domain, and what will be the more probable distribution.
--
Alain
-------------------------------------------------
Never frown, even when you are sad, because you never know who is falling in
love with your smile.
Post a reply to this message
|
|
| |
| |
|
|
|
|
| |
| |
|
|
Orchid XP v7 wrote:
> Hi guys.
>
> I'm guessing somebody here is likely to know the answer to this one...
>
> I want a data structure that stores key/value pairs where the keys are
> points in 3D space. In particular, I want to be able to *efficiently*
> look up the N points nearest to any given location. (Hopefully it's also
> fairly quick to add new points to the structure.)
>
> The points don't have any particular arrangement. (They're certainly not
> a regular grid - in that case, lookup would be quite simple.)
>
> One algorithm I could use is to store a list of key/value pairs, and
> sort the list by the distance between each key and the target point,
> then read off the first few values in the list. This *works*, but it's
> absurdly inefficient. (It's O(n log n) in the total number of entries.)
> Does anybody know of something a little faster?
If you want speed after the points are all read in, then build an MxN
array of indices to the list (M is the total number of points, N is the
number of desired neighbors). It's an O(M^2 * N) problem to build that
structure (although that can probably be reduced), but once the
structure is built, you get the maximum speed.
Regards,
John
Post a reply to this message
|
|
| |
| |
|
|
|
|
| |
|
|
