Removing items requires a bounding box

[DanPen]

tree.remove({ id: '1234' }, (a, b) => {
    console.log(a, b);
    return a.id === b.id;
});

I know the callback is never called because I never see the log statement.

[DanPen]

After experimenting a little, it seems that remove doesn't work without a matching bbox.

DanPen@845e8bd

[eeeeenchanted]

We experienced the same issue when removing, updating, and re-inserting the same item quickly.

We looked at the code and the issue is that contains(node, bbox) is returning false.

One thing that got us confused at first is why there needs to be a spatial search prior to removing an element given that the docs say elements are removed by reference. Would it be possible/make sense to have a Map() and only reference elements in the tree? This way removing would be dead simple, e.g., map.delete(item). Anyway, just a random idea.

[thisredone]

Actually probably the simplest way would be to keep a reference to parent for all nodes and iitems. This also helps greatly with item updates and reinsertions.
I have rewritten this library (https://github.com/thisredone/rbush/tree/dev) to support fast updates and removals; providing predicate function similar to #74; raycasting with stack-based, ordered ray traversal algorithm from this paper; finding collisions with the help of box-intersect for cross-leaf overlaps; and polling almost everywhere to avoid pressuring GC.
It's a very opinionated fork but it's there if you need any of those things.

[photonstorm]

@thisredone thank you for this fork, this is exactly what I need right now! Testing it immediately :)

[mizuiren]

Change the code if (!goingUp && !node.leaf && contains(node, bbox)) { // go down to if (!goingUp && !node.leaf && (item.id || contains(node, bbox))) { // go down can solve the problem, but got heavy performance, due to missing range lookup. Suggested use of reference deletion!

[xiaoiver]

I'm using this hack which makes contains(node, bbox) always returning true.

rBush.remove(
  {
    minX: Infinity,
    minY: Infinity,
    maxX: -Infinity,
    maxY: -Infinity,
    entity,
  },
  (a, b) => a.entity === b.entity,
);