2e:null 2f:["$","title",null,{"children":"H3 Radius Lookup using Figueira's approach | Zachary Marois | Observable"}] 34:[] 32:{"id":"86456ac7102f4dc0","slug":"h3-radius-lookup-using-figueiras-approach","title":"H3 Radius Lookup using Figueira's approach","thumbnail":"60ded8a3a965ce60b717706d3aaca69e1c92f983c3985fa2af15338becd434b5","access_level":"public","create_time":"$D2022-06-17T18:19:22.820Z","update_time":"$D2022-08-10T18:22:40.408Z","view_time":null,"first_public_time":"$D2022-06-17T18:27:24.964Z","fork":{"id":"89ca45a375fd7a90","slug":"h3-radius-lookup","title":"H3 Radius Lookup","owner":{"id":"121dc539a6e3e282","login":"nrabinowitz","name":"Nick Rabinowitz"}},"stars":0,"starred":false,"owner":{"type":"team","id":"1f321ffc655999e5","login":"zmarois-dataminr","name":"Zachary Marois","avatar_url":"https://avatars-next.observableusercontent.com/6df080f601b371922c9f3caa530ebca0e3d1bbb980e103ef76d75d8799bdbe4e","tier":"starter_2024"},"version":274,"publish_version":274,"role":null,"authored":false,"authors":[{"type":"individual","id":"d57311dbac705ede","login":"zmarois-dataminr","name":"Zachary Marois","avatar_url":"https://avatars-next.observableusercontent.com/6df080f601b371922c9f3caa530ebca0e3d1bbb980e103ef76d75d8799bdbe4e","tier":null}],"members":[{"type":"individual","id":"d57311dbac705ede","login":"zmarois-dataminr","name":"Zachary Marois","avatar_url":"https://avatars-next.observableusercontent.com/6df080f601b371922c9f3caa530ebca0e3d1bbb980e103ef76d75d8799bdbe4e","tier":null,"role":"editor"}],"comments":[],"custom_thumbnail":false,"trashed":false,"lapsed":null,"subscribed":null,"forks":0,"collection":null,"type":"notebook","body":{"title":"H3 Radius Lookup using Figueira's approach","cells":[{"id":0,"value":"md`# H3 Radius Lookup using Figueira's approach\n\nhttps://towardsdatascience.com/fast-geospatial-indexing-with-h3-90e862482585\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: -9.150034151022265,\n lat: 38.72531266045836\n };\n \n let map = new mapboxgl.Map({\n container: container,\n center: [center.lng, center.lat],\n zoom: 15,\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 let {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.h3SetToMultiPolygonFeature(kRingIndexes(center)),\n type: 'fill',\n paint: {\n 'fill-color': 'blue',\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: 12,\n step: 1,\n value: 11,\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.01,\n max: 1,\n step: 0.01,\n value: 0.03,\n description:\n \"Search radius in km\"\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.geoToH3(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. You can use the \\`h3.edgeLength\\` function to get the approximate radius of a cell at your current resolution.`","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":117,"value":"function kRingIndexes(searchLocation, pad = 0) {\n const origin = h3.geoToH3(searchLocation.lat, searchLocation.lng, res);\n // Transform the radius from km to grid distance\n const radius = 1 + Math.round(searchRadiusKm / h3.edgeLength(res, h3.UNITS.km)) + pad;\n return h3.kRing(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@3.7.2')","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} 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":"$W34","stdlib":"1","titling":"auto"}} 33:"$32:body"