spatial-grid.mjs
66 lines · archify/renderers/shared/spatial-grid.mjs at a406594
1/** Uniform spatial grid for "which items can this box reach" queries (#8). */
3// A cell box wider than this is not worth walking: the query returns every
4// inserted item instead, which stays a superset of what the box reaches.
5const DEFAULT_MAX_CELLS = 4096;
7export function createSpatialGrid(cellSize, { maxCells = DEFAULT_MAX_CELLS } = {}) {
8 const buckets = new Map();
9 const items = [];
10 // Items whose own box cannot be walked are candidates for every query.
11 const overflow = [];
12 const keyOf = (x, y) => x + ':' + y;
13 const rangeOf = (box) => ({
14 x0: Math.floor(box.minX / cellSize), x1: Math.floor(box.maxX / cellSize),
15 y0: Math.floor(box.minY / cellSize), y1: Math.floor(box.maxY / cellSize),
16 });
17 // Finite coordinates can still land outside the safe-integer range, where
18 // incrementing an index no longer advances it; and a legal coordinate can
19 // name more cells than the grid is worth. Both cases stay out of the buckets
20 // and are answered by the item list, so they never hang or allocate.
21 const walkable = (range) => Number.isSafeInteger(range.x0) && Number.isSafeInteger(range.x1)
22 && Number.isSafeInteger(range.y0) && Number.isSafeInteger(range.y1)
23 && (range.x1 - range.x0 + 1) * (range.y1 - range.y0 + 1) <= maxCells;
25 return {
26 insert(box, item) {
27 items.push(item);
28 const range = rangeOf(box);
29 if (!walkable(range)) {
30 overflow.push(item);
31 return;
32 }
33 for (let x = range.x0; x <= range.x1; x += 1) {
34 for (let y = range.y0; y <= range.y1; y += 1) {
35 const key = keyOf(x, y);
36 let bucket = buckets.get(key);
37 if (!bucket) { bucket = []; buckets.set(key, bucket); }
38 bucket.push(item);
39 }
40 }
41 },
42 query(box) {
43 const range = rangeOf(box);
44 if (!walkable(range)) return items.slice();
45 const seen = new Set();
46 const found = [];
47 for (let x = range.x0; x <= range.x1; x += 1) {
48 for (let y = range.y0; y <= range.y1; y += 1) {
49 const bucket = buckets.get(keyOf(x, y));
50 if (!bucket) continue;
51 for (const item of bucket) {
52 if (seen.has(item)) continue;
53 seen.add(item);
54 found.push(item);
55 }
56 }
57 }
58 for (const item of overflow) {
59 if (seen.has(item)) continue;
60 seen.add(item);
61 found.push(item);
62 }
63 return found;
64 },
65 };
66}