begin refactor to use quadtree

1 files changed, 90 insertions, 0 deletions

diff --git a/modules/Geometry.test.js b/modules/Geometry.test.js
new file mode 100644
index 0000000..45ce397
--- /dev/null
+++ b/modules/Geometry.test.js
@@ -0,0 +1,90 @@
+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('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 });
+});