CollisionIndex stores boxes outside of grid range

[ChrisLoer]

We only store collision boxes in a grid that covers the area of the viewport and a little bit of padding outside of it. When we run collision detection, we may place symbols that end up completely outside the range of that grid. These symbols will never detect any collisions, so they'll always get placed. This doesn't usually matter, because they're offscreen. However, if you pan the map to bring them onscreen, they'll be visible until the next placement occurs, which might then detect collisions and cause them to fade out.

In practice, this doesn't seem to be very disruptive -- placement usually happens quickly enough that by the time the too-densely-placed labels come on screen, they're already mostly faded out.

/cc @ansis @jfirebaugh @anandthakker

[ChrisLoer]

This is more correct but less performant than I thought on my first reading of the code. 😬

Items outside the grid range get added to the cells right along the edge of the grid. This makes the grid slower than it needs to be, but also prevents the problem I originally described. Essentially it makes the range of the grid infinite, but the performance gets worse the more things you place outside the defined range.

[ChrisLoer]

This is more performant but less correct than I thought on my second reading of the code. 😬

It's true that we store boxes for items outside the grid range (which does slow queries along the edges down), but when we query entirely outside the grid range, we'll short circuit the query results to "false":

mapbox-gl-js/src/symbol/grid_index.js

Lines 90 to 93 in 13ea16d

	_query(x1: number, y1: number, x2: number, y2: number, hitTest: boolean) {
	if (x2 < 0 || x1 > this.width || y2 < 0 || y1 > this.height) {
	return hitTest ? false : [];
	}

This means that collision detection still works for features that have any part of their geometry touching the grid, but not for features entirely outside the grid.

In practice, this doesn't seem to be very disruptive -- placement usually happens quickly enough that by the time the too-densely-placed labels come on screen, they're already mostly faded out.

It may not be terrible, but it was at least ugly enough to get reported as #6489.

[dagjomar]

Amy progress on this?

[ChrisLoer]

@dagjomar I put together a PR at #6784, we should merge it soon. If you're interested, you might try checking out that branch to see if you get the behavior you'd expect after the changes.

[mourner]

This was fixed in #6784.