summaryrefslogtreecommitdiff
path: root/examples/noc/src/quadtree.zig
diff options
context:
space:
mode:
Diffstat (limited to 'examples/noc/src/quadtree.zig')
-rw-r--r--examples/noc/src/quadtree.zig135
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));
+}