So let’s say you’ve got some particles in 2-dimensional space.

There they are. Now let’s say you want any two particles which are very close to each other to interact. You need to know which pairs are close enough. You could take all possible pairs of particles, calculate their distances, and compare those to the minimum distance ** d**. That’s fine if you have 10 particles, but if you have 5,000 that’s going to add up to over 12,000,000 pairs. That’s too many pairs.

That complexity can be alleviated if for each particle ** P** we can efficiently find a subset of all particles which includes all those within

**of**

`d`

**and which includes as few as possible which aren’t within**

`P`

**. Then we can calculate the distances from**

`d`

**to the few particles in this subset and determine which ones are actually within distance**

`P`

**.**

`d`

Enter: spatial hashing. I’ll show how `boost::unordered_multimap`

can be used to do this.

Continue reading