31:[] 2f:{"title":"From map tiles to IIIF tiles","cells":[{"id":0,"value":"# From map tiles to IIIF tiles\n\n[Allmaps](https://allmaps.org/) can georeference and warp any map that’s available through [IIIF](https://iiif.io/). \n\nTo render a georeferenced map, Allmaps first needs to figure out what part of the original image — in pixel coordinates — is needed to draw its warped geospatial version.\n\nAlthough many IIIF servers allow you to access any specific [region](https://iiif.io/api/image/3.0/#41-region) of an image in any required [size](https://iiif.io/api/image/3.0/#42-size), it is often much more efficient to use the image’s set of predefined [tiles](https://iiif.io/api/image/3.0/#54-tiles). These can be stitched together which makes them reusable and more useful to cache, both in a web browser and on the IIIF server.","pinned":false,"hidden":false,"mode":"md"},{"id":4,"value":"The algorithm is composed of the following steps:\n\n1. Compute geospatial extent of map view;\n2. Find the [`scaleFactor`](https://iiif.io/api/image/3.0/#54-tiles) of the IIIF tiles that best fits the current map view;\n3. Transform the map extent to tile coordinates in the chosen `scaleFactor`, using the GCPs of the georeferenced map;\n4. Use a [grid traversal algorithm](https://www.redblobgames.com/grids/line-drawing.html#supercover) to determine which IIIF tiles overlap with this polygon.","pinned":false,"hidden":false,"mode":"md"},{"id":1929,"value":"viewof iiifUri = selectUri(defaultManifestUri)","pinned":false,"hidden":false,"mode":"ojs"},{"id":1931,"value":"viewof imageUri = selectImageUri(iiifUri)","pinned":false,"hidden":false,"mode":"ojs"},{"id":1933,"value":"viewof map = selectMap(imageUri.uri)","pinned":false,"hidden":false,"mode":"ojs"},{"id":2002,"value":"The algorithm computes the IIIF tiles needed ${square('iiif-tile needed')} to warp the map with viewport ${square('map-extent')} are shown in the image below; the image also shows the map tiles of which the map viewport is composed ${square('map-tile')} \n as well as all of the Image's IIIF tiles ${square('iiif-tile')}:","pinned":false,"hidden":false,"mode":"html"},{"id":177,"value":"tileOverlapIiif = svg`\n`","pinned":false,"hidden":false,"mode":"ojs"},{"id":2059,"value":"Move the map to recompute the needed IIIF tiles:","pinned":false,"hidden":false,"mode":"md"},{"id":924,"value":"tileOverlapMap = mapView(center, zoom, viewof extent)","pinned":false,"hidden":false,"mode":"ojs"},{"id":1693,"value":"The following IIIF tiles are needed to render the warped map:\n\n

\n
${Object.values(tile.region).join(',')}
\n
${Object.values(tile.size).join(',')}
\n \n

","pinned":false,"hidden":false,"mode":"md"},{"id":5,"value":"## See also\n \n- https://www.redblobgames.com/grids/line-drawing.html#supercover\n- https://github.com/d3/d3-tile","pinned":false,"hidden":false,"mode":"md"},{"id":1688,"value":"## Computed values","pinned":false,"hidden":false,"mode":"md"},{"id":1991,"value":"imageInfo = fetch(`${imageUri.uri}/info.json`).then((response) => response.json())","pinned":false,"hidden":false,"mode":"ojs"},{"id":1989,"value":"parsedImage = iiifParser.parseIiif(imageInfo)","pinned":false,"hidden":false,"mode":"ojs"},{"id":1797,"value":"center = centroid.default(\n transform.svgPolygonToGeoJSONPolygon(transformer, map.pixelMask)\n).geometry.coordinates","pinned":false,"hidden":false,"mode":"ojs"},{"id":1371,"value":"mapTileScale = pixelExtentMinMax.width / width","pinned":false,"hidden":false,"mode":"ojs"},{"id":1748,"value":"zoomLevel = {\n let smallestScaleDiff = Number.POSITIVE_INFINITY\n let bestZoomLevel\n \n for (let tileset of tilesets) {\n for (let zoomLevel of tileset) {\n const scaleFactor = zoomLevel.scaleFactor\n const scaleDiff = Math.abs(Math.log2(scaleFactor) - Math.log2(mapTileScale))\n // const scaleDiff = Math.abs(scaleFactor - mapTileScale)\n \n if (scaleDiff < smallestScaleDiff) {\n smallestScaleDiff = scaleDiff\n bestZoomLevel = zoomLevel\n } \n }\n }\n\n return bestZoomLevel \n}","pinned":false,"hidden":false,"mode":"ojs"},{"id":535,"value":"iiifTileNeeded = (x, y, scaleFactor) => \n neededIiifTilesByX[x] && y >= neededIiifTilesByX[x][0] && y <= neededIiifTilesByX[x][1]\n && zoomLevel.scaleFactor === scaleFactor","pinned":false,"hidden":false,"mode":"ojs"},{"id":1577,"value":"neededIiifTiles = {\n const neededIiifTiles = []\n for (let x in neededIiifTilesByX) {\n const fromY = neededIiifTilesByX[x][0]\n const toY = neededIiifTilesByX[x][1]\n for (let y = fromY; y <= toY; y++) {\n neededIiifTiles.push({\n x: parseInt(x),\n y,\n ...zoomLevel\n })\n }\n }\n\n return neededIiifTiles\n}","pinned":false,"hidden":false,"mode":"ojs"},{"id":1523,"value":"neededIiifTilesByX = {\n const tiles = {}\n for (let i = 0; i < tilePixelExtent.length; i++) {\n const line = [tilePixelExtent[i], tilePixelExtent[(i + 1) % tilePixelExtent.length]] \n const lineTiles = tilesIntersect(line)\n \n lineTiles.forEach(([x, y]) => {\n if (x < 0 || y < 0 ||\n x >= zoomLevel.columns || y >= zoomLevel.rows) {\n return\n }\n \n if (!tiles[x]) {\n tiles[x] = [Number.POSITIVE_INFINITY, Number.NEGATIVE_INFINITY]\n }\n\n if (y < tiles[x][0]) {\n tiles[x][0] = y\n }\n\n if (y > tiles[x][1]) {\n tiles[x][1] = y\n } \n })\n } \n\n return tiles\n}","pinned":false,"hidden":false,"mode":"ojs"},{"id":1444,"value":"// From:\n// https://github.com/vHawk/tiles-intersect\n// See also:\n// https://www.redblobgames.com/grids/line-drawing.html#supercover\nfunction tilesIntersect ([a, b]) {\n let x = Math.floor(a[0])\n let y = Math.floor(a[1])\n const endX = Math.floor(b[0])\n const endY = Math.floor(b[1])\n\t\n let points = [[x, y]]\n\t\n if (x === endX && y === endY) {\n return points\n }\n\t\n const stepX = Math.sign(b[0] - a[0])\n const stepY = Math.sign(b[1] - a[1])\n\n const toX = Math.abs(a[0] - x - Math.max(0, stepX))\n const toY = Math.abs(a[1] - y - Math.max(0, stepY))\n\t\n const vX = Math.abs(a[0] - b[0])\n const vY = Math.abs(a[1] - b[1])\n\n let tMaxX = toX / vX\n let tMaxY = toY / vY\n\t\n const tDeltaX = 1 / vX\n const tDeltaY = 1 / vY\n\t\n while (!(x === endX && y === endY)) {\n if (tMaxX < tMaxY) {\n tMaxX = tMaxX + tDeltaX\n x = x + stepX\n } else {\n tMaxY = tMaxY + tDeltaY\n y = y + stepY\n }\n\t\t\n points.push([x, y])\n }\n\t\n return points\n}","pinned":false,"hidden":false,"mode":"ojs"},{"id":1417,"value":"tilePixelExtent = pixelExtent\n .map((point) => [\n point[0] / zoomLevel.originalWidth,\n point[1] / zoomLevel.originalHeight\n ])","pinned":false,"hidden":false,"mode":"ojs"},{"id":161,"value":"pixelMapTiles = mapTiles\n .map((tile) => tileExtent(tile))\n .map(([y1, x1, y2, x2]) => [\n transform.toImage(transformer, [y1, x1]),\n transform.toImage(transformer, [y1, x2]),\n transform.toImage(transformer, [y2, x2]),\n transform.toImage(transformer, [y2, x1])\n ])","pinned":false,"hidden":false,"mode":"ojs"},{"id":1635,"value":"pixelExtentMinMax = {\n const xs = []\n const ys = []\n \n for (let point of pixelExtent) {\n xs.push(point[0])\n ys.push(point[1])\n }\n\n const [minX, maxX] = d3.extent(xs)\n const [minY, maxY] = d3.extent(ys)\n\n return {\n minX,\n maxX,\n minY,\n maxY,\n width: maxX - minX,\n height: maxY - minY\n }\n}","pinned":false,"hidden":false,"mode":"ojs"},{"id":1279,"value":"pixelExtent = {\n // TODO: maybe it's better and more efficient\n // to just compute the scale of one line of the extent?\n const [y1, x1, y2, x2] = extent\n\n return [\n transform.toImage(transformer, [y1, x1]),\n transform.toImage(transformer, [y1, x2]),\n transform.toImage(transformer, [y2, x2]),\n transform.toImage(transformer, [y2, x1])\n ]\n}","pinned":false,"hidden":false,"mode":"ojs"},{"id":372,"value":"iiifTiles = tilesets.map(tilesFromTileset).flat(1)","pinned":false,"hidden":false,"mode":"ojs"},{"id":404,"value":"fullImageUrl = iiifParser.getImageUrl(parsedImage, { size: { width: width * 2 } })","pinned":false,"hidden":false,"mode":"ojs"},{"id":83,"value":"mapTiles = d3.tile()\n .tileSize(mapTileSize)\n .size([width, height])\n .scale(projection.scale() * 2 * Math.PI)\n .translate(projection([0, 0]))()","pinned":false,"hidden":false,"mode":"ojs"},{"id":254,"value":"viewScale = width / parsedImage.width","pinned":false,"hidden":false,"mode":"ojs"},{"id":85,"value":"height = Math.round(width / parsedImage.width * parsedImage.height)","pinned":false,"hidden":false,"mode":"ojs"},{"id":91,"value":"projection = d3.geoMercator()\n .fitSize([width, height], geojson)","pinned":false,"hidden":false,"mode":"ojs"},{"id":93,"value":"geojson = extentToPolygon(extent)","pinned":false,"hidden":false,"mode":"ojs"},{"id":579,"value":"iiifTileUrls = neededIiifTiles.map((tile) => { \n const { region, size } = iiifParser.getIiifTile(parsedImage, zoomLevel, tile.x, tile.y)\n return {\n ...tile,\n region, \n size,\n url: iiifParser.getImageUrl(parsedImage, { region, size }) \n }\n})","pinned":false,"hidden":false,"mode":"ojs"},{"id":1012,"value":"tilesets = iiifParser.getTilesets(parsedImage)","pinned":false,"hidden":false,"mode":"ojs"},{"id":1111,"value":"transformer = transform.createTransformer(map.gcps)","pinned":false,"hidden":false,"mode":"ojs"},{"id":29,"value":"viewof extent = new View([])","pinned":false,"hidden":false,"mode":"ojs"},{"id":1677,"value":"## Functions","pinned":false,"hidden":false,"mode":"md"},{"id":1669,"value":"function tilesFromTileset (tileset, index) {\n return tileset\n .map((zoomLevel) => Array(Math.ceil(parsedImage.width / (zoomLevel.width * zoomLevel.scaleFactor))).fill().map((_, x) => \n Array(Math.ceil(parsedImage.height / (zoomLevel.height * zoomLevel.scaleFactor))).fill().map((_, y) => ({ \n x,\n y,\n scaleFactor: zoomLevel.scaleFactor,\n ...iiifParser.getIiifTile(parsedImage, zoomLevel, x, y),\n tilesetIndex: index\n })))).flat(2)\n}","pinned":false,"hidden":false,"mode":"ojs"},{"id":122,"value":"tileExtent = ([x, y, z]) => [...tileToLonLat([x, y, z]), ...tileToLonLat([x + 1, y + 1, z])]","pinned":false,"hidden":false,"mode":"ojs"},{"id":111,"value":"tileToLonLat = ([x, y, z]) => {\n const n = Math.PI - 2 * Math.PI * y / Math.pow(2, z)\n const longitude = x / Math.pow(2, z) * 360 - 180\n const latitude = 180 / Math.PI * Math.atan(0.5 * (Math.exp(n) - Math.exp(-n)))\n \n return [longitude, latitude] \n}","pinned":false,"hidden":false,"mode":"ojs"},{"id":113,"value":"extentToPolygon = (extent) => ({\n type: 'Polygon',\n coordinates: [\n [\n [extent[0], extent[1]],\n [extent[0], extent[3]],\n [extent[2], extent[3]],\n [extent[2], extent[1]], \n [extent[0], extent[1]]\n ]\n ]\n})","pinned":false,"hidden":false,"mode":"ojs"},{"id":21,"value":"function* mapView (center, zoom, extent) {\n const container = html`

`\n yield container\n \n const map = createMap(container, center, zoom)\n \n invalidation.then(() => {\n map.dispose()\n })\n\n function mapMoved () {\n extent.value = currentMapExtent(map)\n }\n \n map.on('moveend', mapMoved)\n map.on('pointerdrag', _.throttle(mapMoved, 35))\n \n function updateExtent (data) { \n map.updateSize() \n }\n \n extent.addEventListener('input', updateExtent)\n return Generators.disposable(container, () => {\n extent.removeEventListener('input', updateExtent)\n })\n}","pinned":false,"hidden":false,"mode":"ojs"},{"id":50,"value":"currentMapExtent = function (map) {\n const extent = map.getView().calculateExtent(map.getSize())\n const transformedExtent = ol.proj.transformExtent(extent, 'EPSG:3857', 'EPSG:4326')\n return transformedExtent\n}","pinned":false,"hidden":false,"mode":"ojs"},{"id":12,"value":"function createMap (target, center, zoom = 10) {\n const map = new ol.Map({\n layers: [\n new ol.layer.Tile({\n source: new ol.source.XYZ({\n url: 'https://server.arcgisonline.com/ArcGIS/rest/services/World_Topo_Map/MapServer/tile/{z}/{y}/{x}',\n maxZoom: 19\n }) \n })\n ],\n target,\n view: new ol.View({\n center: ol.proj.fromLonLat(center),\n zoom\n })\n })\n \n target.value = map\n \n return map\n}","pinned":false,"hidden":false,"mode":"ojs"},{"id":2008,"value":"square = (c) => svg`\n`","pinned":false,"hidden":false,"mode":"ojs"},{"id":1675,"value":"## Constants","pinned":false,"hidden":false,"mode":"md"},{"id":993,"value":"defaultManifestUri = 'https://cdm21033.contentdm.oclc.org/iiif/info/krt/2891/manifest.json'","pinned":false,"hidden":false,"mode":"ojs"},{"id":391,"value":"mapTileSize = 256","pinned":false,"hidden":false,"mode":"ojs"},{"id":78,"value":"zoom = 16","pinned":false,"hidden":false,"mode":"ojs"},{"id":542,"value":"style = html``","pinned":false,"hidden":false,"mode":"ojs"},{"id":627,"value":"## Imports","pinned":false,"hidden":false,"mode":"md"},{"id":1925,"value":"import {selectUri, selectImageUri, selectMap} from '@bertspaan/georeferenced-map-selector'","pinned":false,"hidden":false,"mode":"ojs"},{"id":11,"value":"ol = {\n // OpenLayers doesn’t publish a build to npm. :(\n const ol = await require('https://openlayers.org/en/v6.4.3/build/ol.js').catch(() => window.ol)\n \n if (!ol.css) {\n ol.css = document.head.appendChild(html``)\n }\n \n return ol\n}","pinned":false,"hidden":false,"mode":"ojs"},{"id":1871,"value":"// Lodash\n_ = require('lodash@4')","pinned":false,"hidden":false,"mode":"ojs"},{"id":31,"value":"import { View } from '@mbostock/synchronized-views'","pinned":false,"hidden":false,"mode":"ojs"},{"id":1822,"value":"centroid = import('https://cdn.skypack.dev/@turf/centroid@6.5.0?min')","pinned":false,"hidden":false,"mode":"ojs"},{"id":38,"value":"d3 = require('d3@6', 'd3-tile@1', 'd3-geo@2')","pinned":false,"hidden":false,"mode":"ojs"},{"id":1006,"value":"iiifParser = import('@allmaps/iiif-parser@1.0.0-alpha.16')","pinned":false,"hidden":false,"mode":"ojs"},{"id":1108,"value":"transform = import(\"https://cdn.skypack.dev/@allmaps/transform@1.0.0-beta.6\")","pinned":false,"hidden":false,"mode":"ojs"}],"files":"$W31","stdlib":"1","titling":"auto"}