From 3bc2838360627f78a91a7cad81f3bc97711410c2 Mon Sep 17 00:00:00 2001 From: sanine Date: Sun, 29 May 2022 14:50:55 -0500 Subject: refactor: move everything into src/ subdirectory --- src/modules/Geometry.test.js | 259 +++++++++++++++++++++++++++++++++++++++++++ 1 file changed, 259 insertions(+) create mode 100644 src/modules/Geometry.test.js (limited to 'src/modules/Geometry.test.js') diff --git a/src/modules/Geometry.test.js b/src/modules/Geometry.test.js new file mode 100644 index 0000000..925a53d --- /dev/null +++ b/src/modules/Geometry.test.js @@ -0,0 +1,259 @@ +import { test, assert } from './test-assert.js'; +import { AABB, QTNode, QuadTree } from './Geometry.js'; + +const RUN_BENCHMARKS = false; + + +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); +}); + + +const randomPoint = () => ({ x: Math.random(), y: Math.random() }); + + +test('QTNode correctly returns points in region', () => { + const node = new QTNode(0, 0, 1, 1); + let points = []; + for (let i=0; i<100; i++) { + const pt = randomPoint(); + node.insert(pt); + points.push(pt); + } + + const pointsInRegion = aabb => { + let pts = []; + for (let pt of points) { + if (aabb.contains(pt)) pts.push(pt); + } + return pts; + }; + + const region = new AABB(0.25, 0.25, 0.5, 0.5); + let bf_points = pointsInRegion(region); + let qt_points = node.getPointsInRegion(region); + const compare = (a, b) => { + if (a.x == b.x) + return b.y - a.y; + return b.x - a.x; + }; + bf_points.sort(compare); + qt_points.sort(compare); + assert.deepEqual(bf_points, qt_points);}); + + +test('QuadTree correctly finds closest point for 10,000 random points', () => { + const tree = new QuadTree(1, 1); + + let points = []; + for (let i=0; i<10000; i++) { + const pt = randomPoint(); + tree.insert(pt); + points.push(pt); + } + + const distance = (a, b) => Math.sqrt((a.x - b.x)**2 + (a.y - b.y)**2); + const bf_closest = a => { + let closest = null; + let min_dist = 1000; + for (let b of points) { + let d = distance(a, b); + if (d < min_dist) { + min_dist = d; + closest = b; + } + } + return closest; + } + + for (let i=0; i<10000; i++) { + const pt = randomPoint(); + assert.deepEqual(bf_closest(pt), tree.closest(pt)); + } +}); + + +function benchmark(desc, f, iterations) { + process.stdout.write(`${desc}: `); + const start = process.uptime(); + for (let i=0; i { + const n_points = 1e5; + const iterations = 1e4; + console.log(`> benchmark get closest of ${n_points} random points ${iterations} times`); + + const tree = new QuadTree(1, 1); + let points = []; + for (let i=0; i Math.sqrt((a.x - b.x)**2 + (a.y - b.y)**2); + const bf_closest = a => { + let closest = null; + let min_dist = 1000; + for (let b of points) { + let d = distance(a, b); + if (d < min_dist) { + min_dist = d; + closest = b; + } + } + return closest; + } + + benchmark('\tbrute force', () => { + const pt = randomPoint(); + bf_closest(pt); + }, iterations); + + benchmark('\tquadtree', () => { + const pt = randomPoint(); + tree.closest(pt); + }, iterations); +} +if (RUN_BENCHMARKS) + closest_benchmark(); -- cgit v1.2.1