 |
|
|
Scene.org is hosted and supported by:
|
|
|
Scene.org is sponsored by:
|
|
|
|
|
 |
forum - #coders |
|
 | | Topic: | algorithm/datastructure needed | | | greets. i want to do a more generalised cells effect and i need something to give me the k nearest point from set to a query point (for example the 5th nearest). and fast. (faster than computing distance to all points and qsorting them). does anybody know of such a structure ?
thx | | |
| im not sure whether i hnow what u exactly mean but problems related to euclidean space can usually be very well simplified (less ticks for solving a problem) using hierarchical space (scene) reprasentation, e.g. a quad-tree (or forest) for 2D and octal-tree (or forest if needed) for 3D (and tree-cell subdivision driven by number of elements intersecting it), you could also do a combination of n-dim grid and these trees to make it even faster.. hope I hit your problem..
sorry for my creepy english:)
silique | | |
| | well, that's exactly was i was asking for. i know about bsp trees, kd trees, sphere tress, grid cells ect. not enough, that's why i'm asking. because i need to compute the k nearest neighbour for a lot of points, i need a _fast_ algorithm. i'd settle for log n :). | | |
| | if the query point is static or moves as first, you could simply have a binary search tree of max k-elements and when you move other points (all of them), you just do a search and throw-away within the tree, at the end the furthest of those k-elements will be the one you want, doesnt it seem atleast linear? hope im not totally wrong..:) is log_n possible on task like this? maybe after combination with some of the approaches using hierarchical structures, it could even get better than log_n, but surely not every time.. | | |
| Well - another method would simply to use the k'te element, which can be found in linear time. Though the algorithm takes a little getting used to. You can find it "Introduction to Algorithms", it's quite fast (it uses the median to partition the set), try it!
I don't see any other method, that I'm aware of, the sad thing ofcourse is that you'd have to find all distances to all points first (using euclidean distance), but that can be optimized if you are in a grid, since you know that points in the neighbouring gridcells will be much more likely than those further away.
Good luck,
Depth/sol. (depth@diku.dk), if you want more info... | | |
| I think you're probably stuck with a worst-case linear run-time but it seems like you should be able to do a lot better on average. So here's my idea for doing that.
Use a data structure that enables fast sphere queries, i.e. it will quickly find the set of all points within a given distance of the query point. This will likely be some kind of spatial partition or bounding volume hierarchy. Whatever you end up using, annotate each node in the structure by the number of points belonging to the node and its children.
By either preprocessing the point set or by making a qualified guess, you should be able to estimate the 'average distance' from a point to the k-th nearest neighbor.
Suppose we are now given a query point P and wish to find the k-th nearest neighbor. Let R denote the distance estimate (a function of k). We start by using the data structure to find an upper bound on the number of points within a distance R of the point P. This is done by finding out what nodes intersect the sphere of radius R centered at P and adding up all the point counts stored at each node. If this sum is larger than k, cut the query radius in half and try again. If the sum is less than k, double the query radius and try again.
Doing this, at some point you will end up overshooting k, then undershooting, or vice versa. For instance, if k = 5 in one pass you find an upper bound of 20 points within the query sphere, so you halve the query radius and try again. In the next try you find 3 points. So now you know that the 'right radius' is between the last two radii you tried. When this happens you need to actually start descending into the data structure to calculate exactly how many points are contained in the query sphere.
So to summarize: The idea is to perform binary search on the query sphere radius, using the point counts stored at nodes in the data structure to perform early-outs so you don't have to descend deeply into the data structure unless required.
Hope this helps! | | |
| | how about just making a low-resolution 3d-grid of the precalculated 5 nearest neighbours, and then select the closest ones from the 8 nodes nearest to the reference-point? | | |
|
|
|
