search

maplibre / maplibre-rs

Experimental Maps for Web, Mobile and Desktop
Apache License 2.0
1.35k stars 79 forks source link

Optimization: Reduce size of Quadkey #90

Open maxammann opened 2 years ago

maxammann commented 2 years ago

This is an optimization without any clear benefit/problem associated -> Low Priority.

🤔 Expected Behavior

😯 Current Behavior

The quadkey currently uses 8 bits for zoom level + MAX_ZOOM * 8 bits while it could be optimized to 8 bits for zoom level + MAX_ZOOM * 2 bits. The 2 bits define the square used in each subdivision of the quad tree, it can be NW (north west), NE (north east), SW (south west) or SE (south east).

💁 Possible Solution

🔦 Context

💻 Examples

Drabble commented 2 years ago

For reference:

Just FYI, I was hacking on an optimized tile ID storage a while back - see https://github.com/nyurik/planetiler-rs/blob/main/experiments/src/tile_id.rs -- essentially its a single u32 that can store all z/x/y for z in 0..=15. I might create a crate at some point that has all the basic ID features.

_Originally posted by @nyurik in https://github.com/maplibre/maplibre-rs/pull/87#discussion_r868181039_

I think for this crate we want +15 zoom, but maybe it would be cool to have an enum between both representations.

_Originally posted by @maxammann in https://github.com/maplibre/maplibre-rs/pull/87#discussion_r870356154_

maxammann commented 2 years ago

I would like to point ant that the idea for a B-Tree + Quadkey comes from https://docs.microsoft.com/en-us/bingmaps/articles/bing-maps-tile-system#tile-coordinates-and-quadkeys

I never evaluated the performance though.