2d:null 2e:["$","title",null,{"children":"Geometry Tools | Brendan Ratter | Observable"}] 33:T5c9,md` ## 2D Geometry TODO: Should we use tuples or objects to represent points instead of an argument list? Distance and angle formulas for 2D geometries. For use in quadtree nearest neighbor searches, each implementation must implement the interface below (written in TypeScript for clarity). Note that for different 2d coordinate systems (lat/lng, polar, etc.), the x and y can be repurposed as required as long as the functions on quadtree or other consuming modules are called the same way. ~~~ts /** * Geometry interface. */ interface Geom { /** * Calculate the distance between two points. * @param x1 x-coord of start point * @param y1 y-coord of start point * @param x2 x-coord of end point * @param y2 y-coord of end point */ distance: (x1: number, y1: number, x2: number, y2: number) => number /** * Calculate the minimum distance between a point and a shape defined by two opposite corners. * This will be a rectangle in caretesian coordinates, but will be other shapes in other systems. * @param x1 x-coord of the comparison point * @param y1 y-coord of the comparison point * @param x1 x-coord of the first corner of the shape * @param y1 y-coord of the first corner of the shape * @param x2 x-coord of the second corner of the shape * @param y2 y-coord of the second corner of the shape */ distanceRect: (x: number, y: number, x1: number, x2: number, y1: number, y2: number) => number } ~~~ `34:T433,/** * Cartesian coordinate system. */ cartesian = { function cartesian() { return { distance: function(x1, y1, x2, y2) { return Math.sqrt(Math.pow(x1 - x2, 2) + Math.pow(y1 - y2, 2)); }, distanceRect: function(x, y, x1, y1, x2, y2) { const dx1 = x - x1, dx2 = x - x2, dy1 = y - y1, dy2 = y - y2; if (dx1 * dx2 < 0) { // x is between x1 and x2, if not inside completely, then distance to nearest x // y also between y1 and y2, therefore inside the rectangle if (dy1 * dy2 < 0) return 0; return Math.min(Math.abs(dy1), Math.abs(dy2)); } // y is between y1 and y2, but not inside, so distance to nearest y if (dy1 * dy2 < 0) return Math.min(Math.abs(dx1), Math.abs(dx2)); // Otherwise distance to nearest corner return this.distance( x, y, Math.abs(dx1) < Math.abs(dx2) ? x1 : x2, Math.abs(dy1) < Math.abs(dy2) ? y1 : y2 ); } }; } return cartesian; }35:T12d0,/** * Haversine coordinate system for distances on the surface of a sphere. * To keep consistency with cartesian x/y coordinate order, coord pairs are ordered with longitude first. * Requires lng/lat to be measured in degrees with lng +/-180 and lat +/-90. * Useful resource: http://www.movable-type.co.uk/scripts/latlong.html * * TODO: Should r be an extra (optional) argument to dist and distRect to override the setting? */ haversine = { // Function for the minimum difference in longitudes accounting for wrapping around +/-180 deg const minLngDifference = dLng => Math.min(Math.abs(dLng), Math.abs(360 - dLng)); function haversine(radius) { let r = radius || haversine.earth.km; return { /** * Get or set the radius of the sphere. */ radius: function(_) { return arguments.length ? ((r = _), this) : r; }, /** * Initial bearing (in degrees) from point 1 to point 2. * Unlike euclidean systems, the bearing changess througout the path. */ bearing: function(lngDeg1, latDeg1, lngDeg2, latDeg2, inRad) { const dLng = degToRad(lngDeg2 - lngDeg1); const lat1 = degToRad(latDeg1); const lat2 = degToRad(latDeg2); const y = Math.sin(dLng) * Math.cos(lat2); const x = Math.cos(lat1) * Math.sin(lat2) - Math.sin(lat1) * Math.cos(lat2) * Math.cos(dLng); const rad = Math.atan2(y, x); return inRad ? rad : radToDeg(rad); }, /** * Angular distance between two points in degrees. * If the final argument is passed as true, will output the angle in radians instead. */ distanceAng: function(lngDeg1, latDeg1, lngDeg2, latDeg2, inRad) { const lat1 = degToRad(latDeg1); const lat2 = degToRad(latDeg2); const dLat = degToRad(latDeg1 - latDeg2); const dLng = degToRad(lngDeg1 - lngDeg2); const a = Math.sin(dLat / 2) * Math.sin(dLat / 2) + Math.cos(lat1) * Math.cos(lat2) * Math.sin(dLng / 2) * Math.sin(dLng / 2); const rad = 2 * Math.atan2(Math.sqrt(a), Math.sqrt(1 - a)); return inRad ? rad : radToDeg(rad); }, /** * Haversine distance between two points on the surface of a sphere. */ distance: function(lngDeg1, latDeg1, lngDeg2, latDeg2) { return r * this.distanceAng(lngDeg1, latDeg1, lngDeg2, latDeg2, true); }, /** * Closest distance between a point and a lat/lng "rectangle". * Angles are kept in degrees to pass to other methods. */ distanceRect: function(lng, lat, lng1, lat1, lng2, lat2) { const dLng1 = lng - lng1, dLng2 = lng - lng2, dLat1 = lat - lat1, dLat2 = lat - lat2; // 1. If within lng bounds of the rectangle... if (dLng1 * dLng2 < 0) { // 1a. If also within lat bounds, then completely, contained and disance is 0 if (dLat1 * dLat2 < 0) return 0; // 1b. Otherwise, the closest point's lat and input point's lng will be the nearest // point on the rectangle. This works because longitude lines are great circles. return this.distance( lng, lat, lng, Math.abs(dLat1) < Math.abs(dLat2) ? lat1 : lat2 ); } // 2. If outside lng, but inside lat bounds, we need to find the closest point on the // lng line (which is a great circle). As per site above known as cross-track distance. // The start-end bearing can be simplified as bearing along a lng line is always 0 or 180. if (dLat1 * dLat2 < 0) { const lngDiff = minLngDifference(dLng1) < minLngDifference(dLng2) ? lng1 : lng2; const angleStPt = this.distanceAng(lngDiff, lat1, lng, lat, true); const bearingStPt = this.bearing(lngDiff, lat1, lng, lat, true); const bearingStEnd = lat1 > lat2 ? Math.PI : 0; return ( r * Math.asin( Math.sin(angleStPt) * Math.sin(bearingStPt - bearingStEnd) ) ); } // 3. If outside both lat and lng, then find the closest corner to compare. // Lat is just the abs difference, but lng has to be tested both directions around the sphere. return this.distance( lng, lat, minLngDifference(dLng1) < minLngDifference(dLng2) ? lng1 : lng2, Math.abs(dLat1) < Math.abs(dLat2) ? lat1 : lat2 ); } }; } // Static variables for Earth's radius in km/mi // See: https://en.wikipedia.org/wiki/Earth_radius#Mean_radius haversine.earth = { km: 6371.0088, mi: 3958.7613 }; return haversine; }36:T604,// Some tests for the haversine distance formula { const geoData = [ { name: 'chicago', lat: 41.8781, lng: -87.6298 }, { name: 'los angeles', lat: 34.0522, lng: -118.2437 }, { name: 'sydney', lat: -33.8688, lng: 151.2093 }, { name: 'london', lat: 51.5074, lng: -0.1278 }, { name: 'singapore', lat: 1.3521, lng: 103.8198 }, { name: 'miami', lat: 25.7617, lng: -80.1918 } ]; const [chi, la, syd, lon, sin, mia] = geoData; const f = n => Math.round(n, 0); const hav = haversine(); return md` Testing the haversine distance formulae: * Fully contained (Sin to Lon-Syd): ${f( hav.distanceRect(sin.lng, sin.lat, lon.lng, lon.lat, syd.lng, syd.lat) )} km * Within lng bounds (Lon to Chi-Sin): ${f( hav.distanceRect(lon.lng, lon.lat, chi.lng, chi.lat, sin.lng, sin.lat) )} km * Within lat bounds (LA to Lon-Sin): ${f( hav.distanceRect(la.lng, la.lat, lon.lng, lon.lat, sin.lng, sin.lat) )} km * Outside closest to a point (Lon to LA-Chi): ${f( hav.distanceRect(lon.lng, lon.lat, la.lng, la.lat, chi.lng, chi.lat) )} km * Outside closest to point, but wrapping 180 deg (Syd to LA-Chi): ${f( hav.distanceRect(syd.lng, syd.lat, la.lng, la.lat, chi.lng, chi.lat) )} km * Outside closeest to a non-point corner (Mia to LA-Chi): ${f( hav.distanceRect(mia.lng, mia.lat, la.lng, la.lat, chi.lng, chi.lat) )} km * As above, but with Earth radius in mi: ${f( hav .radius(haversine.earth.mi) .distanceRect(mia.lng, mia.lat, la.lng, la.lat, chi.lng, chi.lat) )} mi `; }37:T3a95,/** * Quadtree constructor function. * Returns the quadtree execution function. * * TODO: Consider flattening the results array when multiple datapoints exist at each node to avoid results[i].data[0] access in most cases * TODO: Add copy method * TODO: Consider promoting x1, y1, x2, y2 from nodes, and x, y, from leaf nodes to the results object (will have to be called x and y even though may not be that on the data) * TODO: Work out how to perform the actions on reset during traversal to reduce overhead * for large trees that change (could even be lazily evaluated get a getter so not preloaded on flatNodes) * Could adapt the recursion by only calculating the x/y values when added to the workStack * TODO: When data cannot be resolved properly, it fails but sometimes just doesn't create the root node... should test this on data load to give a more meaningul error * TODO: Consider not polluting the nodes with the reset data, but this requires another map, * which doesn't seem worth it unless the previous TODO can be resolved * TODO: Consider replacing the incrementing node id with this (See Jeff Ward's answer): * https://stackoverflow.com/questions/105034/create-guid-uuid-in-javascript */ quadtree = function quadtree(data, x, y) { // ---------------------------------------- // Internal variables // ---------------------------------------- // Create the underlying d3-quadtree instance const qt = d3Quadtree.quadtree(data, x, y); // Base info for merging with kNearest output const baseInfo = { distance: undefined, visited: false, selected: false }; // Internal variables let k = Infinity, r = Infinity, geom = cartesian(), countDuplicates = false, excludeMode = 'self', changed = true, idCounter = 0; // ---------------------------------------- // Inner function // ---------------------------------------- /** * Inner quadtree execution function. */ function quadtree(testData) { return testData.map(d => quadtree.kNearest(d)); } // ---------------------------------------- // Public API // ---------------------------------------- /** * Get/set the "x" accessor. * Repurposed as necessary for alternative coordinate systems. */ quadtree.x = function(_) { return arguments.length ? (qt.x(_), this) : qt.x(); }; /** * Get/set the "y" accessor. * Repurposed as necessary for alternative coordinate systems. */ quadtree.y = function(_) { return arguments.length ? (qt.y(_), this) : qt.y(); }; /** * Get/set the number of nearest neighbors to find for kNearest searches. * Set to Infinity (default) to select all neighbors. */ quadtree.k = function(_) { return arguments.length ? ((k = _), this) : k; }; /** * Get/set the maximum radius (in same units as the coordinate system) to return matches. * Set to Infinity (default) to not impose a radius restriction. */ quadtree.r = function(_) { return arguments.length ? ((r = _), this) : r; }; /** * Get/set the coordinate system for the instance. * The coordinate system must be an object that implements the Geom interface. */ quadtree.geometry = function(_) { return arguments.length ? ((geom = _), this) : geom; }; /** * Get/set the count duplicates flag. * Defaults to false, but if set to true, will count all the datapoints at a given node * against the count `k`. */ quadtree.countDuplicates = function(_) { return arguments.length ? ((countDuplicates = _), this) : countDuplicates; }; /** * Get set the exclude mode. * Valid values are 'self' (default), 'all', and 'none', which have the follow effect on the results: * - self: Excludes items from the data array that === the passed test point * - all: Excludes all items at the same node if any one of them === the test point * - none: Retains all items */ quadtree.excludeMode = function(_) { return arguments.length ? ((excludeMode = _), this) : excludeMode; }; /** * Get/set the extent that the quadtree covers. * See d3-quadtree documentation for detail. */ quadtree.extent = function(_) { changed = true; return arguments.length ? (qt.extent(_), this) : qt.extent(); }; /** * Expand the extent to cover the specified point. * See d3-quadtree documentation for detail. */ quadtree.cover = function(x, y) { changed = true; qt.cover(x, y); return this; }; /** * Return the root node of the quadtree. */ quadtree.root = () => qt.root(); /** * Return an array of all data in the quadtree. */ quadtree.data = () => qt.data(); /** * Return the total count of data in the quadtree. */ quadtree.size = () => qt.size(); /** * Add the specified datum to the quadtree, expanding the extent as required. * See d3-quadtree documentation for detail. */ quadtree.add = function(_) { changed = true; qt.add(_); return this; }; /** * Add the specified array of data to the quadtree, expanding the extent as required. * See d3-quadtree documentation for detail. */ quadtree.addAll = function(_) { changed = true; qt.addAll(_); return this; }; /** * Remove the specified datum from the quadtree. * See d3-quadtree documentation for detail. */ quadtree.remove = function(_) { changed = true; qt.remove(_); return this; }; /** * Remove the specified array of data from the quadtree. * See d3-quadtree documentation for detail. */ quadtree.removeAll = function(_) { changed = true; qt.removeAll(_); return this; }; /** * Get a flat array of all the nodes in the tree in preorder. * If leafOnly is true, will only return leaf nodes. */ quadtree.nodes = function(leafOnly) { const nodes = []; reset(); qt.visit(node => { if (!leafOnly || node.leaf) nodes.push(node); }); return nodes; }; /* * Visit each node in pre-order calling the callback for each. * If the callback returns `true`, the node's children will not be visited. * See d3-quadtree documentation for callback detail. */ quadtree.visit = callback => qt.visit(callback); /* * Visit each node in post-order calling the callback for each. * See d3-quadtree documentation for callback detail. */ quadtree.visitAfter = callback => qt.visitAfter(callback); /** * Find the nearest node to the passed point. * If the optional radius is provided it will override the current setting. */ quadtree.find = function(testPoint, rOverride) { const find = quadtree.kNearest(testPoint, null, { k: 1, r: rOverride || r }); return find.length ? find[0] : undefined; }; /** * Return a result object array for the k-nearest nodes to the provided point. * The content of the result object is outlined below in the resToNode() definition. * Result will be based on the preset k, r, and data values in the quadtree object. * If 'full' or 'scanned' is passed as the final argument will augment the array with a * "nodes" member containing an array of result objects. The "extra" member will identify * the type of extra nodes (full or scanned). Full outputs all nodes, scanned only * outputs scanned nodes (much smaller for large trees). Full can be converted to scanned * with full.filter(n => n.scanned), so both are not required. * * @param testPoint The test point with the same x and y accessors as the input data * @param extra Optional ability to return a larger set of comparison points, accepts null/undef, 'full', or 'scanned' */ quadtree.kNearest = function(testPoint, extra, override) { // Reset the node coordinates if the tree has changed reset(); // Setup stacks for passing to the recursive function const root = qt.root(), workStack = [root], resultStack = [], infoMap = new Map(), x = qt.x()(testPoint), y = qt.y()(testPoint); infoMap.addFn = infoMapAdd; // Execute the recursion and map the nodes // The following does not work in Edge // kNearestRecursive({x, y, k, r, workStack, resultStack, infoMap, testPoint, ...override}); kNearestRecursive( Object.assign( { x, y, k, r, workStack, resultStack, infoMap, testPoint }, override ) ); const result = resultStack.map(node => resultFromNode(node, infoMap)); // If extras are to be provided, then add them to the result // Scanned will be minimal overhead as we already have the Map, but full // requires a complete traversal, which is expensive for large trees if (extra && (extra === 'full' || extra === 'scanned')) { const nodes = extra === 'full' ? quadtree.nodes() : Array.from(infoMap.keys()); result.extra = extra; result.nodes = nodes.map(n => resultFromNode(n, infoMap)); } return result; }; // ---------------------------------------- // Private functions // ---------------------------------------- /** * Produces a result object given a node and the infoMap for the current iteration. * The result is an object with the following members: * * leaf: boolean Is the node a leaf node * data: data[] (leaf nodes only) An array of input data, will be undefined for non-leaf nodes, but guaranteed to hold at least one item for leaves * count: number (leaf nodes only) The count of items i nthe data array for leaf nodes * distance: number The distance to the comparison point * scanned: boolean Has the node been scanned and its distance calculated * visited: boolean Has the node been popped off the end of the stack and processed, is a subset of scanned * selected: boolean Has the node been selected into the result, is a subset of visited and will only ever be true for leaf node * node: Node Reference to the node object from the tree, with depth/location additions */ function resultFromNode(node, infoMap) { const info = infoMap.get(node.id); const item = { node, id: node.id, leaf: node.leaf, depth: node.depth, scanned: !!info }; return Object.assign( { node, id: node.id, leaf: node.leaf, depth: node.depth, scanned: !!info }, baseInfo, info ); } /** * Helper function to add an item to the infoMap as it is being built in the recursive function. */ function infoMapAdd(x, y, node) { const result = { distance: node.leaf ? geom.distance(x, y, qt.x()(node.data), qt.y()(node.data)) : geom.distanceRect(x, y, node.x1, node.y1, node.x2, node.y2) }; this.set(node.id, result); return result; } /** * Helper function to extract and flatten the data from a node based on the exclude mode setting. */ function dataFromNode(node, testPoint) { const data = [], excludeMode = 'none'; let next = node; do { if (excludeMode !== 'none' && next.data === testPoint) { if (excludeMode === 'self') continue; return []; } data.push(next.data); } while ((next = next.next)); return data; } /** * Update the status of all nodes before running operations. * Also adds a unique id to the nodes for infoMap keys and data joins. */ function reset() { // Don't reset if unchanged if (!changed) return; // Add the depth to the root node, then visit all nodes to add coords qt.root().depth = 0; qt.visit((node, x1, y1, x2, y2) => { //Add a unique index to each of the nodes if it hasn't already been processed if (!node.id) node.id = idCounter++; // Update the position and type of the nodes node.x1 = x1; node.y1 = y1; node.x2 = x2; node.y2 = y2; node.leaf = !node.length; // If the node has the specified child, set its depth to 1 + it's parent. // This works because the preorder traversal guarantees the parent has been visited first. for (let i = 0; i < 4; i++) { if (node[i]) node[i].depth = node.depth + 1; } }); // Reset the changed flag changed = false; } /** * Recursively work through the nodes to find the nearest k. * Having k/r in the options allows override of the settings if a method requires it. */ function kNearestRecursive(opts, count) { const { x, y, k, r, workStack, resultStack, infoMap, testPoint } = opts; count = count || 0; // 1. Scan and sort // Sort the children according to their distance // But first step to "scan" nodes being sorted to calculate distance if not already processed // Also have to process a single node if there is only one in the stack if (workStack.length === 1) { if (!infoMap.has(workStack[0].id)) infoMap.addFn(x, y, workStack[0], infoMap); } else { workStack.sort((a, b) => { const ia = infoMap.get(a.id) || infoMap.addFn(x, y, a, infoMap); const ib = infoMap.get(b.id) || infoMap.addFn(x, y, b, infoMap); return ib.distance - ia.distance; }); } // 2. Select leaf nodes // Add the nearest leaf nodes if any exist in the current iteration, looping in reverse order for (let i = workStack.length - 1; i >= 0; i--) { const node = workStack[i], info = infoMap.get(node.id); // Break if not a leaf node if (!node.leaf) break; // Pop the leaf node and mark as visited workStack.pop(); info.visited = true; // If a leaf node but out of radius or the same as the current item // do not add to the results and rollover to flush leaf nodes if (info.distance > r) continue; // Process data, then skip if there is none to add, otherwise set the count and add to the stack const data = dataFromNode(node, testPoint); if (!data.length) continue; // Add the leaf node and its additional properties resultStack.push(node); info.selected = true; info.data = data; info.count = data.length; count += countDuplicates ? data.length : 1; // Exit If the queue is filled if (count >= k) break; } // 3. Recurse // Check if we have enough points (skip if not using), if we've run out, exiting if so if (count >= k || workStack.length === 0) return; // Add child nodes to the stack and recurse, exiting if node is out of radius // as there is no need to iterate over nodes that are too far away const curNode = workStack.pop(); const curInfo = infoMap.get(curNode.id); curInfo.visited = true; if (curInfo.distance > r) return; curNode.forEach(n => workStack.push(n)); kNearestRecursive(opts, count); } // Finally return the inner quadtree function return quadtree; }38:T69a,{ const geoData = [ { name: 'chicago', lat: 41.8781, lng: -87.6298 }, { name: 'los angeles', lat: 34.0522, lng: -118.2437 }, { name: 'sydney', lat: -33.8688, lng: 151.2093 }, { name: 'london', lat: 51.5074, lng: -0.1278 }, { name: 'singapore', lat: 1.3521, lng: 103.8198 }, { name: 'miami', lat: 25.7617, lng: -80.1918 }, { name: 'london2', lat: 51.5074, lng: -0.1278 } ]; const [chi, la, syd, lon, sin, mia, lon2] = geoData; const qt = quadtree() .x(d => d.lng) .y(d => d.lat) .addAll(geoData) .remove(lon) .remove(lon2) .removeAll([la]) .add(lon) .add(lon) .add(lon2) .k(2) .r(10000) .geometry(haversine()); const ex = qt.extent(); const find = qt.find(la); const knn = qt.kNearest(lon, 'full'); return md` Testing the quadtree extension using the geodata. * The extent is [${ex[0][0]}, ${ex[0][1]}], [${ex[1][0]}, ${ex[1][1]}]. * The nearest point to LA is: ${find.data[0].name} [${find.data[0].lng}, ${ find.data[0].lat }]. * Finding ${qt.k()} nearest neighbors within max radius of ${qt.r()}, ${ knn.length }/${qt.k()} were found. * There are ${knn.nodes.length} nodes (max depth of ${Math.max( ...knn.nodes.map(n => n.depth) )}), ${knn.nodes.filter(n => n.scanned).length} were scanned, and ${ knn.nodes.filter(n => n.visited).length } were visited. The nearest neighbors, in order, are: ${knn .map( d => `* ${d.data[0].name} [${d.data[0].lng}, ${ d.data[0].lat }], at a distance of ${Math.round(d.distance, 0)}km)` ) .join('\n')} The loaded data is: ${qt .data() .map(d => `* ${d.name} [${d.lng}, ${d.lat}]`) .join('\n')} `; }39:[] 31:{"id":"b5e40bbf8533a6cf","slug":"geometry-tools","title":"Geometry Tools","thumbnail":"57fd794b684dc81ad1a8c107e59a78f1ee37b76ad332950c74b66c48fa985e71","access_level":"public","create_time":"$D2019-11-02T18:50:59.740Z","update_time":"$D2020-04-21T07:48:03.298Z","view_time":null,"first_public_time":"$D2019-11-06T01:41:44.234Z","fork":false,"stars":0,"starred":false,"owner":{"type":"team","id":"ac1efc54e02edbcb","login":"bratter","name":"Brendan Ratter","avatar_url":"https://avatars-next.observableusercontent.com/72254c56b9894f2113524282297d982abcaaa6b50b1fb4d9e19658e6572e58d6","tier":"starter_2024"},"version":752,"publish_version":752,"role":null,"authored":false,"authors":[{"type":"individual","id":"832b3a3dcd4c23fe","login":"bratter","name":"Brendan Ratter","avatar_url":"https://avatars-next.observableusercontent.com/72254c56b9894f2113524282297d982abcaaa6b50b1fb4d9e19658e6572e58d6","tier":null}],"members":[{"type":"individual","id":"832b3a3dcd4c23fe","login":"bratter","name":"Brendan Ratter","avatar_url":"https://avatars-next.observableusercontent.com/72254c56b9894f2113524282297d982abcaaa6b50b1fb4d9e19658e6572e58d6","tier":null,"role":"editor"}],"comments":[],"custom_thumbnail":false,"trashed":false,"lapsed":null,"subscribed":null,"forks":0,"collection":null,"type":"notebook","body":{"title":"Geometry Tools","cells":[{"id":0,"value":"md`\n# Geometry Tools\nD3-oriented extentions for geometry topics, including a higher-level quadtree module. \n`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":7,"value":"$33","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":11,"value":"md`\n### Cartesian\nCreate a new cartesian system with \\`cartesian()\\`.\n`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":50,"value":"$34","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":22,"value":"md`\n### Haversine\nCreate a new haversine system for lat/lng coordinates on a globe with \\`haversine(radius)\\` where \\`radius\\` is the radius of the sphere. If no radius is provided, will default to Earth's radius in km. Earth's radius in k and mi are available on the static \\`haversine.earth.km\\` and \\`haversine.earth.mi\\` respectively.\n`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":77,"value":"$35","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":88,"value":"degToRad = deg => (deg * Math.PI) / 180","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":91,"value":"radToDeg = rad => (rad * 180) / Math.PI","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":106,"value":"$36","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":274,"value":"md`\n## Quadtree\nExtension of d3-quadtree to incorporate additional methods, particularly k nearest neighbors, and the ability to use different 2D geometries. Inspired by Inspired by http://bl.ocks.org/llb4ll/8709363. Note that other 2D indexing methods are possible, see https://github.com/salsita/geo-tree for an alternative.\n`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":280,"value":"$37","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":308,"value":"$38","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":323,"value":"d3Quadtree = require('d3-quadtree')","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"}],"files":"$W39","stdlib":"1","titling":"auto"}} 32:"$31:body"