mirror of
https://github.com/mourner/flatbush.git
synced 2025-12-08 17:36:26 +00:00
34d7277eec
* added test * add Bentley-McIlroy 3-way partitioning * switch to non recursive implementation * fixed stack handling * rename function * escaped ts errors + enhanced performance * remove escaped error * additional performance enhancement
285 lines
9.2 KiB
JavaScript
285 lines
9.2 KiB
JavaScript
import Flatbush from './index.js';
|
|
import test from 'node:test';
|
|
import assert from 'node:assert/strict';
|
|
|
|
const data = [
|
|
8, 62, 11, 66, 57, 17, 57, 19, 76, 26, 79, 29, 36, 56, 38, 56, 92, 77, 96, 80, 87, 70, 90, 74,
|
|
43, 41, 47, 43, 0, 58, 2, 62, 76, 86, 80, 89, 27, 13, 27, 15, 71, 63, 75, 67, 25, 2, 27, 2, 87,
|
|
6, 88, 6, 22, 90, 23, 93, 22, 89, 22, 93, 57, 11, 61, 13, 61, 55, 63, 56, 17, 85, 21, 87, 33,
|
|
43, 37, 43, 6, 1, 7, 3, 80, 87, 80, 87, 23, 50, 26, 52, 58, 89, 58, 89, 12, 30, 15, 34, 32, 58,
|
|
36, 61, 41, 84, 44, 87, 44, 18, 44, 19, 13, 63, 15, 67, 52, 70, 54, 74, 57, 59, 58, 59, 17, 90,
|
|
20, 92, 48, 53, 52, 56, 92, 68, 92, 72, 26, 52, 30, 52, 56, 23, 57, 26, 88, 48, 88, 48, 66, 13,
|
|
67, 15, 7, 82, 8, 86, 46, 68, 50, 68, 37, 33, 38, 36, 6, 15, 8, 18, 85, 36, 89, 38, 82, 45, 84,
|
|
48, 12, 2, 16, 3, 26, 15, 26, 16, 55, 23, 59, 26, 76, 37, 79, 39, 86, 74, 90, 77, 16, 75, 18,
|
|
78, 44, 18, 45, 21, 52, 67, 54, 71, 59, 78, 62, 78, 24, 5, 24, 8, 64, 80, 64, 83, 66, 55, 70,
|
|
55, 0, 17, 2, 19, 15, 71, 18, 74, 87, 57, 87, 59, 6, 34, 7, 37, 34, 30, 37, 32, 51, 19, 53, 19,
|
|
72, 51, 73, 55, 29, 45, 30, 45, 94, 94, 96, 95, 7, 22, 11, 24, 86, 45, 87, 48, 33, 62, 34, 65,
|
|
18, 10, 21, 14, 64, 66, 67, 67, 64, 25, 65, 28, 27, 4, 31, 6, 84, 4, 85, 5, 48, 80, 50, 81, 1,
|
|
61, 3, 61, 71, 89, 74, 92, 40, 42, 43, 43, 27, 64, 28, 66, 46, 26, 50, 26, 53, 83, 57, 87, 14,
|
|
75, 15, 79, 31, 45, 34, 45, 89, 84, 92, 88, 84, 51, 85, 53, 67, 87, 67, 89, 39, 26, 43, 27, 47,
|
|
61, 47, 63, 23, 49, 25, 53, 12, 3, 14, 5, 16, 50, 19, 53, 63, 80, 64, 84, 22, 63, 22, 64, 26,
|
|
66, 29, 66, 2, 15, 3, 15, 74, 77, 77, 79, 64, 11, 68, 11, 38, 4, 39, 8, 83, 73, 87, 77, 85, 52,
|
|
89, 56, 74, 60, 76, 63, 62, 66, 65, 67
|
|
];
|
|
|
|
function createIndex() {
|
|
const index = new Flatbush(data.length / 4);
|
|
|
|
for (let i = 0; i < data.length; i += 4) {
|
|
index.add(data[i], data[i + 1], data[i + 2], data[i + 3]);
|
|
}
|
|
index.finish();
|
|
|
|
return index;
|
|
}
|
|
|
|
function createSmallIndex(numItems, nodeSize) {
|
|
const index = new Flatbush(numItems, nodeSize);
|
|
for (let i = 0; i < 4 * numItems; i += 4) {
|
|
index.add(data[i], data[i + 1], data[i + 2], data[i + 3]);
|
|
}
|
|
index.finish();
|
|
return index;
|
|
}
|
|
|
|
function createIndexSharedArrayBuffer() {
|
|
const index = new Flatbush(data.length / 4, 16, Float64Array, SharedArrayBuffer);
|
|
|
|
for (let i = 0; i < data.length; i += 4) {
|
|
index.add(data[i], data[i + 1], data[i + 2], data[i + 3]);
|
|
}
|
|
index.finish();
|
|
return index;
|
|
}
|
|
|
|
|
|
test('indexes a bunch of rectangles', () => {
|
|
const index = createIndex();
|
|
|
|
const len = index._boxes.length;
|
|
assert.equal(index._boxes.length + index._indices.length, 540);
|
|
assert.deepEqual(Array.from(index._boxes.subarray(len - 4, len)), [0, 1, 96, 95]);
|
|
assert.deepEqual(index._indices[len / 4 - 1], 400);
|
|
});
|
|
|
|
test('skips sorting less than nodeSize number of rectangles', () => {
|
|
const numItems = 14;
|
|
const nodeSize = 16;
|
|
const index = createSmallIndex(numItems, nodeSize);
|
|
|
|
// compute expected root box extents
|
|
let rootXMin = Infinity;
|
|
let rootYMin = Infinity;
|
|
let rootXMax = -Infinity;
|
|
let rootYMax = -Infinity;
|
|
for (let i = 0; i < 4 * numItems; i += 4) {
|
|
if (data[i] < rootXMin) rootXMin = data[i];
|
|
if (data[i + 1] < rootYMin) rootYMin = data[i + 1];
|
|
if (data[i + 2] > rootXMax) rootXMax = data[i + 2];
|
|
if (data[i + 3] > rootYMax) rootYMax = data[i + 3];
|
|
}
|
|
|
|
// sort should be skipped, ordered progressing indices expected
|
|
const expectedIndices = [];
|
|
for (let i = 0; i < numItems; ++i) {
|
|
expectedIndices.push(i);
|
|
}
|
|
expectedIndices.push(0);
|
|
|
|
const len = index._boxes.length;
|
|
|
|
assert.deepEqual(Array.from(index._indices), expectedIndices);
|
|
assert.equal(len, (numItems + 1) * 4);
|
|
assert.deepEqual(Array.from(index._boxes.subarray(len - 4, len)), [rootXMin, rootYMin, rootXMax, rootYMax]);
|
|
});
|
|
|
|
test('performs bbox search', () => {
|
|
const index = createIndex();
|
|
|
|
const ids = index.search(40, 40, 60, 60);
|
|
|
|
const results = [];
|
|
for (let i = 0; i < ids.length; i++) {
|
|
results.push(data[4 * ids[i]]);
|
|
results.push(data[4 * ids[i] + 1]);
|
|
results.push(data[4 * ids[i] + 2]);
|
|
results.push(data[4 * ids[i] + 3]);
|
|
}
|
|
|
|
assert.deepEqual(results.sort(compare), [57, 59, 58, 59, 48, 53, 52, 56, 40, 42, 43, 43, 43, 41, 47, 43].sort(compare));
|
|
});
|
|
|
|
test('reconstructs an index from array buffer', () => {
|
|
const index = createIndex();
|
|
const index2 = Flatbush.from(index.data);
|
|
|
|
assert.deepEqual(index, index2);
|
|
});
|
|
|
|
test('throws an error when reconstructing an index from array buffer if not 8-byte aligned', () => {
|
|
const index = createIndex();
|
|
const byteOffset = 12;
|
|
const newArrayBuffer = new ArrayBuffer(index.data.byteLength + byteOffset);
|
|
const newView = new Uint8Array(newArrayBuffer, byteOffset);
|
|
newView.set(new Uint8Array(index.data));
|
|
|
|
assert.throws(() => {
|
|
Flatbush.from(newArrayBuffer, byteOffset);
|
|
});
|
|
});
|
|
|
|
test('reconstructs an index from a Uint8Array', () => {
|
|
const index = createIndex();
|
|
const byteOffset = 16;
|
|
const newArrayBuffer = new ArrayBuffer(index.data.byteLength + byteOffset);
|
|
const newView = new Uint8Array(newArrayBuffer, byteOffset);
|
|
newView.set(new Uint8Array(index.data));
|
|
|
|
const index2 = Flatbush.from(newArrayBuffer, byteOffset);
|
|
|
|
assert.deepEqual(index._boxes, index2._boxes);
|
|
assert.deepEqual(index._indices, index2._indices);
|
|
assert.equal(index.numItems, index2.numItems);
|
|
assert.equal(index.nodeSize, index2.nodeSize);
|
|
assert.deepEqual(index._levelBounds, index2._levelBounds);
|
|
assert.notEqual(index.byteOffset, index2.byteOffset);
|
|
});
|
|
|
|
test('defaults to adding a point when not providing maxX/maxY', () => {
|
|
const index = new Flatbush(1);
|
|
index.add(10, 10);
|
|
index.finish();
|
|
assert.deepEqual(index.search(0, 0, 20, 20), [0]);
|
|
});
|
|
|
|
test('throws an error if added less items than the index size', () => {
|
|
assert.throws(() => {
|
|
const index = new Flatbush(data.length / 4);
|
|
index.finish();
|
|
});
|
|
});
|
|
|
|
test('throws an error if searching before indexing', () => {
|
|
assert.throws(() => {
|
|
const index = new Flatbush(data.length / 4);
|
|
index.search(0, 0, 20, 20);
|
|
});
|
|
});
|
|
|
|
test('does not freeze on numItems = 0', {timeout: 100}, () => {
|
|
assert.throws(() => {
|
|
new Flatbush(0); // eslint-disable-line
|
|
});
|
|
});
|
|
|
|
test('performs a k-nearest-neighbors query', () => {
|
|
const index = createIndex();
|
|
const ids = index.neighbors(50, 50, 3);
|
|
assert.deepEqual(ids.sort(compare), [31, 6, 75].sort(compare));
|
|
});
|
|
|
|
test('k-nearest-neighbors query accepts maxDistance', () => {
|
|
const index = createIndex();
|
|
const ids = index.neighbors(50, 50, Infinity, 12);
|
|
assert.deepEqual(ids.sort(compare), [6, 29, 31, 75, 85].sort(compare));
|
|
});
|
|
|
|
test('k-nearest-neighbors query accepts filterFn', () => {
|
|
const index = createIndex();
|
|
const ids = index.neighbors(50, 50, 6, Infinity, i => i % 2 === 0);
|
|
assert.deepEqual(ids.sort(compare), [6, 16, 18, 24, 54, 80].sort(compare));
|
|
});
|
|
|
|
test('performs a k-nearest-neighbors query with all items', () => {
|
|
const index = createIndex();
|
|
const ids = index.neighbors(50, 50);
|
|
assert.deepEqual(ids.length, data.length >> 2);
|
|
});
|
|
|
|
test('returns index of newly-added rectangle', () => {
|
|
const count = 5;
|
|
const index = new Flatbush(count);
|
|
|
|
const ids = [];
|
|
for (let i = 0; i < count; i++) {
|
|
const id = index.add(data[i], data[i + 1], data[i + 2], data[i + 3]);
|
|
ids.push(id);
|
|
}
|
|
|
|
const expectedSequence = Array.from(Array(count), (v, i) => i);
|
|
assert.deepEqual(ids, expectedSequence);
|
|
});
|
|
|
|
test('creates an index using SharedArrayBuffer', () => {
|
|
const index = createIndexSharedArrayBuffer();
|
|
assert(index.data instanceof SharedArrayBuffer);
|
|
});
|
|
|
|
test('reconstructs an index from SharedArrayBuffer', () => {
|
|
const index = createIndexSharedArrayBuffer();
|
|
const index2 = Flatbush.from(index.data);
|
|
|
|
assert.deepEqual(index, index2);
|
|
});
|
|
|
|
test('quicksort should work with an inbalanced dataset', () => {
|
|
const n = 15000;
|
|
const index = new Flatbush(2 * n);
|
|
|
|
function linspace(start, stop, num, endpoint = true) {
|
|
const div = endpoint ? (num - 1) : num;
|
|
const step = (stop - start) / div;
|
|
return Array.from({length: num}, (_, i) => start + step * i);
|
|
}
|
|
|
|
const items = linspace(0, 1000, n);
|
|
const items2 = linspace(0, 1000, n);
|
|
|
|
for (const p of items) {
|
|
index.add(p, 0, p, 0);
|
|
}
|
|
|
|
for (const p of items2) {
|
|
index.add(p, 0, p, 0);
|
|
}
|
|
|
|
index.finish();
|
|
|
|
assert.doesNotThrow(() => {
|
|
index.search(-100, -1, 15000, 1);
|
|
});
|
|
});
|
|
|
|
test('quicksort should work with duplicates', () => {
|
|
const n = 55000 + 5500 + 7700;
|
|
const index = new Flatbush(n);
|
|
|
|
let x = 0;
|
|
|
|
for (let p = 0; p < 55000; p++) {
|
|
index.add(x, 3.0, x, 3.0);
|
|
x++;
|
|
}
|
|
|
|
for (let p = 0; p < 5500; p++) {
|
|
index.add(x, 4.0, x, 4.0);
|
|
x++;
|
|
}
|
|
|
|
for (let p = 0; p < 7700; p++) {
|
|
index.add(x, 5.0, x, 5.0);
|
|
x++;
|
|
}
|
|
|
|
index.finish();
|
|
|
|
assert.doesNotThrow(() => {
|
|
index.search(0.5, -1, 6.5, 1);
|
|
});
|
|
});
|
|
|
|
|
|
|
|
|
|
function compare(a, b) { return a - b; }
|