2

I'm trying to find a spatial index structure suitable for a particular problem : using a union-find data structure, I want to connect\associate points that are within a certain range of each other. I have a lot of points and I'm trying to optimize an existing solution by using a better spatial index.

Right now, I'm using a simple 2D grid indexing each square of width [threshold distance] of my point map, and I look for potential unions by searching for points in adjacent squares in the grid.

Then I compute the squared Euclidean distance to the adjacent cells combinations, which I compare to my squared threshold, and I use the union-find structure (optimized using path compression and etc.) to build groups of points.

Here is some illustration of the method. The single black points actually represent the set of points that belong to a cell of the grid, and the outgoing colored arrows represent the actual distance comparisons with the outside points.

Simple grid index

(I'm also checking for potential connected points that belong to the same cells).

By using this pattern I make sure I'm not doing any distance comparison twice by using a proper "neighbor cell" pattern that doesn't overlap with already tested stuff when I iterate over the grid cells.

Issue is : this approach is not even close to being fast enough, and I'm trying to replace the "spatial grid index" method with something that could maybe be faster.

I've looked into quadtrees as a suitable spatial index for this problem, but I don't think it is suitable to solve it (I don't see any way of performing repeated "neighbours" checks for a particular cell more effectively using a quadtree), but maybe I'm wrong on that.

Therefore, I'm looking for a better algorithm\data structure to effectively index my points and query them for proximity.

Thanks in advance.

Improve this question
5
  • What do you mean by " cluster points that are within a certain range of each other"? Do you mean Density based Clustering? Commented Apr 3, 2019 at 14:17
  • Alright, I'm going to correct this straight away in the original post : I just mean that if two points are within range of each other, they should be connected/ Commented Apr 3, 2019 at 14:21
  • To answer your question directly : it's not DBScan because I'm not really building any cluster. I've removed the word "cluster" in the original post, my problem is actually simpler than that Commented Apr 3, 2019 at 14:23
  • So you want to build a graph (thats what I read when you say connect two points), where two points are neighbors when their distance is below a given range? Or do you want the pairs of points that are within range? Commented Apr 3, 2019 at 14:25
  • Yes, I want to build a graph where two points are neighbors when their distance is below a given range Commented Apr 3, 2019 at 14:38

2 Answers 2

Reset to default
3

I have some comments:

1) I think your problem is equivalent to a "spatial join". A spatial join takes two sets of geometries, for example a set R of rectangles and a set P of points and finds for every rectangle all points in that rectangle. In Your case, R would be the rectangles (edge length = 2 * max distance) around each point and P the set of your points. Searching for spatial join may give you some useful references.

2) You may want to have a look at space filling curves. Space filling curves create a linear order for a set of spatial entities (points) with the property that points that a close in the linear ordering are usually also close in space (and vice versa). This may be useful when developing an algorithm.

3) Have look at OpenVDB. OpenVDB has a spatial index structure that is highly optimized to traverse 'voxel'-cells and their neighbors.

4) Have a look at the PH-Tree (disclaimer: this is my own project). The PH-Tree is a somewhat like a quadtree but uses low level bit operations to optimize navigation. It is also Z-ordered/Morten-ordered (see space filling curves above). You can create a window-query for each point which returns all points within that rectangle. To my knowledge, the PH-Tree is the fastest index structure for this kind of operation, especially if you typically have only 9 points in a rectangle. If you are interested in the code, the V13 implementation is probably the fastest, however the V16 should be much easier to understand and modify. I tried on my rather old desktop machine, using about 1,000,000 points I can do about 200,000 window queries per second, so it should take about 5 second to find all neighbors for every point.

If you are using Java, my spatial index collection may also be useful.

Improve this answer
Sign up to request clarification or add additional context in comments.

1 Comment

Awesome, exactly what I was looking for. Thanks
1

A standard approach to this is the "sweep and prune" algorithm. Sort all the points by X coordinate, then iterate through them. As you do, maintain the lowest index of the point which is within the threshold distance (in X) of the current point. The points within that range are candidates for merging. You then do the same thing sorting by Y. Then you only need to check the Euclidean distance for those pairs which showed up in both the X and Y scans.

Note that with your current union-find approach, you can end up unioning points which are quite far from each other, if there are a bunch of nearby points "bridging" them. So your basic approach -- of unioning groups of points based on proximity -- can induce an arbitrary amount of distance error, not just the threshold distance.

Improve this answer

Comments

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.