Compute frontend label collisions when generating tiles

[wipfli]

Planetiler has a functionality to limit the number of point labels in a given area. Something with setSortKey() and setLabelGridSizeAndLimit() I think. This is nice because it reduces the number of point labels that go into the tiles and MapLibre GL JS has to handle fewer collisions in the frontend.

I wonder if we could take this one step further and compute frontend label collisions when generating tiles and remove points that anyway would not render because other points are more important?

The approach would assume some frontend rendering style, pitch and rotation of the map, and screen resolution.

[msbarry]

Yes, I've done this in a precise way before where I precompute the exact minzoom to show labels at so there is no client-side collision detection at all. I have a fork of maplibre that uses an attribute to drive minzoom feature comparison in the shaders and proposed maplibre/maplibre-gl-js#1867 to pull that capability into maplibre without needing a fork. The result is super smooth but only if you disable tilting and rotating. It also requires a global index of all points that you insert points into in order of importance to determine the min zoom at which there is no collision with other labels - although I wonder if that same calculation could be done on a per-tile basis...?

You could do a more coarse version of this that doesn't compute the exact label size based on text but instead comes up with a rectangle to use for a point and only emits it if there are less than a certain number of collisions with other points to limit density. That would work for points in addition to labels, like the density limiting that tippecanoe can do.

[wipfli]

Interesting!

[wipfli]

Crazy that you can get rid of collision detection completely with fractional min zooms...

[msbarry]

Here's a demo using this approach: https://msbarry.github.io/maplibre-minzoom-demo

[wipfli]

Thanks for sharing the source in maplibre-gl-js: msbarry/maplibre-gl-js@bf3b8de

[wipfli]

One could even precalculate label placement along lines

[1ec5]

The approach would assume some frontend rendering style, pitch and rotation of the map, and screen resolution.

That’s a lot of assumptions. This optimization could be quite useful for some cases, especially static image rendering, while others like navigation would absolutely need to consider rotation and pitch (and therefore the map viewport’s dimensions). Another confounding factor would be 3D terrain. It could be worth the trouble if it’s disabled by default but developers have the option to enable it.

[wipfli]

Right. Its just when I think about the way I use google maps it is, for me, always no pitch and North is up. I know not everybody is the same, but for me this is how I like to look at maps...

[wipfli]

Maybe one could also just turn on and off collision detection in the frontend depending on pitch and rotation...

[wipfli]

Currently, I am using setPointLabelGridSizeAndLimit to limit the number of points in the tiles, but I guess this method does not allow to compute bounding boxes or similar of point labels.

How could I calculate collisions in Planetiler?

[msbarry]

For perfect collision avoidance, the tricky part is computing the exact size of the text bounding boxes based on the font and layout parameters - I used a modified version of maplibre to do that in https://msbarry.github.io/maplibre-minzoom-demo/ but it won't scale up to making a real map. You could either port maplibre layout code to java, or figure out an approximate bounding box.

Once you've got the bounding boxes, you'd need to port https://github.com/maplibre/maplibre-gl-js/blob/main/src/symbol/collision_index.ts logic to java which places each box from most to least important, determining the min zoom to avoid collision based on distance from nearest box that's already placed. I could share a simplified version of that too

[wipfli]

For me it would be fine to have some padding around text labels. So we could be a bit generous in estimating the size of the bounding box. We could assume a single line of text and a fixed width character.

It would be great if you could share a simplified version of the collision code in java.

[msbarry]

Sounds good, here's a simplified pseudo-javascript version of the logic: https://gist.github.com/msbarry/bfe755866ad568686d38f9f4e0674379

There are spatial indexes with a a similar API to rbush in JTS, see "all know implementing classes" here: https://locationtech.github.io/jts/javadoc/org/locationtech/jts/index/SpatialIndex.html - I think QuadTree is the only mutable one though.