2e:null 2f:["$","title",null,{"children":"H3 Radius Lookup - optimized - measure each ring | Zachary Marois | Observable"}] 34:T4d9,{ const {map, center} = mapView; const searchRadiusKm = searchRadiusMiles*1.60934; const alertLocation = { type: "FeatureCollection", features: [{ type: "Feature", geometry: {type: "Point", coordinates: [25.954223817201044,24.940714411344228,0]}, id: "alertLocation" }] } // Layer rendering logic renderMapLayer({ map, id: 'alertLocation', data: alertLocation, type: 'circle', paint: { 'circle-color': 'darkblue', 'circle-radius': 4 } }); renderMapLayer({ map, id: 'bart', data: bartStations, type: 'circle', paint: { 'circle-color': 'darkblue', 'circle-radius': 4 } }); renderMapLayer({ map, id: 'kring', data: geojson2h3.h3SetToMultiPolygonFeature(kRingIndexes(center)), type: 'fill', paint: { 'fill-color': 'red', 'fill-opacity': 0.4 } }); renderMapLayer({ map, id: 'true-circle', data: makeCircle([center.lng, center.lat], searchRadiusKm, {units: 'kilometers'}), type: 'line', paint: { 'line-color': 'green', 'line-opacity': 0.7 } }); return md`*Center (double-click to set):* ${mapView.center.lat}, ${mapView.center.lng}`; }35:T7e5,function kRingIndexes(searchLocation, pad = 0) { const searchRadiusKm = searchRadiusMiles*1.60934; const origin = h3.geoToH3(searchLocation.lat, searchLocation.lng, res); const searchingFor = h3.geoToH3(24.940714411344228,25.954223817201044, res) console.log(searchingFor); // While the h3 lib has an edge length calculation, due to distortion, it isn't right at all locations // Further, calculating the apothem from the edge needs more-complex algebra because of the curvature of the earth // So, we can just measure what the apothem and edge are at the origin. Each hexagon is slightly different (again, distortion), // So we take the largest apothem for use by the inscription, and the smallest edge for the circumscription const a = Math.max(...h3.kRingDistances(origin, 1)[1].map( oneAwayH3 => h3.pointDist(h3.h3ToGeo(oneAwayH3), h3.h3ToGeo(origin), h3.UNITS.km) / 2)) const e = Math.min(...h3.kRingDistances(origin, 2)[2].map( twoAwayH3 => h3.pointDist(h3.h3ToGeo(twoAwayH3), h3.h3ToGeo(origin), h3.UNITS.km) / 3)) const radiusIfEven = Math.ceil(((searchRadiusKm - e) / e) / (3.0/2.0)); const radiusIfOdd = Math.ceil(((((searchRadiusKm - e) / e) * 2.0) + 1.0)/3.0); const inscriptionRadius = Math.ceil((searchRadiusKm - a)/(2.0*a)); const circumscriptionRadius = (radiusIfEven % 2 === 0 ? radiusIfEven : radiusIfOdd) + 1; const kRingDistances = h3.kRingDistances(origin, circumscriptionRadius); // We know that every h3 in the inscription are within range const h3sFromInscription = kRingDistances.slice(0, inscriptionRadius + 1).flat(); // And the rest are somewhere in the inscription, just need to filter for the ones actually within range const h3s = h3sFromInscription.concat(kRingDistances.slice(inscriptionRadius + 1).map(hexRing => hexRing.filter(newH3 => { const h3Center = h3.h3ToGeo(newH3); return h3.pointDist([searchLocation.lat, searchLocation.lng], h3Center, h3.UNITS.km) < (searchRadiusKm + e); })).flat()); return h3s; }36:[] 32:{"id":"fc4065940de57775","slug":"h3-radius-lookup-optimized-measure-each-ring","title":"H3 Radius Lookup - optimized - measure each ring","thumbnail":"2cc8233c5d95f58262afd881d3cc7d344b34170fd48f08a2042988191b66e56a","access_level":"public","create_time":"$D2022-06-20T13:30:21.410Z","update_time":"$D2022-12-22T20:16:17.557Z","view_time":null,"first_public_time":"$D2022-06-20T13:51:31.349Z","fork":{"id":"c8bbbe83dffafd9e","slug":"h3-radius-lookup-measure-each-ring","title":"H3 Radius Lookup - measure each ring","owner":{"id":"1f321ffc655999e5","login":"zmarois-dataminr","name":"Zachary Marois"}},"stars":1,"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":337,"publish_version":null,"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":2,"collection":null,"type":"notebook","body":{"title":"H3 Radius Lookup - optimized - measure each ring","cells":[{"id":0,"value":"md`# H3 Radius Lookup - optimized - measure each ring\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":"$34","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: 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 searchRadiusMiles = slider({\n min: 0.5,\n max: 50,\n step: 0.5,\n value: 4,\n description:\n \"Search radius in miles\"\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":"$35","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: 'miles'}\n ) < searchRadiusMiles\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 =\nd3Fetch.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":"$W36","stdlib":"1","titling":"auto"}} 33:"$32:body"