search & collides support custom intersects & contains

[sakitam-fdd]

Motivation

I used this in the implementation of a patch mapbox tilt view tile, where we invert the missing tiles under this tier based on the row and column numbers of the TileID, who probably looks like this:

function intersects(a, b) {
    return b.minX < a.maxX &&
        b.minY < a.maxY &&
        b.maxX > a.minX &&
        b.maxY > a.minY;
}

for (let x = 0; x < xd; x++) {
    for (let y = 0; y < yd; y++) {
        const tile = neighbor(baseTileID, x, y);
        if (!tiles.find(t => t.key === tile.key)) {
            const result = tree.collides({
                minX: tile.bbox[0],
                minY: tile.bbox[1],
                maxX: tile.bbox[2],
                maxY: tile.bbox[3],
            }, { intersects });

            if (!result) {
                addTiles.push(tile);
            }
            console.log(tile, result);
        }
    }
}

But the computed tiles always return true when tested for collision with existing tiles, and in fact mathematically the co-edged tiles do intersect, but implementation-wise we might expect to reserve a certain amount of buffer.
An implementation that doesn't interfere with the existing logic is to support user-defined intersection and containment test functions, which is easy to implement, but requires some discussion.

Design Alternatives

1. search

search(bbox, options) {
    let node = this.data;
    const result = [];
    const intersectsFn = options && options.intersects ? options.intersects : intersects;
    const containsFn = options && options.contains ? options.contains : contains;

    if (!intersectsFn(bbox, node)) return result;

    const toBBox = this.toBBox;
    const nodesToSearch = [];

    while (node) {
        for (let i = 0; i < node.children.length; i++) {
            const child = node.children[i];
            const childBBox = node.leaf ? toBBox(child) : child;

            if (intersectsFn(bbox, childBBox)) {
                if (node.leaf) result.push(child);
                else if (containsFn(bbox, childBBox)) this._all(child, result);
                else nodesToSearch.push(child);
            }
        }
        node = nodesToSearch.pop();
    }

    return result;
}

2. collides

collides(bbox, options) {
    let node = this.data;
    const intersectsFn = options && options.intersects ? options.intersects : intersects;
    const containsFn = options && options.contains ? options.contains : contains;

    if (!intersectsFn(bbox, node)) return false;

    const nodesToSearch = [];
    while (node) {
        for (let i = 0; i < node.children.length; i++) {
            const child = node.children[i];
            const childBBox = node.leaf ? this.toBBox(child) : child;

            if (intersectsFn(bbox, childBBox)) {
                if (node.leaf || containsFn(bbox, childBBox)) return true;
                nodesToSearch.push(child);
            }
        }
        node = nodesToSearch.pop();
    }

    return false;
}

[CharanSriramUni]

For my personal project, just overwriting the toBBox function in a custom class to add a small amount of buffer circumvents this issue for me. Essentially just separating collision logic from displaying logic.

E.g,

toBBox(item: Box): BBox {
	return {
		minX: item.x + 0.01,
		minY: item.y + 0.01,
		maxX: item.x + item.width - 0.01,
		maxY: item.y + item.height - 0.01,
	};
}