1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
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));
}
|