which data structure is appropriate to query "all points within distance d from point p"

Question

I have a 3D pointcloud and I'd like to efficiently query all points within distance d from an arbitrary point p (which is not necessarily part of the stored pointcloud)

The query would look something like

Pointcloud getAllPoints(Point p, float d);

what accelerationstructure would be appropriate for this? A range-tree seems to be appropriate only for querying rectangular volumes, not sphere volumes (of course I could query the boundingbox of the sphere and then sort out all vertices that have larger distance than d - but maybe there is a better way to do this??)

thanks!

according to Novelocrats suggestion, I try to define the desired functions of the structure:

SearchStructure Create(Set<Point> cloud) 
Set<Point> Query(SearchStructure S, Point p, float maxDistance)
SearchStructure Remove(Point p)
SearchStructure Insert(Point p)
SearchStructure Displace(Set<Point> displacement) //where each value describes an offsetVector to the currently present points

Usually, after n queries, the points get displaced and a few (not many!) insertions and deletions are made. the offset vectors are very small compared to the boundingbox of all points

Lidia

I think linear time creation might be asking too much, and could discourage people from providing good answers to the primary question. Are you constantly querying new pointclouds as well? If the new pointclouds are the result of changes in the existing one, modification of the structure might be cheaper. – Premise

"Query" has only one 'r' in it. I suggest fixing that for posterity. – Premise

Novelocrat: you are right - the new pointclouds are modifications of old ones, but pretty difficult ones (all the points move, each one in another direction, also, new points may be added that were not present before) so i thoght recreating the map each time will be the best. there will be aproximately n such queries for a map holding n points, before the pointcloud moves – Lidia

In keeping with the style of many algorithms texts, you may want to specify all of the desired operations in procedure form: SearchStructure Create(Set<Point> cloud) Set<Point> Query(SearchStructure S, Point p, float maxDistance) Note the non-member style; this makes it easier for someone to look at this description and get a very quick view of the problem you wish to solve. – Premise

You should specify how these structures will change as your program runs, rather than presuming that complete reconstruction will be the best approach. Computational geometers have done some really clever work. Considering one of their major historical funding sources (US Office of Naval Research) moving points would have been a topic of great interest. You should fold all of that information into the question. – Premise

I've added a bunch of links to my answer based on following the tags and seeing what else is similar. – Premise

Your Displace procedure takes a slightly odd argument - how will you match up the points in that with the existing points? – Premise

What is the typical size of your problem? How big is the original pointcloud? How many queries you plan to do? And how large is typically the "d" range in a query -- how large do you expect the result pointcloud to be? I am just trying to see what are really the dimensions you need to really scale, so see if it is worth describing the solution I have im mind... – Stunning

Answer 1

What you want is a structure that decomposes space so that particular regions can be found efficiently. A properly decomposed octree or kD-tree should allow you to do this well, as you would only 'open' the section of the tree containing your point p to look for points nearby. This should let you put a fairly low asymptotic bound on how many extra points you need to compare distance to (knowing that below some level of decomposition, all points are close enough). Unfortunately, I don't know the literature in this area well enough to give more detailed pointers. My encounter with these things is from the Barnes-Hut n-Body simulation algorithm.

Here's another question closely related to this one. And another. And a third, mentioning a data structure (Hilbert R-Trees) that I hadn't previously heard of.

Premise

i thoght about the octree but it seems to be not apropriate, since there meight be points that are in fact within range d, which lie in another section than p itself. so one would have to querry all sections that intersect with the sphere defined by p and d – Lidia

That's a good point. If there were some range-tree variant of octrees, then you'd be golden. – Premise

SciPy has a KDTree implementation, and it has a function called query_ball_point which does exactly this. – Quoin

Answer 2

VTK can help:

void vtkAbstractPointLocator::FindPointsWithinRadius (
double R, double x, double y, double z, vtkIdList * result
)

Subclasses of vtkAbstractPointLocator contain different data structures for search acceleration: regular buckets, kd-trees, and octrees.

Spirituality

Answer 3

I don't understand your API, you can round up all points in a PointCloud that lie inside an arbitrary sphere, but you also say that the point-clouds are stored? In that case shouldn't you get a list of PointClouds that is inside the given sphere, otherwise what is the point (excuse the pun) with having the PointClouds stored?

Instead of trying to define the API in advance, define it when you need it. There is no need to implement something that never will be used, let alone optimize a function that never will be called (unless it's for fun of course :)).

I think you should implement the bounding-box culling, followed by the more detailed sphere search as a first implementation. Perhaps it's not such a bottleneck as you think, and perhaps you will have far more serious bottlenecks to consider. It's always possible to optimize later when you actually see that you have everything working toghether as you have planned.

Comprise

Answer 4

Have a look at A Template for the Nearest Neighbor Problem (Larry Andrews at DDJ). Its only 2D, having a retrival complexity of O(log n), but it might be adopted for 3D as well.

Poss

Answer 5

A map with key equal to the distance and value being the Point itself would allow you to query for all Points less than a given distance or within a given range.

Americanist

the distance can't be key, since p is an arbitrary point (so p is an argument of the querry - i wasn't specific enough on that) – Lidia

Once you specify the point you populate the data structure. Change the point, repopulate. I think it still works. – Americanist

the point is a different one in each query. updating all the distances to point p would already need O(n) time – Lidia

Yes, I agree, but I don't see any way out of that. Do you? – Americanist

Answer 6

Well, it depends on what other uses you need for the data structure.

You can have a list of distances from point p to other points, ordered by distance, and map these lists to the points with a hashmap.

map:
p1 -> [{p2, d12}, {p4, d14}, {p3, d13}]
p2 -> ...
...

You can look up the point in the map, and iterate the list until the distance is higher than required.

Oringas