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
136
137
138
139
140
141
142
143
144
145
|
import { test, assert } from './test-assert.js';
import { AABB, QTNode } from './Geometry.js';
test('AABB correctly contains/excludes points', () => {
const box = new AABB(0, 0, 1, 1);
// interior
assert.ok(box.contains({ x: 0.5, y: 0.5 }));
// upper left
assert.ok(!box.contains({ x: -1, y: -1 }));
// above
assert.ok(!box.contains({ x: 0.5, y: -1}));
// upper right
assert.ok(!box.contains({ x: 2, y: -1 }));
// left
assert.ok(!box.contains({ x: -1, y: 0.5 }));
// right
assert.ok(!box.contains({ x: 2, y: 0.5}));
// lower left
assert.ok(!box.contains({ x: -1, y: 2 }));
// below
assert.ok(!box.contains({ x: 0.5, y: 2}));
// lower right
assert.ok(!box.contains({ x: 2, y: 2 }));
});
test('AABB correctly intersects other AABBs', () => {
const box = new AABB(1, 1, 4, 4);
// interior
assert.ok(box.intersects(new AABB(2, 2, 2, 2,)));
// upper left
assert.ok(box.intersects(new AABB(0, 0, 4, 4)));
assert.ok(!box.intersects(new AABB(0, 0, 0.5, 0.5)));
// above
assert.ok(box.intersects(new AABB(2, 0, 2, 2)));
assert.ok(!box.intersects(new AABB(2, 0, 2, 0.5)));
// upper right
assert.ok(box.intersects(new AABB(2, 0, 4, 2)));
assert.ok(!box.intersects(new AABB(6, 0, 4, 2)));
// left
assert.ok(box.intersects(new AABB(0, 2, 2, 2)));
assert.ok(!box.intersects(new AABB(0, 2, 0.5, 2)));
// right
assert.ok(box.intersects(new AABB(4, 2, 2, 2)));
assert.ok(!box.intersects(new AABB(6, 2, 2, 2)));
// lower left
assert.ok(box.intersects(new AABB(0, 4, 4, 4)));
assert.ok(!box.intersects(new AABB(0, 6, 0.5, 0.5)));
// below
assert.ok(box.intersects(new AABB(2, 4, 2, 2)));
assert.ok(!box.intersects(new AABB(2, 6, 2, 0.5)));
// lower right
assert.ok(box.intersects(new AABB(2, 4, 4, 2)));
assert.ok(!box.intersects(new AABB(6, 6, 4, 2)));
});
test('AABB correctly handles points at the edges', () => {
const box = new AABB(0, 0, 1, 1);
assert.ok(box.contains({ x: 0, y: 0 }));
assert.ok(box.contains({ x: 0.5, y: 0 }));
assert.ok(box.contains({ x: 0, y: 0.5 }));
// bad corners
assert.ok(!box.contains({ x: 1, y: 0 }));
assert.ok(!box.contains({ x: 0, y: 1 }));
assert.ok(!box.contains({ x: 1, y: 1 }));
// bad edges
assert.ok(!box.contains({ x: 1, y: 0.5 }));
assert.ok(!box.contains({ x: 0.5, y: 1 }));
});
test('QTNode correctly inserts points', () => {
const node = new QTNode(0, 0, 1, 1);
assert.equal(node.type.toString(), 'QTNode.Empty');
let result = node.insert({ x: -1, y: -1 }); // out of range, should not insert
assert.ok(!result);
assert.equal(node.type.toString(), 'QTNode.Empty');
result = node.insert({ x: 0.5, y: 0.5 }); // in range
assert.ok(result);
assert.equal(node.type.toString(), 'QTNode.Leaf');
assert.deepEqual(node.point, { x: 0.5, y: 0.5 });
});
test('QTNode correctly subdivides', () => {
const node = new QTNode(0, 0, 2, 2);
assert.ok(!node.subnode);
node.subdivide();
assert.equal(node.subnode.length, 4);
assert.deepEqual(node.subnode[0], new QTNode(0, 0, 1, 1));
assert.deepEqual(node.subnode[1], new QTNode(1, 0, 1, 1));
assert.deepEqual(node.subnode[2], new QTNode(0, 1, 1, 1));
assert.deepEqual(node.subnode[3], new QTNode(1, 1, 1, 1));
});
test('QTNode correctly inserts multiple points', () => {
const node = new QTNode(0, 0, 2, 2);
const p0 = { x: 1, y: 1 };
const p1 = { x: 0.5, y: 0.5 };
const oob = { x: 10, y: 15 };
assert.ok(node.insert(p0));
assert.ok(node.insert(p1));
assert.ok(!node.insert(oob));
assert.equal(node.type.toString(), 'QTNode.Branch');
assert.equal(node.subnode[0].type.toString(), 'QTNode.Leaf');
assert.deepEqual(node.subnode[0].point, p1);
assert.equal(node.subnode[1].type.toString(), 'QTNode.Empty');
assert.equal(node.subnode[2].type.toString(), 'QTNode.Empty');
assert.equal(node.subnode[3].type.toString(), 'QTNode.Leaf');
assert.deepEqual(node.subnode[3].point, p0);
});
|
