Skip to content
AITroveRead. Build. Understand.
Reading list
Make this comfortable

Spatial hash grids: move points between occupied cells

Last updated: 5 Oct 20269 min read
tutorial
IntermediateBy AITrove Editorial

A spatial hash grid maps a coordinate to a cell key, then stores the IDs in that cell. A second map stores each ID's current coordinates so a move can remove it from its previous cell before insertion into the new one. This example uses floor division, including for negative coordinates, and deletes an empty cell after its last point moves or leaves. A radius query enumerates cells touched by the bounding square and checks actual squared distance for every candidate. The cell lookup is a coarse filter. It cannot by itself establish that a point is inside a circle. IDs are unique, and upsert replaces the current position of an existing ID. Coordinates and radius use the same planar units; this is not a latitude-longitude distance calculator.

Operational case

Pump-47 starts at minus three, four; valve-19 moves from nine, five to one, six; sensor-61 stays at two, seven. A radius-four query around zero, five returns all three after the move. If the old valve cell retained its ID, a later query there could return a stale location or duplicate result. The implementation computes distance from the authoritative coordinate map rather than trusting which grid cell supplied a candidate. Queries that cross the zero axis still enumerate negative cell numbers correctly because floor division places minus one in the preceding cell rather than truncating it toward zero.

Working Python program

python
import math


class MovingDepotGrid:
    def __init__(self, cell_size):
        if cell_size <= 0:
            raise ValueError("cell size must be positive")
        self.cell_size = cell_size
        self.points = {}
        self.cells = {}

    def _cell(self, x, y):
        return math.floor(x / self.cell_size), math.floor(y / self.cell_size)

    def upsert(self, depot_id, x, y):
        destination = self._cell(x, y)
        if depot_id in self.points:
            previous = self._cell(*self.points[depot_id])
            if previous != destination:
                self.cells[previous].remove(depot_id)
                if not self.cells[previous]:
                    del self.cells[previous]
        self.points[depot_id] = (x, y)
        self.cells.setdefault(destination, set()).add(depot_id)

    def remove(self, depot_id):
        x, y = self.points.pop(depot_id)
        cell = self._cell(x, y)
        self.cells[cell].remove(depot_id)
        if not self.cells[cell]:
            del self.cells[cell]

    def within_radius(self, x, y, radius):
        if radius < 0:
            raise ValueError("radius cannot be negative")
        left, bottom = self._cell(x - radius, y - radius)
        right, top = self._cell(x + radius, y + radius)
        matches = []
        for cell_x in range(left, right + 1):
            for cell_y in range(bottom, top + 1):
                for depot_id in self.cells.get((cell_x, cell_y), ()):
                    depot_x, depot_y = self.points[depot_id]
                    if (depot_x - x) ** 2 + (depot_y - y) ** 2 <= radius ** 2:
                        matches.append(depot_id)
        return sorted(matches)


index = MovingDepotGrid(cell_size=8)
index.upsert("pump-47", -3, 4)
index.upsert("valve-19", 9, 5)
index.upsert("sensor-61", 2, 7)
index.upsert("valve-19", 1, 6)
print("near=", index.within_radius(0, 5, 4), "cells=", len(index.cells), sep="")

Output

Output
near=['pump-47', 'sensor-61', 'valve-19']cells=2

Time, space, and tradeoff

An upsert or removal uses expected O(1) hash-map and set work. A query touching C cells and inspecting K candidate points costs O(C + K + R log R) here, where R results are sorted before return. Memory is O(N + E) for N points and E occupied cells. A huge radius or a very small cell size can make C large even when most cells are empty; a hot cell can make K approach N. Hash operations are expected costs, not hard bounds. The index is mutable and single-process but does not support rectangle geometry, geographic projections, or concurrent move/query snapshots.

Common Mistakes

  • Do not keep an ID in its old cell after a move.
  • Do not truncate negative coordinates toward zero when choosing a cell.
  • Do not return every point from a touched cell without distance verification.
  • Do not describe a large-radius query as constant time.

Connected lessons

Compare its geometry and update costs with Point-region quadtrees: subdivide crowded cells, Bounding-volume hierarchies: prune box overlap searches, Morton ordering: decompose a grid window into code ranges, then run the spatial audit and contract quiz.

Vantage-point trees: nearest depots by a metric radius adds a distinct structure contract to compare.

data structures
hash-tables
Storage details