2d:null 2e:["$","title",null,{"children":"H3 Radius Lookup | Nick Rabinowitz | Observable"}] 33:[] 31:{"id":"89ca45a375fd7a90","slug":"h3-radius-lookup","title":"H3 Radius Lookup","thumbnail":"f3c014d706e8e8e3fb8b087aaac0e6632794ed1d0f95fa43015713994a49864e","access_level":"public","create_time":"$D2019-07-16T16:08:18.319Z","update_time":"$D2023-04-10T23:58:20.176Z","view_time":null,"first_public_time":"$D2019-07-16T16:44:13.733Z","fork":false,"stars":11,"starred":false,"owner":{"type":"team","id":"121dc539a6e3e282","login":"nrabinowitz","name":"Nick Rabinowitz","avatar_url":"https://avatars-next.observableusercontent.com/af324aa7e7df8e450fdb6d331ddc6b2d2c5bb804c04b52a174bc6e0db88872e8","tier":"starter_2024"},"version":279,"publish_version":null,"role":null,"authored":false,"authors":[{"type":"individual","id":"8eeacd6e693d83a2","login":"nrabinowitz","name":"Nick Rabinowitz","avatar_url":"https://avatars-next.observableusercontent.com/af324aa7e7df8e450fdb6d331ddc6b2d2c5bb804c04b52a174bc6e0db88872e8","tier":null}],"members":[{"type":"individual","id":"8eeacd6e693d83a2","login":"nrabinowitz","name":"Nick Rabinowitz","avatar_url":"https://avatars-next.observableusercontent.com/af324aa7e7df8e450fdb6d331ddc6b2d2c5bb804c04b52a174bc6e0db88872e8","tier":null,"role":"editor"}],"comments":[],"custom_thumbnail":false,"trashed":false,"lapsed":null,"subscribed":null,"forks":45,"collection":{"id":"5b5f0aac05a68be5","slug":"h3-tutorial","title":"H3 Tutorials","owner":{"id":"121dc539a6e3e282","login":"nrabinowitz","name":"Nick Rabinowitz"}},"type":"notebook","body":{"title":"H3 Radius Lookup","cells":[{"id":0,"value":"md`# H3 Radius Lookup\n\nYou can use H3 for an efficient radius lookup, as long as you're willing to approximate the circle as a k-ring of hexagons (roughly, a large hexagonal shape). This is much faster than a true search by Haversine distance, but less accurate.\n`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":106,"value":"viewof mapView = {\n let container = html`

`;\n yield container;\n \n const center = {\n lng: -122.25,\n lat: 37.7923539\n };\n \n let map = new mapboxgl.Map({\n container: container,\n center: [center.lng, center.lat],\n zoom: 9,\n interactive: true,\n doubleClickZoom: false,\n style: 'mapbox://styles/mapbox/light-v9'\n });\n \n // Set up view values on load\n map.on('load', () => {\n container.value = {map, center};\n container.dispatchEvent(new CustomEvent(\"input\"));\n \n map.on(\"dblclick\", e => {\n console.log('clicked');\n container.value.center = e.lngLat;\n container.dispatchEvent(new CustomEvent(\"input\"));\n });\n });\n \n invalidation.then(() => map.remove());\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":138,"value":"{\n const {map, center} = mapView;\n \n // Layer rendering logic\n renderMapLayer({\n map,\n id: 'bart',\n data: bartStations,\n type: 'circle',\n paint: {\n 'circle-color': 'darkblue',\n 'circle-radius': 4\n }\n });\n renderMapLayer({\n map,\n id: 'kring',\n data: geojson2h3.h3SetToFeature(kRingIndexes(center)),\n type: 'fill',\n paint: {\n 'fill-color': 'red',\n 'fill-opacity': 0.4\n }\n });\n renderMapLayer({\n map,\n id: 'true-circle',\n data: makeCircle([center.lng, center.lat], searchRadiusKm, {units: 'kilometers'}),\n type: 'line',\n paint: {\n 'line-color': 'green',\n 'line-opacity': 0.7\n }\n });\n \n return md`*Center (double-click to set):* ${mapView.center.lat}, ${mapView.center.lng}`;\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":78,"value":"md`## Input`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":42,"value":"viewof res = slider({\n min: 7,\n max: 10,\n step: 1,\n value: 8,\n description:\n \"H3 resolution for lookup. Finer res means more accuracy but more memory usage. Res 8 is roughly a few city blocks in size.\"\n})","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":59,"value":"viewof searchRadiusKm = slider({\n min: 0.5,\n max: 10,\n step: 0.5,\n value: 4,\n description:\n \"Search radius in km\"\n})","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":257,"value":"viewof radiusMethod = radio({\n description: 'Grid radius calculation method',\n options: [\n { label: 'Edge Length', value: 'edge' },\n { label: 'Cell Area', value: 'area' },\n ],\n value: 'edge'\n})","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":177,"value":"{\n const h3Results = new Set(kRingResults(mapView.center));\n const distResults = new Set(haversineResults(mapView.center));\n const results = [...new Set([...h3Results, ...distResults])]\n .map(feature => ({\n name: feature.properties.name,\n // Color depending on which result sets they're in\n color: h3Results.has(feature) && distResults.has(feature) ? 'black' :\n h3Results.has(feature) ? 'darkred' : 'green'\n }))\n .sort((a, b) => a.color > b.color ? 1 : -1);\n \n return html`\n

Results

in circle but not k-ring / in k-ring but not circle

${result.name}

\n `;\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":28,"value":"md`## Logic`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":32,"value":"md`### K-Ring Lookup\n\nTo use H3 for the radius lookup, you need to index the points of interest by H3 index. If you want this to be efficient, you'd be better off indexing all the points ahead of time.`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":37,"value":"lookupMap = bartStations.features.reduce((map, feature) => {\n // Make a map like {[hexagon]: [id, id, ...]}\n const [lon, lat] = feature.geometry.coordinates;\n const h3Index = h3.latLngToCell(lat, lon, res);\n if (!map[h3Index]) map[h3Index] = [];\n map[h3Index].push(feature);\n return map;\n}, {})","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":48,"value":"md`To search, index your search location and get all the H3 indexes within some radius. The functions below demonstrate two methods to go from real-world radius (e.g. meters) to grid radius - one based on edge length, and one based on cell area.`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":50,"value":"function kRingResults(searchLocation) {\n const lookupIndexes = kRingIndexes(searchLocation);\n // Find all points of interest in the k-ring\n return lookupIndexes.reduce((output, h3Index) => [...output, ...(lookupMap[h3Index] || [])], []);\n}","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":266,"value":"kRingIndexes = radiusMethod === 'edge' ? kRingIndexesEdge : kRingIndexesArea","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":117,"value":"/**\n * Calculate the indexes within the radius based on average cell edge length\n */\nfunction kRingIndexesEdge(searchLocation, pad = 0) {\n const origin = h3.latLngToCell(searchLocation.lat, searchLocation.lng, res);\n // Transform the radius from km to grid distance\n const radius = Math.floor(searchRadiusKm / (h3.getHexagonEdgeLengthAvg(res, h3.UNITS.km) * 2)) + pad;\n return h3.gridDisk(origin, radius);\n}","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":261,"value":"/**\n * Calculate the indexes within the radius based on the search area\n */\nfunction kRingIndexesArea(searchLocation) {\n const origin = h3.latLngToCell(searchLocation.lat, searchLocation.lng, res);\n const originArea = h3.cellArea(origin, h3.UNITS.km2);\n const searchArea = Math.PI * searchRadiusKm * searchRadiusKm;\n\n let radius = 0;\n let diskArea = originArea;\n\n while (diskArea < searchArea) {\n radius++;\n const cellCount = 3 * radius * (radius + 1) + 1;\n diskArea = cellCount * originArea;\n }\n \n return h3.gridDisk(origin, radius);\n}","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":191,"value":"md`### Distance Lookup\n\nOne naive alternative is to check every point by Haversine distance, and find those within the radius. This is more accurate, but slower in many cases - it's \\`O(points)\\` instead of \\`O(hexagons)\\`, and the Haversine calculation is relatively slow compared to H3 indexing and lookup.`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":196,"value":"function haversineResults(searchLocation) {\n return bartStations.features.filter(\n feature => haversineDistance(\n [searchLocation.lng, searchLocation.lat],\n feature.geometry.coordinates,\n {units: 'kilometers'}\n ) < searchRadiusKm\n );\n}","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":16,"value":"md`## Data\nBART station locations in GeoJSON format. Source: [bart.gov](https://www.bart.gov/schedules/developers/geo)`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":23,"value":"bartStations = d3Fetch.json('https://gist.githubusercontent.com/nrabinowitz/d3a5ca3e3e40727595dd137b65058c76/raw/8f1a3e30113472404feebc288e83688a6d5cf33d/bart.json')","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":6,"value":"md`## Dependencies`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":8,"value":"h3 = require('h3-js@4.1.0')","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":10,"value":"d3Fetch = require('d3-fetch')","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":12,"value":"geojson2h3 = require('https://bundle.run/geojson2h3@1.0.1')","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":100,"value":"mapboxgl = {\n let mapboxgl = await require('mapbox-gl@0.43.0');\n mapboxgl.accessToken = mapboxApiToken;\n return mapboxgl;\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":157,"value":"makeCircle = {\n const module = await require('https://bundle.run/@turf/circle@6.0.1');\n return module.default;\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":201,"value":"haversineDistance = {\n const module = await require('https://bundle.run/@turf/distance@6.0.1');\n return module.default;\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":93,"value":"import {renderMapLayer} from \"@nrabinowitz/mapbox-utils\"","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":85,"value":"import {slider, radio} from \"@jashkenas/inputs\"","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":98,"value":"import {mapboxApiToken} from '@nrabinowitz/mapbox-token'","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":95,"value":"// CSS import required for the Mapbox map\nhtml``","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"}],"files":"$W33","stdlib":"1","titling":"auto"}} 32:"$31:body"