Spatial indexes: grids, quadtrees and BVH
Find points in an area, nearest neighbours and colliding objects without checking everything: uniform grids, quadtrees, k-d trees, R-trees and bounding volume hierarchies, and when to use each.
Uniform grid (spatial hashing)
Dictionary keyed by the cell coordinates. A search looks only in the cells that overlap the search area.
var sensors = new (string Id, double X, double Y)[]{ ("S1", 12, 8), ("S2", 47, 15), ("S3", 51, 22), ("S4", 55, 18), ("S5", 90, 75), ("S6", 33, 61), ("S7", 58, 26), ("S8", 72, 40), ("S9", 5, 95), ("S10", 49, 30)}; const double Cell = 20;var grid = new Dictionary<(int, int), List<(string Id, double X, double Y)>>();foreach (var s in sensors){ var key = ((int)(s.X / Cell), (int)(s.Y / Cell)); if (!grid.TryGetValue(key, out var list)) grid[key] = list = new(); list.Add(s);} var (x1, y1, x2, y2) = (40.0, 10.0, 60.0, 28.0); // the search zonevar found = new List<string>();int checkedCount = 0;for (int cx = (int)(x1 / Cell); cx <= (int)(x2 / Cell); cx++) for (int cy = (int)(y1 / Cell); cy <= (int)(y2 / Cell); cy++) if (grid.TryGetValue((cx, cy), out var list)) foreach (var s in list) { checkedCount++; if (s.X >= x1 && s.X <= x2 && s.Y >= y1 && s.Y <= y2) found.Add(s.Id); }Console.WriteLine($"Found {string.Join(", ", found)}");Console.WriteLine($"Checked {checkedCount} of {sensors.Length}");Found S2, S4, S3, S7 Checked 5 of 10
Quadtree: adapt to the data
var sensors = new (string Id, double X, double Y)[]{ ("S1", 12, 8), ("S2", 47, 15), ("S3", 51, 22), ("S4", 55, 18), ("S5", 90, 75), ("S6", 33, 61), ("S7", 58, 26), ("S8", 72, 40), ("S9", 5, 95), ("S10", 49, 30)};var root = new QuadTree(0, 0, 100);foreach (var s in sensors) root.Insert(s.Id, s.X, s.Y); var found = new List<string>();int visited = root.Query(40, 10, 60, 28, found);Console.WriteLine($"Found {string.Join(", ", found)}");Console.WriteLine($"Visited {visited} squares"); class QuadTree(double x, double y, double size){ const int Capacity = 2; readonly List<(string Id, double X, double Y)> points = new(); QuadTree[]? kids; public void Insert(string id, double px, double py) { if (kids != null) { Child(px, py).Insert(id, px, py); return; } points.Add((id, px, py)); if (points.Count > Capacity && size > 1) // too crowded: split into four { double h = size / 2; kids = [new(x, y, h), new(x + h, y, h), new(x, y + h, h), new(x + h, y + h, h)]; foreach (var p in points) Child(p.X, p.Y).Insert(p.Id, p.X, p.Y); points.Clear(); } } QuadTree Child(double px, double py) => kids![(px >= x + size / 2 ? 1 : 0) + (py >= y + size / 2 ? 2 : 0)]; public int Query(double x1, double y1, double x2, double y2, List<string> found) { if (x2 < x || x1 >= x + size || y2 < y || y1 >= y + size) return 0; // no overlap: skip it all int visited = 1; foreach (var p in points) if (p.X >= x1 && p.X <= x2 && p.Y >= y1 && p.Y <= y2) found.Add(p.Id); if (kids != null) foreach (var k in kids) visited += k.Query(x1, y1, x2, y2, found); return visited; }}Found S2, S3, S4, S7 Visited 7 squares
Nearest neighbour: k-d trees
Objects with size: R-trees and BVH
var crane = new Box(10, 10, 30, 40);var scaffold = new Box(25, 35, 50, 60);var hut = new Box(60, 0, 80, 20);Console.WriteLine(crane.Overlaps(scaffold));Console.WriteLine(crane.Overlaps(hut));Console.WriteLine(Box.Union(crane, scaffold)); record struct Box(double MinX, double MinY, double MaxX, double MaxY){ public bool Overlaps(Box o) => MinX <= o.MaxX && o.MinX <= MaxX && MinY <= o.MaxY && o.MinY <= MaxY; // overlap on both axes public static Box Union(Box a, Box b) => // the box around both new(Math.Min(a.MinX, b.MinX), Math.Min(a.MinY, b.MinY), Math.Max(a.MaxX, b.MaxX), Math.Max(a.MaxY, b.MaxY));}True
False
Box { MinX = 10, MinY = 10, MaxX = 50, MaxY = 60 }| Index | Good for | Watch out for |
|---|---|---|
Show a hint
j > i, and compare squared distances to avoid square roots.
Show the solution
const double R = 10;var pts = new (double X, double Y)[] { (1, 1), (4, 5), (12, 3), (25, 25), (27, 22), (40, 40), (9, 9), (45, 41) }; var grid = new Dictionary<(int, int), List<int>>();for (int i = 0; i < pts.Length; i++){ var key = ((int)Math.Floor(pts[i].X / R), (int)Math.Floor(pts[i].Y / R)); if (!grid.TryGetValue(key, out var list)) grid[key] = list = new(); list.Add(i);} int pairs = 0, checks = 0;for (int i = 0; i < pts.Length; i++){ int cx = (int)Math.Floor(pts[i].X / R), cy = (int)Math.Floor(pts[i].Y / R); for (int dx = -1; dx <= 1; dx++) for (int dy = -1; dy <= 1; dy++) if (grid.TryGetValue((cx + dx, cy + dy), out var list)) foreach (int j in list) if (j > i) // each pair once { checks++; double ex = pts[i].X - pts[j].X, ey = pts[i].Y - pts[j].Y; if (ex * ex + ey * ey < R * R) pairs++; }}Console.WriteLine($"{pairs} close pairs, {checks} checks, {pts.Length * (pts.Length - 1) / 2} pairs in total");6 close pairs, 8 checks, 28 pairs in total
Remember
Spatial indexes group objects by position so that whole regions can be skipped. A uniform grid is simplest and great for evenly spread objects; clusters defeat it. Quadtrees (octrees in 3D) subdivide only where data is dense; k-d trees answer nearest-neighbour queries. Objects with size go in bounding boxes; BVHs and R-trees are hierarchies of boxes for collisions, clash detection and databases.