Uniform [[Lattice|Grid]] Spatial Partitioning is a form of [[Spatial Partitioning]] where objects are stored based on their location in some uniformly spaced grid. For a [[Set|set]] of objects $O$, find the [[Bounding Volume]] containing all objects. Divide this volume by some fixed size $\Delta x,\Delta y$. The maximum coordinates of this structure are: $\huge \begin{align} N &= \left\lceil \frac{1}{\Delta G} \oplus \pa{ \vec{\max} - \vec{\min} } \right\rceil \end{align}$ Given an object $o$ with [[Bounding Volume]] centered $\vec c$, we find the integer coordinates into our array with the following: $\huge \begin{align} \vec i = \floor{ \vec c \oplus \frac{1}{\Delta G}} \end{align}$ ### Update / Removal The naive aproach would be to delete everything and rebuild from scratch. The other option is to only update cells that overlaps with the object $o_{n-1}$ and $o_n$. You then update / remove those cells accordinly, you can also use some sort of [[Hash Map]] to make things easier. ### Pros and Cons - Simple and efficient/effective enough for many problems - May be difficult to clculate the size of the grid (picking value of $\Delta G$). - Sparsity? - Does not account for an unbounded world ### Cell Hashing - Use a [[Hashing Function]] with $(i,j,k)$, obtain a hash key - Use hash key to store objects into a hash table