方案
https://github.com/mourner/rbush
Usage
Importing RBush
// as a ES module
import RBush from 'rbush';
// as a CommonJS module
const RBush = require('rbush');
Creating a Tree
const tree = new RBush();
An optional argument to RBush
defines the maximum number of entries in a tree node. 9
(used by default) is a reasonable choice for most applications. Higher value means faster insertion and slower search, and vice versa.
const tree = new RBush(16);
Adding Data
Insert an item:
const item = {
minX: 20,
minY: 40,
maxX: 30,
maxY: 50,
foo: 'bar'
};
tree.insert(item);
Removing Data
Remove a previously inserted item:
tree.remove(item);
By default, RBush removes objects by reference. However, you can pass a custom equals
function to compare by value for removal, which is useful when you only have a copy of the object you need removed (e.g. loaded from server):
tree.remove(itemCopy, (a, b) => {
return a.id === b.id;
});
Remove all items:
tree.clear();
Data Format
By default, RBush assumes the format of data points to be an object with minX
, minY
, maxX
and maxY
properties. You can customize this by overriding toBBox
, compareMinX
and compareMinY
methods like this:
class MyRBush extends RBush {
toBBox([x, y]) { return {minX: x, minY: y, maxX: x, maxY: y}; }
compareMinX(a, b) { return a.x - b.x; }
compareMinY(a, b) { return a.y - b.y; }
}
const tree = new MyRBush();
tree.insert([20, 50]); // accepts [x, y] points
If you're indexing a static list of points (you don't need to add/remove points after indexing), you should use kdbush which performs point indexing 5-8x faster than RBush.
Bulk-Inserting Data
Bulk-insert the given data into the tree:
tree.load([item1, item2, ...]);
Bulk insertion is usually ~2-3 times faster than inserting items one by one. After bulk loading (bulk insertion into an empty tree), subsequent query performance is also ~20-30% better.
Note that when you do bulk insertion into an existing tree, it bulk-loads the given data into a separate tree and inserts the smaller tree into the larger tree. This means that bulk insertion works very well for clustered data (where items in one update are close to each other), but makes query performance worse if the data is scattered.
Search
const result = tree.search({
minX: 40,
minY: 20,
maxX: 80,
maxY: 70
});
Returns an array of data items (points or rectangles) that the given bounding box intersects.
Note that the search
method accepts a bounding box in {minX, minY, maxX, maxY}
format regardless of the data format.
const allItems = tree.all();
Returns all items of the tree.
Collisions
const result = tree.collides({minX: 40, minY: 20, maxX: 80, maxY: 70});
Returns true
if there are any items intersecting the given bounding box, otherwise false
.
Export and Import
// export data as JSON object
const treeData = tree.toJSON();
// import previously exported data
网友评论