diff options
| author | Gabriel Schneider <[email protected]> | 2026-11-16 21:28:20 -0300 |
|---|---|---|
| committer | Gabriel Schneider <[email protected]> | 2026-11-16 21:28:20 -0300 |
| commit | 6933f99ddb2d7103515d26838496309a807bba26 (patch) | |
| tree | 991c2fe7d4a57957222876e190fa4d16a0fb889c /examples/noc/src/quadtree.zig | |
| parent | 82fca5c9f29124f37f6dcd08e73e6999ce44a69d (diff) | |
| download | sketchbook-6933f99ddb2d7103515d26838496309a807bba26.tar.gz sketchbook-6933f99ddb2d7103515d26838496309a807bba26.zip | |
Move standalone sketches into sketchbook examples
Diffstat (limited to 'examples/noc/src/quadtree.zig')
| -rw-r--r-- | examples/noc/src/quadtree.zig | 135 |
1 files changed, 135 insertions, 0 deletions
diff --git a/examples/noc/src/quadtree.zig b/examples/noc/src/quadtree.zig new file mode 100644 index 0000000..98c791d --- /dev/null +++ b/examples/noc/src/quadtree.zig @@ -0,0 +1,135 @@ +//! 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)); +} |
