Using QuadTree2D for finding neighbors

vvvv beta question
1

I have a 2D swarm of 3000 particles and I want to connect them with a range threshold.

I read that that the best way to go is to use spatial indexing / QuadTree, instead of comparing every point with all other points of the spread.

But I have no clue how to use this node. Can someone provide an example on how to use this to find the nearest neighbors of one particle in a swarm/random spread?

2

boubles-proximity-dynamic

3

thanks mrboni.

I tried to rebuild joreg’s connectAll contribution and hoped to make it a bit faster with this… but unfortunately there are no speed gains at all :)

I still want to triple the particle count, any idea how to speed it up?

wrotzlaw_connectAll.zip (16.4 kB)

4

gpu… no text …

5

the vl version of connectall is ~3 times faster
you can find it with explenation in the alpha forum

6

Problem is, connect all is not a linear algorithm, so 3 times faster in vl doesn’t mean that you can triple particle count.

So if we take the 3000 elements as example, you need 4498500 iterations.
Now if you triple the element count (eg: 9000), suddenly this becomes : 40495500

So that means if you consider using VL and being 3 times faster originally, tripling the amount of elements will still be approx 3 times slower.

(As a side note, using VL and achieving same speed as other method turns is approx 5190 elements in this case).

So we still need better data structures ;)

Using quadtree node as such is not so useful, since it doesn’t provide some of the vital information to perform a correct lookup (hierarchy), and anyway you pretty much need to perform traversal, which will be recursive, not ideal (here read: total pain) by patching.

So easiest way is to write one plugin that builds your dataset (and outputs the spatial grid as a node type), and a second plugin to lookup in that grid.

Note that you have two choices to build your structure, as per selecting the original root quad dimensions:

  • Static size : You set initial corners yourself as a fixed value. Please note that some elements might not make it into the grid at all (outside boundaries), or you can have a really large initial depth (particles are tighly packed together).
  • Adaptive : You compute bounding square from your particle dataset (n iterations, so it’s fast), and use that as your initial root square (scale it up a little tad to avoid rounding error).

Code to build the quadtree in vvvv-sdk github, it’s an old plugin done (by me) a long time ago, so pretty sure it can be decently optimized (can probably be modified to output the grid as a node object in few lines of code as well).

Now you need to perform lookup in the grid, that part is not implemented in the plugin, but is really trivial, pseudo code follows:

1/ Get your particle position
2/ Start from the root of the quad tree, mark it as current quad

3/

  • If current quad is a leaf:
    <- For each particle in this quad, do a distance check and append if necessary
  • If current quad is a container (eg : has 4 children)
    <-Do a circle quad intersection between quad rectangle and a circle that represents particle position/radius
    <- If you have intersection/containment, for each 4 sub quads, recursively go back to 3
    <- Else you can safely ignore any particle in that quad and all subquads.

As an important note, depending on your lookup radius (worst case being : it covers all the dataset), then doing a static lookup is still much faster, so up to you to balance that (it’s also easy, create a circle with center = center of your root square, radius = lookup. Then check if your root quad is fully contained within the circle).

Hope that helps

7

Ok thx for the detailed answer vux, I’ll give it a try :)