🧊 Spatial Partitioning

Spatial partitioning is a technique for dividing a space into multiple sub-spaces, or partitions, to aid in the processing and management of data. It is used in a variety of applications, from collision detection to ray tracing. Here is a nice visualization of how it works.

A simple use case could be checking the distance between the player and nearby enemies in a game. If there are 100 enemies, you would have to check the distance between the player and all 100 enemies. If you divide the game world into 4 quadrants, you would only have to check the distance between the player and the enemies in the quadrant the player is in, resulting in a significant performance boost.

Here are some libraries to help you implement spatial partitioning in your projects.

2D

Quadtrees, R-trees, k-d trees on Wikipedia

• Stars
  NPM
  TS
  Maintained
• RBush

  2k

  2M/w

  
  2k2M/w
  
• KDBush

  600

  2M/w

  
  6002M/w
  
  2 years
• Flatbush

  1k

  32k/w

  
  1k32k/w
  
• quadtree-ts

  110

  1k/w

  
  1101k/w
  
• d3-quadtree

  222

  3M/w

  
  2223M/w
  
  3 years
• js-quadtree

  63

  200/w

  
  63200/w
  
  3 years

3D

Octrees on Wikipedia

• Stars
  NPM
  TS
  Maintained
• sparse-octree

  100

  5k/w

  

  – Requires Three.js as a peer dependency
  1005k/w
  
• vasturiano/d3-octree

  25

  30k/w

  
  2530k/w
  

BVH

Bounding Volume Hierarchy: Wikipedia

• Stars
  NPM
  TS
  Maintained
• three-mesh-bvh

  2k

  182k/w

  

  – With React Three Fiber, see Drei <Bvh>
  2k182k/w