2b:null 2c:["$","title",null,{"children":"Web Mercator Tile Visibility | Jake Low | Observable"}] 31:Tc6d,getVisibleTiles = function(projection, zoom) { function getVisibleChildren(x, y, z) { console.log(x, y, z); let visible = false; // Define a projection stream based on the input projection. This stream first does all of // the operations (rotating, clipping, and resampling) that the input projection would do. // Then, any geometries that survive that process (i.e. are visible in the output projection) // get passed on to our custom stream, which just sets `visible = true` if it sees a point. // We'll use this stream to determine if a tile is visible when projected through `projection`. let stream = projection.stream({ point: () => { visible = true; }, lineStart: () => {}, lineEnd: () => {}, polygonStart: () => {}, polygonEnd: () => {} }); // calculate screen-space coordinates of tile (x, y, z) in the `mercator` projection below const extent = mercator.clipExtent(); // we assume that extent is a square, and thus all tiles are also squares const size = (extent[1][0] - extent[0][0]) / (2 ** z); const epsilon = 0.001; const x0 = x * size + epsilon, y0 = y * size + epsilon, x1 = (x + 1) * size - epsilon, y1 = (y + 1) * size - epsilon; const step = Math.min(size, 1); const tile = { type: "Polygon", coordinates: [ [] // Interpolate along each of the four edges of the Mercator polygon. This is a rather // crude way to do interpolation (with a constant step size) but it's easier than the // adaptive resampling that d3 does natively, which is not available to us here since // we're not using a projection. .concat(d3.range(x0, x1 + step / 2, +step).map(x => [x, y0])) .concat(d3.range(y0, y1 + step / 2, +step).map(y => [x1, y])) .concat(d3.range(x1, x0 - step / 2, -step).map(x => [x, y1])) .concat(d3.range(y1, y0 - step / 2, -step).map(y => [x0, y])) // convert this mercator polygon to a spherical polygon on the Earth .map(point => mercator.invert(point)) ], }; // Project the spherical polygon representing the tile by feeding it through the stream. d3.geoStream(tile, stream); // If any point in the tile was visible in the output projection, then our stream will have // received that point via its `point` method and set `visible = true`. if (visible) { if (z < zoom) { // if we're not yet at the desired zoom level, recurse on each of the four sub-tiles let visibleChildren = [] .concat(getVisibleChildren(2 * x, 2 * y, z + 1)) // upper left .concat(getVisibleChildren(2 * x + 1, 2 * y, z + 1)) // upper right .concat(getVisibleChildren(2 * x, 2 * y + 1, z + 1)) // lower left .concat(getVisibleChildren(2 * x + 1, 2 * y + 1, z + 1)) // lower right return visibleChildren; } else { return [tile]; // this tile is visible and is of the desired zoom level } } else { return []; // this tile is not visible } } return getVisibleChildren(0, 0, 0); }32:T524,globeView = { let context; if (this) { context = this; //this.getContext("2d"); context.clearRect(0, 0, size, size); } else { context = DOM.context2d(size, size); d3.select(context.canvas).call(drag); } const path = d3.geoPath(globe, context); context.strokeStyle = 'black'; context.fillStyle = 'black'; context.lineWidth = 1; context.beginPath(), path(sphere), context.fillStyle = "#fff", context.fill(); context.beginPath(), path(land), context.fillStyle = "#000", context.fill(); context.beginPath(), path(graticule), context.strokeStyle = 'rgba(100, 100, 100, 0.25)', context.stroke(); context.beginPath(), path(quads), context.strokeStyle = 'red', context.stroke(); context.beginPath(), path(quads), context.fillStyle = 'rgba(255, 0, 0, 0.25)', context.fill(); context.beginPath(), path(sphere), context.strokeStyle = 'black', context.stroke(); context.strokeStyle = 'yellow'; context.strokeRect(rect.x, rect.y, rect.width, rect.height); // context.fillStyle = 'rgba(0, 0, 0, 0.25)'; // context.fillRect(0, 0, size, rect.y); // context.fillRect(0, rect.y, rect.x, rect.height); // context.fillRect(rect.x + rect.width, rect.y, size, rect.height); // context.fillRect(0, rect.y + rect.height, size, size); return context; }33:T94b,versor = { var acos = Math.acos, asin = Math.asin, atan2 = Math.atan2, cos = Math.cos, max = Math.max, min = Math.min, PI = Math.PI, sin = Math.sin, sqrt = Math.sqrt, radians = PI / 180, degrees = 180 / PI; // Returns the unit quaternion for the given Euler rotation angles [λ, φ, γ]. function versor(e) { var l = e[0] / 2 * radians, sl = sin(l), cl = cos(l), // λ / 2 p = e[1] / 2 * radians, sp = sin(p), cp = cos(p), // φ / 2 g = e[2] / 2 * radians, sg = sin(g), cg = cos(g); // γ / 2 return [ cl * cp * cg + sl * sp * sg, sl * cp * cg - cl * sp * sg, cl * sp * cg + sl * cp * sg, cl * cp * sg - sl * sp * cg ]; } // Returns Cartesian coordinates [x, y, z] given spherical coordinates [λ, φ]. versor.cartesian = function(e) { var l = e[0] * radians, p = e[1] * radians, cp = cos(p); return [cp * cos(l), cp * sin(l), sin(p)]; }; // Returns the Euler rotation angles [λ, φ, γ] for the given quaternion. versor.rotation = function(q) { return [ atan2(2 * (q[0] * q[1] + q[2] * q[3]), 1 - 2 * (q[1] * q[1] + q[2] * q[2])) * degrees, asin(max(-1, min(1, 2 * (q[0] * q[2] - q[3] * q[1])))) * degrees, atan2(2 * (q[0] * q[3] + q[1] * q[2]), 1 - 2 * (q[2] * q[2] + q[3] * q[3])) * degrees ]; }; // Returns the quaternion to rotate between two cartesian points on the sphere. versor.delta = function(v0, v1) { var w = cross(v0, v1), l = sqrt(dot(w, w)); if (!l) return [1, 0, 0, 0]; var t = acos(max(-1, min(1, dot(v0, v1)))) / 2, s = sin(t); // t = θ / 2 return [cos(t), w[2] / l * s, -w[1] / l * s, w[0] / l * s]; }; // Returns the quaternion that represents q0 * q1. versor.multiply = function(q0, q1) { return [ q0[0] * q1[0] - q0[1] * q1[1] - q0[2] * q1[2] - q0[3] * q1[3], q0[0] * q1[1] + q0[1] * q1[0] + q0[2] * q1[3] - q0[3] * q1[2], q0[0] * q1[2] - q0[1] * q1[3] + q0[2] * q1[0] + q0[3] * q1[1], q0[0] * q1[3] + q0[1] * q1[2] - q0[2] * q1[1] + q0[3] * q1[0] ]; }; function cross(v0, v1) { return [ v0[1] * v1[2] - v0[2] * v1[1], v0[2] * v1[0] - v0[0] * v1[2], v0[0] * v1[1] - v0[1] * v1[0] ]; } function dot(v0, v1) { return v0[0] * v1[0] + v0[1] * v1[1] + v0[2] * v1[2]; } return versor; }34:[] 2f:{"id":"9e20563a9b04afd7","slug":"web-mercator-tile-visibility","title":"Web Mercator Tile Visibility","thumbnail":"11ef6c0e29f879ffef7d179d96b8dadd5f2704bae14c1bc7639728ff8df0b829","access_level":"public","create_time":"$D2018-04-16T23:05:47.529Z","update_time":"$D2020-08-25T23:53:18.146Z","view_time":null,"first_public_time":"$D2018-04-25T01:22:11.535Z","fork":true,"stars":50,"starred":false,"owner":{"type":"team","id":"cbb2b32473d3e648","login":"jake-low","name":"Jake Low","avatar_url":"https://avatars-next.observableusercontent.com/fcff7503af57e71a7006d2543ad38643918ba16eb09e01f116b42d94a497c0a0","tier":"starter_2024"},"version":1673,"publish_version":1673,"role":null,"authored":false,"authors":[{"type":"individual","id":"e30eca3d7ea0ab2c","login":"jake-low","name":"Jake Low","avatar_url":"https://avatars-next.observableusercontent.com/fcff7503af57e71a7006d2543ad38643918ba16eb09e01f116b42d94a497c0a0","tier":null}],"members":[{"type":"individual","id":"e30eca3d7ea0ab2c","login":"jake-low","name":"Jake Low","avatar_url":"https://avatars-next.observableusercontent.com/fcff7503af57e71a7006d2543ad38643918ba16eb09e01f116b42d94a497c0a0","tier":null,"role":"editor"}],"comments":[{"id":"edcfbc0b93148189","reply_to_id":null,"content":"\"Click and drag\" is not working.\nAm I missing something trivial ?","create_time":"$D2020-08-25T10:22:27.215Z","update_time":null,"resolved":true,"user":{"type":"individual","id":"68e18af682792012","login":"pbrockmann","name":"Patrick Brockmann","avatar_url":"https://avatars-next.observableusercontent.com/25f3e1483d611e61cc2dc87b5091004972f4ad8dbf4792cd225809597ddb2463","tier":null}},{"id":"620106e533056d59","reply_to_id":"edcfbc0b93148189","content":"Thanks for the report. No, you're not missing anything; I hadn't properly pinned the versions of my d3 dependencies and a recent release (likely d3-drag 2.0.0?) broke dragging. I've pinned d3@5 now which I believe should keep things working in the future.","create_time":"$D2020-08-25T23:45:06.979Z","update_time":null,"resolved":true,"user":{"type":"individual","id":"e30eca3d7ea0ab2c","login":"jake-low","name":"Jake Low","avatar_url":"https://avatars-next.observableusercontent.com/fcff7503af57e71a7006d2543ad38643918ba16eb09e01f116b42d94a497c0a0","tier":null}},{"id":"4b9c1e497d273cd9","reply_to_id":"edcfbc0b93148189","content":"Thanks Jake ! And congratulations for this notebook.","create_time":"$D2020-08-26T14:03:52.303Z","update_time":null,"resolved":true,"user":{"type":"individual","id":"68e18af682792012","login":"pbrockmann","name":"Patrick Brockmann","avatar_url":"https://avatars-next.observableusercontent.com/25f3e1483d611e61cc2dc87b5091004972f4ad8dbf4792cd225809597ddb2463","tier":null}}],"custom_thumbnail":true,"trashed":false,"subscribed":null,"forks":19,"collection":{"id":"9cbebc0d45eec1ae","slug":"maps","title":"Maps","owner":{"id":"f35c755083683fe5","login":"observablehq","name":"Observable"}},"type":"notebook","body":{"title":"Web Mercator Tile Visibility","cells":[{"id":0,"value":"md`# Web Mercator Tile Visibility`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":1581,"value":"md`\nThis notebook demonstrates a method to work out what Web Mercator tiles (also known as [Slippy tiles](https://wiki.openstreetmap.org/wiki/Slippy_map_tilenames)) are visible on an arbitrary map projection _P_. Since slippy tiles are arranged in a [quadtree](https://en.wikipedia.org/wiki/Quadtree), it's possible to traverse tiles recursively to determine visibility. This enables fast visibility detection, even at high zoom levels (where there may be thousands of candidate tiles). Inspired by [Jason Davies' work](https://www.jasondavies.com/maps/tile/) in the same domain.\n\nClick and drag the globe!\n`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":1489,"value":"demo = {\n let demo = DOM.element('div');\n \n demo.appendChild(globeView.canvas);\n demo.appendChild(mercatorView.canvas);\n \n globeView.canvas.style.display = 'inline-block';\n globeView.canvas.style.width = '45%';\n globeView.canvas.style.margin = '5px';\n \n mercatorView.canvas.style.display = 'inline-block';\n mercatorView.canvas.style.width = '45%';\n mercatorView.canvas.style.margin = '5px';\n \n return demo;\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":1221,"value":"viewof scale = {\n let form;\n\n if (this) {\n form = this;\n } else {\n form = html`\n \n `;\n\n form.scale.addEventListener('input', () => {\n mutable globe = mutable globe.scale(300 * form.scale.valueAsNumber);\n });\n }\n\n form.value = form.scale.valueAsNumber;\n\n return form;\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":1329,"value":"viewof zoom = {\n const scaleToZoom = scale => Math.round(2 * Math.log2(scale + 1));\n\n let form;\n\n if (this) {\n form = this;\n\n if (form.auto.checked) {\n form.zoom.value = scaleToZoom(scale);\n }\n\n form.value = form.zoom.valueAsNumber;\n } else {\n form = html`\n \n `;\n\n form.zoom.oninput = () => {\n form.value = form.zoom.valueAsNumber;\n };\n\n form.value = form.zoom.valueAsNumber;\n }\n\n form.auto.oninput = () => {\n form.zoom.disabled = form.auto.checked;\n form.zoom.value = scaleToZoom(scale);\n form.value = form.zoom.valueAsNumber;\n };\n\n return form;\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":1654,"value":"md`\nIn the demo above, the yellow rectangle on the globe is the area of interest; slippy tiles that intersect this area are shown in red. Try dragging the globe to rotate the Earth, adjusting the scale slider (which will zoom in on the globe), or adjusting the zoom slider (which will change the size of the mercator tiles being considered). When \"auto\" is checked, an appropriate zoom level is chosen based on the current scale.\n`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":1659,"value":"md`\nThe heavy lifting here is done in \\`getVisibleTiles\\` (below), which is commented to help explain the process.\n`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":1280,"value":"$31","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":5,"value":"$32","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":285,"value":"mercatorView = {\n let context;\n \n if (this) {\n context = this; //this.getContext(\"2d\");\n context.clearRect(0, 0, size, size);\n } else {\n context = DOM.context2d(size, size);\n }\n \n const path = d3.geoPath(mercator, context);\n \n context.fillStyle = 'black';\n context.strokeStyle = 'black';\n\n context.beginPath(), path(sphere), context.fillStyle = \"#fff\", context.fill();\n context.beginPath(), path(land), context.fillStyle = \"#000\", context.fill();\n context.beginPath(), path(graticule), context.strokeStyle = 'rgba(100, 100, 100, 0.25)', context.stroke();\n \n for (var quad of quads.features) {\n context.beginPath(), path(quad), context.strokeStyle = 'red', context.stroke();\n context.beginPath(), path(quad), context.fillStyle = 'rgba(255, 0, 0, 0.25)', context.fill();\n }\n \n context.beginPath(), path(sphere), context.strokeStyle = 'black', context.stroke();\n\n\n return context;\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":915,"value":"quads = {\n globe.clipExtent([[rect.x, rect.y], [rect.x + rect.width, rect.y + rect.height]]);\n \n let features = getVisibleTiles(globe, zoom)\n .map(geom => turf.feature(geom));\n \n globe.clipExtent([[0, 0], [size, size]]);\n return turf.featureCollection(features);\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":242,"value":"drag = {\n let v0, q0, r0;\n \n function dragstarted() {\n v0 = versor.cartesian(mutable globe.invert(d3.mouse(this)));\n q0 = versor(r0 = mutable globe.rotate());\n }\n \n function dragged() {\n const v1 = versor.cartesian(mutable globe.rotate(r0).invert(d3.mouse(this)));\n const q1 = versor.multiply(q0, versor.delta(v0, v1));\n mutable globe = mutable globe.rotate(versor.rotation(q1));\n }\n \n return d3.drag()\n .on(\"start\", dragstarted)\n .on(\"drag\", dragged);\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":237,"value":"rect = Object({\n x: 1/6 * size,\n y: 2/6 * size,\n width: 4/6 * size,\n height: 2/6 * size,\n})","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":11,"value":"size = 600","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":9,"value":"mutable globe = d3.geoOrthographic()\n .translate([size / 2, size / 2])\n .clipExtent([[0, 0], [size, size]])\n .rotate([-17, -13, 30])\n .precision(0.1)","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":43,"value":"mercator = d3.geoMercator()\n .fitSize([size, size], sphere)\n .clipExtent([[0, 0], [size, size]])","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":688,"value":"graticule = d3.geoGraticule10()","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":590,"value":"sphere = Object({ type: 'Sphere' })","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":20,"value":"land = topojson.feature(world, world.objects.land)","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":16,"value":"world = d3.json(\"https://unpkg.com/world-atlas@1/world/110m.json\")","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":432,"value":"$33","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":18,"value":"topojson = require(\"topojson-client@3\")","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":145,"value":"turf = require(\"@turf/turf@5\")","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":7,"value":"d3 = require(\"d3@5\")","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":743,"value":"pi = Math.PI","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":745,"value":"tau = 2 * Math.PI","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"}],"files":"$W34","stdlib":"1","titling":"auto"}} 30:"$2f:body"