Question: Just to make sure you understand this example... why do the gray grid cells contain all particles within radius R of the red particle?
ericwang
If one particle is not located in surrounding cells, the line segment between this particle and the red one will cross one or more surrounding cells. As the cell size is R, the length of this line segment would be larger than R. So any particles out side the surrounding cells are not within radius R of the red one.
jezimmer
For a naive algorithm, it would suffice to just look at the 9 boxes shown here, but with a little effort it shouldn't be too hard to see if boxes in the corners are simply too far away (like the top right here), which cuts down your search space by just a little extra.
kayvonf
@ericwang. Yep!
BigFish
This reminds me of indexing method in multimedia database. We can use spatial filling curve to create index for all these particles and use them as the key in B-tree. Then we can do a range query in the B-tree to find all particles within radius R by cutting off those unrelated branches.
Question: Just to make sure you understand this example... why do the gray grid cells contain all particles within radius R of the red particle?
If one particle is not located in surrounding cells, the line segment between this particle and the red one will cross one or more surrounding cells. As the cell size is R, the length of this line segment would be larger than R. So any particles out side the surrounding cells are not within radius R of the red one.
For a naive algorithm, it would suffice to just look at the 9 boxes shown here, but with a little effort it shouldn't be too hard to see if boxes in the corners are simply too far away (like the top right here), which cuts down your search space by just a little extra.
@ericwang. Yep!
This reminds me of indexing method in multimedia database. We can use spatial filling curve to create index for all these particles and use them as the key in B-tree. Then we can do a range query in the B-tree to find all particles within radius R by cutting off those unrelated branches.