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 --- modules/Geometry.test.js | 259 ----------------------------------------------- 1 file changed, 259 deletions(-) delete mode 100644 modules/Geometry.test.js (limited to 'modules/Geometry.test.js') diff --git a/modules/Geometry.test.js b/modules/Geometry.test.js deleted file mode 100644 index 925a53d..0000000 --- a/modules/Geometry.test.js +++ /dev/null @@ -1,259 +0,0 @@ -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