//! Nature of Code, Example 5.13: QuadTree. The points under the pointer's //! square are found through the tree; drag to add points. const std = @import("std"); const sk = @import("sketch"); const vec = sk.math; pub const name = "quadtree"; pub const width = 640; pub const height = 360; /// Points a node holds before it splits in four. const capacity = 8; /// A rect by its centre and half-sizes, as the book has it. const Box = struct { x: f32, y: f32, w: f32, h: f32, fn contains(b: Box, p: vec.Vec) bool { return p[0] >= b.x - b.w and p[0] < b.x + b.w and p[1] >= b.y - b.h and p[1] < b.y + b.h; } fn intersects(b: Box, r: Box) bool { return !(r.x - r.w > b.x + b.w or r.x + r.w < b.x - b.w or r.y - r.h > b.y + b.h or r.y + r.h < b.y - b.h); } fn rect(b: Box) vec.Rect { return .{ .x = b.x - b.w, .y = b.y - b.h, .w = b.w * 2, .h = b.h * 2 }; } }; /// The tree is derived from the points: `draw` builds it every frame in /// scratch memory (a few thousand inserts), so State holds only the /// points, and a seek or a replay needs nothing else. Nodes refer to /// their children by index, not by pointer. const QuadTree = struct { nodes: std.ArrayList(Node) = .empty, const Node = struct { boundary: Box, points: sk.List(vec.Vec, capacity) = .{}, /// The first of four children (ne, nw, se, sw), or 0 for none. children: u32 = 0, }; fn init(gpa: std.mem.Allocator, boundary: Box) !QuadTree { var t: QuadTree = .{}; try t.nodes.append(gpa, .{ .boundary = boundary }); return t; } fn insert(t: *QuadTree, gpa: std.mem.Allocator, index: u32, p: vec.Vec) !bool { const node = &t.nodes.items[index]; if (!node.boundary.contains(p)) return false; if (node.points.appendBounded(p)) |_| return true else |_| {} if (node.children == 0) try t.subdivide(gpa, index); const first = t.nodes.items[index].children; for (first..first + 4) |child| if (try t.insert(gpa, @intCast(child), p)) return true; return false; } fn subdivide(t: *QuadTree, gpa: std.mem.Allocator, index: u32) !void { const b = t.nodes.items[index].boundary; const w = b.w / 2; const h = b.h / 2; t.nodes.items[index].children = @intCast(t.nodes.items.len); for ([_][2]f32{ .{ 1, -1 }, .{ -1, -1 }, .{ 1, 1 }, .{ -1, 1 } }) |d| { try t.nodes.append(gpa, .{ .boundary = .{ .x = b.x + d[0] * w, .y = b.y + d[1] * h, .w = w, .h = h } }); } } fn query(t: *const QuadTree, gpa: std.mem.Allocator, index: u32, range: Box, found: *std.ArrayList(vec.Vec)) !void { const node = t.nodes.items[index]; if (!node.boundary.intersects(range)) return; for (node.points.constSlice()) |p| if (range.contains(p)) try found.append(gpa, p); if (node.children != 0) for (node.children..node.children + 4) |child| try t.query(gpa, @intCast(child), range, found); } }; pub const State = struct { rng: std.Random.Xoshiro256 = .init(13), /// Processing's list grows without bound; State needs a number. points: sk.List(vec.Vec, 4096) = .{}, }; /// setup(): 2000 points, normally distributed around the centre. (The /// book centres y on width / 2 too, which puts the cloud at the bottom /// edge; here it is height / 2.) pub fn init(s: *State) void { const rng = s.rng.random(); for (0..2000) |_| { const p: vec.Vec = .{ rng.floatNorm(f32) * width / 8 + width / 2, rng.floatNorm(f32) * width / 8 + height / 2 }; s.points.appendBounded(p) catch break; } } /// Dragging sprinkles a point a step near the pointer (the book's video /// version). pub fn update(s: *State, in: *const sk.Input) void { if (!in.mouseHeld(.left)) return; const rng = s.rng.random(); const p: vec.Vec = .{ in.mouse_x + vec.uniform(rng, -5, 5), in.mouse_y + vec.uniform(rng, -5, 5) }; s.points.appendBounded(p) catch {}; } const range_pen: sk.draw.Pen = .{ .fill = sk.Color.hex(0xff3232).alpha(50), .stroke = .hex(0xff3232), .width = 2 }; pub fn draw(s: *const State, f: *sk.Frame) void { f.clear(sk.Color.white); build(s, f) catch f.host.log("out of scratch memory: tree dropped"); } fn build(s: *const State, f: *sk.Frame) !void { const gpa = f.scratch; var tree: QuadTree = try .init(gpa, .{ .x = width / 2, .y = height / 2, .w = width, .h = height }); for (s.points.constSlice()) |p| _ = try tree.insert(gpa, 0, p); // Every node's outline and every point, black, in one shape: show(). var black: sk.draw.Tessellation = .empty; for (tree.nodes.items) |node| { try black.strokeRect(gpa, node.boundary.rect(), 1, .identity); for (node.points.constSlice()) |p| try black.fillRect(gpa, .{ .x = p[0] - 0.5, .y = p[1] - 0.5, .w = 1, .h = 1 }, .identity); } f.shape(&black, .black); const mouse: vec.Vec = .{ f.in.mouse_x, f.in.mouse_y }; if (mouse[0] >= width or mouse[1] >= height) return; const range: Box = .{ .x = mouse[0], .y = mouse[1], .w = 50, .h = 50 }; sk.draw.rect(f, range.rect(), range_pen); var found: std.ArrayList(vec.Vec) = .empty; try tree.query(gpa, 0, range, &found); var dots: sk.draw.Tessellation = .empty; for (found.items) |p| try dots.fillCircle(gpa, p, 1.5, .identity); f.shape(&dots, .gray(50)); }