28:null 29:["$","title",null,{"children":"Map Tile Priorities | Jeshurun Hembd | Observable"}] 2e:T53c,md`## Value function dynamics Consider how the function behaves as each of the parameters are varied. ### Vary ${tex`A_{vis}`}, fix ${tex`L_t`} With tile size ${tex`L_t`} fixed, we can vary ${tex`A_{vis}`} by sliding it across the edge of the map. The tile's value is now proportional to ${tex`A_{vis}`}, the fraction of the tile that is within the viewport. ### Vary ${tex`L_t`}, keep tile within viewport As long as the tile is within the viewport, ${tex`A_{vis} = L_t^2`}. As the map zoom changes, the displayed size of the tile ${tex`L_t`} will change. The value function behavior has two cases: - ${tex`L_t > N_t`}: The value function reduces to ${tex`L_t / N_t`}, the *square root* of the tile's normalized visible area on the screen. - ${tex`L_t \le N_t`}: The tile is displayed smaller than its native resolution, so ${tex`\Delta^{-1} = 1`}, and the tile's value is its normalized visible area on the screen. Note that the first case mildly prioritizes lower-resolution tiles that fit within the viewport. These tiles can quickly give a big-picture view of the requested map area, while waiting for the higher-resolution tiles to load. Tiles with a resolution higher than the screen can display are strongly down-weighted based on their visible area. We can use this fact to define a default threshold for the value function. `2f:T518,md`## Preserving the edges The map extent is not tied to tile boundaries. The tiles required to render the edge of the map may have much of their area extending outside the map. Since the tile value function (at a given zoom) is proportional to the **visible** area within the map, these tiles may have values falling below the threshold of ${tex`\frac{1}{4}`}. For the map to be fully rendered, any tile at the map zoom level, with any pixels inside the visible area of the map, must be retained in the cache. To ensure that these tiles have a value above the threshold, ${tex`A_{vis}`} can be computed as the fraction of the tile that is inside a *padded* rectangle around the visible map. The most challenging case will be a tile just outside a corner of the map, with only one pixel inside the viewport. How much padding is needed to keep this tile's value above 1/4? Given padding length ${tex`N_p`}, the value of the corner tile will be: ${tex.block`V(tile) = \frac{N_p^2}{N_t^2} * \min\left( 1, \frac{N_t}{L_t} \right)`} The resolution term (for tiles at the zoom level requested by [d3-tile](https://github.com/d3/d3-tile)) can be as small as ${tex`\frac{1}{\sqrt{2}}`}. To handle the minimum resolution case, we therefore need ${tex.block`N_p \ge \frac{1}{2^{3/4}} N_t \approx 0.595 N_t`} `30:T6d3,function getTileMetric(layout, tileset, padding = 0.595) { const zoom = tileset[0][2]; const nTiles = 2 ** zoom; const tileLength = tileset.scale; // Length of one tile in pixels const mapResolution = layout.tileSize() / tileLength; function wrap(x, xmax) { while (x < 0) x += xmax; while (x >= xmax) x -= xmax; return x; } // Map is viewport + padding. Store the map cornerpoints in tile units const [vpWidth, vpHeight] = layout.size(); const pad = padding * mapResolution; // In tile units const x0 = wrap(-tileset.translate[0] - pad, nTiles); const x1 = x0 + vpWidth / tileLength + 2 * pad; // May cross antimeridian const y0 = -tileset.translate[1] - pad; const y1 = y0 + vpHeight / tileLength + 2 * pad; return function(tile) { let zoomFac = 2 ** (zoom - tile.z); let tileResolution = Math.min(1, mapResolution / zoomFac); // Convert the tile cornerpoints to tile units at MAP zoom level let tb = { x0: tile.x * zoomFac, x1: (tile.x + 1) * zoomFac, y0: tile.y * zoomFac, y1: (tile.y + 1) * zoomFac }; // Find intersections of map and tile. Be careful with the antimeridian let xOverlap = Math.max( // Test for intersection with the tile in its raw position Math.min(x1, tb.x1) - Math.max(x0, tb.x0), // Test with the tile shifted across the antimeridian Math.min(x1, tb.x1 + nTiles) - Math.max(x0, tb.x0 + nTiles) ); let yOverlap = Math.min(y1, tb.y1) - Math.max(y0, tb.y0); let overlapArea = Math.max(0, xOverlap) * Math.max(0, yOverlap); let visibleArea = overlapArea / mapResolution ** 2; // Flip sign to put most valuable tiles at the minimum return 1.0 - visibleArea * tileResolution; }; }31:T8fd,tileOptions = [ { name: "CartoDB Voyager", url: (x, y, z) => `https://${ "abc"[Math.abs(x + y) % 3] }.basemaps.cartocdn.com/rastertiles/voyager/${z}/${x}/${y}${ devicePixelRatio > 1 ? "@2x" : "" }.png`, cssTileSize: () => 256, realTileSize: () => rescalePixels(256), }, { name: "Stamen Terrain", url: (x, y, z) => `https://stamen-tiles-${ "abc"[Math.abs(x + y) % 3] }.a.ssl.fastly.net/terrain/${z}/${x}/${y}${ devicePixelRatio > 1 ? "@2x" : "" }.png`, cssTileSize: () => 256, realTileSize: () => rescalePixels(256), }, { name: "Stamen Toner", url: (x, y, z) => `https://stamen-tiles-${ "abc"[Math.abs(x + y) % 3] }.a.ssl.fastly.net/toner/${z}/${x}/${y}${ devicePixelRatio > 1 ? "@2x" : "" }.png`, cssTileSize: () => 256, realTileSize: () => rescalePixels(256), }, { name: "Stamen Toner (hybrid)", url: (x, y, z) => `https://stamen-tiles-${ "abc"[Math.abs(x + y) % 3] }.a.ssl.fastly.net/toner-hybrid/${z}/${x}/${y}${ devicePixelRatio > 1 ? "@2x" : "" }.png`, cssTileSize: () => 256, realTileSize: () => rescalePixels(256), }, { name: "Stamen Toner (lite)", url: (x, y, z) => `https://stamen-tiles-${ "abc"[Math.abs(x + y) % 3] }.a.ssl.fastly.net/toner-lite/${z}/${x}/${y}${ devicePixelRatio > 1 ? "@2x" : "" }.png`, cssTileSize: () => 256, realTileSize: () => rescalePixels(256), selected: true }, { name: "Stamen Watercolor", url: (x, y, z) => `https://stamen-tiles-${ "abc"[Math.abs(x + y) % 3] }.a.ssl.fastly.net/watercolor/${z}/${x}/${y}.png`, cssTileSize: () => 256, realTileSize: () => 256, // No @2x tile scaling on hi-res screens }, { name: "OSM Mapnik", url: (x, y, z) => `https://${"abc"[Math.abs(x + y) % 3]}.tile.osm.org/${z}/${x}/${y}.png`, cssTileSize: () => 256, realTileSize: () => 256, // No @2x tile scaling on hi-res screens }, { name: "Wikimedia Maps", url: (x, y, z) => `https://maps.wikimedia.org/osm-intl/${z}/${x}/${y}.png`, cssTileSize: () => 256, realTileSize: () => 256, // No @2x tile scaling on hi-res screens } ]32:[] 2c:{"id":"31d332fdf9d5cd35","slug":"map-tile-priorities","title":"Map Tile Priorities","thumbnail":"14bc7e3d50db437b6e4721ddc7e43c9eecdcf00293cf98b120be9a36500cc1d6","access_level":"public","create_time":"$D2020-03-18T02:23:52.825Z","update_time":"$D2020-04-04T23:34:24.931Z","view_time":null,"first_public_time":"$D2020-04-04T23:35:17.762Z","has_unpublished_edits":null,"fork":{"id":"0b2551610e24a6d3","slug":"tile-cache-pruning","title":"Tile Cache Pruning","owner":{"id":"54b0aa2cda468b5a","login":"jjhembd","name":"Jeshurun Hembd"}},"stars":7,"starred":false,"owner":{"type":"team","id":"54b0aa2cda468b5a","login":"jjhembd","name":"Jeshurun Hembd","avatar_url":"https://avatars-next.observableusercontent.com/d42857c40a13c8179e0491536477452e54d4f6808ec32ed4d8fbdad81c03758d","tier":"starter_2024"},"version":1788,"publish_version":1788,"role":null,"authored":false,"authors":[{"type":"individual","id":"4e65ca212a169cf2","login":"jjhembd","name":"Jeshurun Hembd","avatar_url":"https://avatars-next.observableusercontent.com/d42857c40a13c8179e0491536477452e54d4f6808ec32ed4d8fbdad81c03758d","tier":null}],"members":[{"type":"individual","id":"4e65ca212a169cf2","login":"jjhembd","name":"Jeshurun Hembd","avatar_url":"https://avatars-next.observableusercontent.com/d42857c40a13c8179e0491536477452e54d4f6808ec32ed4d8fbdad81c03758d","tier":null,"role":"editor"}],"comments":[],"custom_thumbnail":false,"trashed":false,"lapsed":null,"subscribed":null,"forks":0,"collection":null,"type":"notebook","body":{"title":"Map Tile Priorities","cells":[{"id":0,"value":"md`# Map Tile Priorities`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":487,"value":"md`The notebook [Tile Cache Pruning](https://observablehq.com/@jjhembd/tile-cache-pruning) explored how to identify map tiles that were no longer needed, so that they could be removed from the cache. Tiles were weighted based on their \"distance\" from the current view.\n\nThe distance metric gives unreasonably small values to low-zoom tiles. When the map is at zoom level 10, the zoom 0 tile covers the current view, so it has a small distance. But perhaps only one of this tile's pixels contributes to the map.\n\nThis notebook explores how to make the best use of the available bandwidth, by giving first priority to the tiles that will contribute the most to the current view.\n\nFirst, some results. Here is a map using the new priority function for cache pruning. At big zooms, it loads about 40% fewer tiles than the [previous method](https://observablehq.com/@jjhembd/tile-cache-pruning).\n`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":3,"value":"viewof mapContext = {\n const box = html`

`;\n const context = DOM.context2d(width, height);\n box.appendChild(context.canvas);\n const attribution = html`

`;\n box.appendChild(attribution);\n box.value = context;\n return box;\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":980,"value":"md`There are currently **${numCachedTiles}** tiles in the cache.`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":989,"value":"md`## The Tile Value Function\n\nHow valuable is a given tile to the current map? There are two factors to consider:\n1. The area within the viewport that is covered by the tile\n2. The visible resolution contributed by the tile\n\nIn equation form, the value of a tile is given by:\n${tex.block`V(tile) = \\frac{A_{vis}}{N_t^2} \\space \\Delta^{-1},`}\nwhere \n- ${tex`A_{vis}`} is the visible area covered by the tile, in units of screen pixels\n- ${tex`N_t`} is the number of pixels along one edge of a (square) tile\n- ${tex`\\Delta`} is the distance between tile pixels, in units of screen pixels.\n`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":1523,"value":"md`To compute ${tex`\\Delta`}, first define ${tex`L_t`}, the actual displayed size of a tile, again in units of screen pixels. (${tex`L_t`} differs from ${tex`N_t`} when the map zoom level is different from the tile's native zoom.)\n\nThe screen distance between tile pixels is ${tex`\\Delta = \\frac{L_t}{N_t}`}. But if ${tex`L_t < N_t`}, the tile pixels are too small to be visible on the screen. The useable resolution is therefore limited by the screen resolution:\n${tex.block`\\Delta^{-1} = \\min\\left( 1, \\frac{N_t}{L_t} \\right)`}\n`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":1516,"value":"$2e","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":1702,"value":"md`## Defining a threshold\nSuppose the user is zooming out. When the current tileset scale reaches ${tex`L_t < \\frac{1}{\\sqrt{2}} N_t`}, [d3-tile](https://github.com/d3/d3-tile) will request tiles from the next lower zoom level. The previous higher zoom tiles, which now have a value of ${tex`V(tile) = \\frac{1}{2}`}, are not displayed, and could be discarded.\n\nBut what if the user suddenly decides to zoom back in? Or suppose the zoom input device introduces a slight oscillation across the ${tex`L_t = \\frac{1}{\\sqrt{2}} N_t`} boundary? With a threshold of ${tex`\\frac{1}{2}`}, slight changes in the requested zoom could mean having to repeatedly re-load and parse a whole screenful of tiles.\n\nThe threshold to discard tiles should therefore be different from the boundary at which new tiles are requested. A threshold of ${tex`\\frac{1}{4}`}, corresponding to ${tex`L_t = \\frac{1}{2} N_t`}, will initiate the cache purges halfway between any tileset zoom changes.\n`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":1472,"value":"$2f","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":1743,"value":"md`## The code\n\nThe getTileMetric function inputs both a [d3-tile](https://github.com/d3/d3-tile) layout object, as well as a tileset created by this layout object. We need the layout object itself to get the tile size and viewport extent used in generating the tileset.\n\nThe metric function created by getTileMetric inputs a tile, and returns a *priority* for that tile, equal to ${tex`1 - V(tile)`}. This is for backwards compatibility: the .trim method in [tile-rack](https://github.com/GlobeletJS/tile-rack) retains the tiles with the *smallest* metric values. The recommended usage is therefore to discard tiles with priorities *larger* than 0.75.\n`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":1201,"value":"$30","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":1225,"value":"metric = getTileMetric(tiler, tileset)","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":753,"value":"numCachedTiles = {\n while (true) {\n drawTiles(mapContext);\n yield cache.trim(metric, 0.75);\n }\n}","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":1133,"value":"md`## Potential further work\n\nMore generally, we could weight different areas of the map based on their importance to the viewer. For example, the center of the map is important. We may also want to include a buffer around the viewport as \"visible\" area, to allow faster panning. But this buffer would be lower weight. A 2D Gaussian weight function, centered at the viewport center, might be one option.\n`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":890,"value":"md`---\n## Appendix 1: Tile factory function and cache\nAs of v0.2.0, [tile-rack](https://www.npmjs.com/package/tile-rack) can construct its own basic tile factory function for raster data. The tile size still depends on a screen resolution check.`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":1281,"value":"cachedTiles = {\n const retrieved = {};\n\n function retrieve(tile) {\n let id = [tile.z, tile.x, tile.y].join(\"/\");\n retrieved[id] = tile;\n }\n cache.process(retrieve);\n\n return retrieved;\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":197,"value":"cache = tileRack.initRasterCache(cacheTileSize, (z, x, y) =>\n tileSource.url(x, y, z)\n)","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":773,"value":"mutable cacheTileSize = tileSource.realTileSize();","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":776,"value":"resolutionString = {\n let mqString = `(resolution: ${devicePixelRatio}dppx)`;\n matchMedia(mqString).addEventListener(\"change\", () => {\n mutable cacheTileSize = tileSource.realTileSize();\n });\n return mqString;\n}","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":909,"value":"md`## Appendix 2: Tile layout management`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":852,"value":"md`### Finding the right tiles`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":10,"value":"tiler = d3\n .tile()\n .tileSize(tileSource.cssTileSize())\n .size([width, height])\n .clampX(false) // Allow panning across longitude 180 degrees","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":646,"value":"tileset = tiler(transform)","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":16,"value":"projection = d3\n .geoMercator()\n .center([-122.4183, 37.7750])\n .scale(Math.pow(2, 21) / (2 * Math.PI))\n .translate([width / 2, height / 2])","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":372,"value":"mutable transform = d3.zoomIdentity\n .translate(projection([0, 0])[0], projection([0, 0])[1])\n .scale(projection.scale() * 2 * Math.PI)","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":531,"value":"md`### Updating the map position and zoom`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":744,"value":"zoom = d3\n .zoom()\n .scaleExtent([1 << 10, 1 << 26])\n .extent([[0, 0], [width, height]])\n .translateExtent([[-Infinity, -0.5], [Infinity, 0.5]])\n .on(\"zoom\", () => {\n mutable transform = d3.event.transform;\n })","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":788,"value":"d3\n .select(mapContext.canvas)\n .call(zoom)\n .call(zoom.transform, mutable transform)","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":344,"value":"function drawTiles(ctx) {\n ctx.clearRect(0, 0, width, height);\n let scale = tileset.scale;\n // Edit translation: make sure the first tile starts at an integer pixel coordinate\n const tx = Math.round(tileset.translate[0] * scale) / scale;\n const ty = Math.round(tileset.translate[1] * scale) / scale;\n // If we are on an integer zoom level, all tiles will now be pixel-aligned\n\n for (const [x, y, z] of tileset) {\n const [xw, yw, zw] = d3.tileWrap([x, y, z]);\n let tileBox = cache.retrieve([zw, xw, yw]);\n if (!tileBox) continue;\n drawTileBox(ctx, tileBox, x + tx, y + ty, scale);\n }\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":212,"value":"md`## Appendix 3: Imports and other constants`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":1779,"value":"html``","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":1101,"value":"import { drawTileBox } from \"@jjhembd/zoomable-map-with-tile-cache\"","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":122,"value":"viewof tileSource = {\n const form = html`\n \n `;\n let deviceFactor = 1;\n form.i.onchange = () => {\n form.value = tileOptions[form.i.selectedIndex];\n form.dispatchEvent(new CustomEvent(\"input\"));\n };\n form.i.selectedIndex = Math.max(0, tileOptions.findIndex(o => o.selected));\n form.value = tileOptions[form.i.selectedIndex];\n return form;\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":444,"value":"$31","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":721,"value":"function rescalePixels(cssTileSize) {\n return devicePixelRatio > 1 ? 2 * cssTileSize : cssTileSize;\n}","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":14,"value":"height = 600","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":195,"value":"tileRack = import(\"tile-rack@0.2.0\")","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":5,"value":"d3 = require(\"d3@5\", \"d3-geo@1\", \"d3-tile@1\")","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"}],"files":"$W32","stdlib":"1","titling":"auto"}} 2d:"$2c:body"