2e:null 2f:["$","title",null,{"children":"K-d Trees with non-recursive functions and array based implementation | Chathura Jayalath | Observable"}] 34:T4e3,function kdNearestNeighborsInRange(in_kdTreeArray, in_point, in_radius){ if(in_kdTreeArray.length < 1){ return []; } const numDims = in_kdTreeArray[0].key.length; const retVal = []; const stack = [ [0, 0] ]; // stack contains elementIdx and depth const sqrSearchDist = in_radius * in_radius; while(stack.length > 0){ const [curIdx, depth] = stack.pop(); const curSqrDist = util_calcSquaredDistance(in_kdTreeArray[curIdx].key, in_point); if(curSqrDist <= sqrSearchDist){ retVal.push(curIdx); } const dim = depth % numDims; let goodSide = -1; let badSide = -1; if(in_point[dim] < in_kdTreeArray[curIdx].key[dim]){ goodSide = in_kdTreeArray[curIdx].leftIdx; badSide = in_kdTreeArray[curIdx].rightIdx; }else{ goodSide = in_kdTreeArray[curIdx].rightIdx; badSide = in_kdTreeArray[curIdx].leftIdx; } if(badSide != -1){ const sqrBadSideDist = (in_point[dim] - in_kdTreeArray[curIdx].key[dim]) * (in_point[dim] - in_kdTreeArray[curIdx].key[dim]); if(sqrBadSideDist < sqrSearchDist){ stack.push([badSide, depth + 1]); } } if(goodSide != -1){ stack.push([goodSide, depth + 1]); } } return retVal; }35:[] 32:{"id":"eb71392a21952e03","slug":"k-d-trees-non-recursive-array-based","title":"K-d Trees with non-recursive functions and array based implementation","thumbnail":"8bb1082b7015e89ed033f7110c7bf76c40c8b4e3c87c231fbc5c9d537f62a3d7","access_level":"public","create_time":"$D2021-05-08T03:37:20.665Z","update_time":"$D2021-05-14T05:36:24.915Z","view_time":null,"first_public_time":"$D2021-05-08T16:58:21.715Z","has_unpublished_edits":null,"fork":false,"stars":2,"starred":false,"owner":{"type":"team","id":"faa67bfd1359f951","login":"deamonpog","name":"Chathura Jayalath","avatar_url":"https://avatars-next.observableusercontent.com/1bc13a0724d43e94c26de301357a2897d22e5c4e01e7f160ea8fba232ef861f1","tier":"starter_2024"},"version":376,"publish_version":376,"role":null,"authored":false,"authors":[{"type":"individual","id":"5fe81dea2f61079a","login":"deamonpog","name":"Chathura Jayalath","avatar_url":"https://avatars-next.observableusercontent.com/1bc13a0724d43e94c26de301357a2897d22e5c4e01e7f160ea8fba232ef861f1","tier":null}],"members":[{"type":"individual","id":"5fe81dea2f61079a","login":"deamonpog","name":"Chathura Jayalath","avatar_url":"https://avatars-next.observableusercontent.com/1bc13a0724d43e94c26de301357a2897d22e5c4e01e7f160ea8fba232ef861f1","tier":null,"role":"editor"}],"comments":[],"custom_thumbnail":false,"trashed":false,"lapsed":null,"subscribed":null,"forks":2,"collection":null,"type":"notebook","body":{"title":"K-d Trees with non-recursive functions and array based implementation","cells":[{"id":0,"value":"md`# K-d Trees with non-recursive functions and array based implementation`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":366,"value":"md`This implementation could be used for any k dimensions and the payload is clearly separated.`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":349,"value":"md`---\n## Examples\n---`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":336,"value":"md`k-d Tree Array Generation Examples`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":280,"value":"known_kdtree_1d_notBalanced = generateKdTreeFromArray(_.cloneDeep(knownArray_1d));","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":286,"value":"known_kdtree_1d_pseudoBalanced = generateKdTreeFromArray(pseudoSelectionSortForKdTree(_.cloneDeep(knownArray_1d)));","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":62,"value":"known_kdtree_1d_balancedByMedian = generateKdTreeFromArray(selectionSortForKdTree(_.cloneDeep(knownArray_1d)));","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":65,"value":"known_kdtree_2d_notBalanced = generateKdTreeFromArray(_.cloneDeep(knownArray_2d));","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":276,"value":"known_kdtree_2d_pseudoBalanced = generateKdTreeFromArray(pseudoSelectionSortForKdTree(_.cloneDeep(knownArray_2d)))","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":230,"value":"known_kdtree_2d_balancedByMedian = generateKdTreeFromArray(selectionSortForKdTree(_.cloneDeep(knownArray_2d)))","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":66,"value":"known_kdtree_3d = generateKdTreeFromArray(_.cloneDeep(knownArray_3d));","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":272,"value":"known_kdtree_3d_pseudoBalanced = generateKdTreeFromArray(pseudoSelectionSortForKdTree(_.cloneDeep(knownArray_3d)));","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":268,"value":"known_kdtree_3d_balancedByMedian = generateKdTreeFromArray(selectionSortForKdTree(_.cloneDeep(knownArray_3d)));","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":352,"value":"md`Search function examples`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":189,"value":"kdNearestNeighborsInRange(known_kdtree_1d_balancedByMedian, [13], 3).map(d => knownArray_1d[d])","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":208,"value":"kdNearestNeighborsInRange(known_kdtree_2d_pseudoBalanced, [4,3], 2).map(d => knownArray_2d[d])","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":32,"value":"md`---\n## k-d Tree Search Functions\n---`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":356,"value":"md`Following funcitons : Returns an array of indexes that fit the given criteria`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":172,"value":"$34","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":345,"value":"md`---\n## k-d Tree Generation Funcitons\n---`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":56,"value":"function generateKdTreeFromArray(in_array){\n if(in_array.length < 1){\n return [];\n }\n const numDims = in_array[0].key.length;\n const kdtree = Array.from(in_array).map(d => {d.leftIdx = -1; d.rightIdx = -1; return d;});\n // As root is at index 0, continue setting up the rest starting from index 1\n for(let newItmIdx = 1; newItmIdx < in_array.length; ++newItmIdx){\n let depth = 0;\n let curIdx = 0;\n while(curIdx < kdtree.length){\n const curDim = depth % numDims;\n if(kdtree[newItmIdx].key[curDim] < kdtree[curIdx].key[curDim]){\n if(kdtree[curIdx].leftIdx == -1){\n kdtree[curIdx].leftIdx = newItmIdx;\n break;\n }\n curIdx = kdtree[curIdx].leftIdx;\n }else{\n if(kdtree[curIdx].rightIdx == -1){\n kdtree[curIdx].rightIdx = newItmIdx;\n break;\n }\n curIdx = kdtree[curIdx].rightIdx;\n }\n }\n }\n return kdtree;\n}","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":304,"value":"md`---\n## Sorting Algorithms for sorting input arrays\n---`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":257,"value":"function selectionSortForKdTree(in_array){\n if(in_array.length < 1){\n return in_array;\n }\n \n const numDims = in_array[0].key.length;\n // One by one move boundary of unsorted subarray \n for (let i = 0; i < in_array.length - 1; ++i){ \n \n // Find a central element in unsorted array \n const dim = i % numDims;\n \n for (let j = i+1; j < in_array.length - 1; ++j){\n for(let k = i+1; k < in_array.length - 1 - j; ++k){\n if( in_array[k+1].key[dim] < in_array[k].key[dim] ){\n const tempkth = in_array[k];\n in_array[k] = in_array[k+1];\n in_array[k+1] = tempkth;\n }\n }\n }\n \n const mididx = Math.floor((in_array.length - i - 1) * 0.5) + i;\n\n // Swap the found minimum element with the first element \n const temp = in_array[mididx];\n in_array[mididx] = in_array[i];\n in_array[i] = temp;\n }\n return in_array;\n}","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":218,"value":"function pseudoSelectionSortForKdTree(in_array){\n if(in_array.length < 1){\n return in_array;\n }\n \n const numDims = in_array[0].key.length;\n // One by one move boundary of unsorted subarray \n for (let i = 0; i < in_array.length - 1; ++i){ \n \n // Find a central element in unsorted array \n const dim = i % numDims;\n let sum = 0;\n let mididx = 0;\n \n for (let j = i+1; j < in_array.length; j++){\n sum += in_array[j].key[dim];\n const mean = sum / (j + 1);\n if( Math.abs(in_array[j].key[dim] - mean) < Math.abs(in_array[mididx].key[dim] - mean) ){\n mididx = j;\n }\n }\n\n // Swap the found minimum element with the first element \n const temp = in_array[mididx];\n in_array[mididx] = in_array[i];\n in_array[i] = temp;\n }\n return in_array;\n}","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":27,"value":"md`---\n## Utility Functions\n---`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":179,"value":"function util_calcSquaredDistance(in_p, in_q){\n if(in_p.length != in_q.length){\n console.log(\"dimensions does not match : \", in_p, \" : \", in_q);\n }\n let sqrSum = 0;\n for(let dim = 0; dim < in_p.length; ++dim){\n sqrSum += (in_p[dim] - in_q[dim]) * (in_p[dim] - in_q[dim]);\n }\n return sqrSum;\n}","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":313,"value":"md`---\n## Test Arrays for Examples\n---`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":243,"value":"randomArray_1d = Array(10).fill(1).map((d,i) => ({key: [Math.floor(Math.random() * 10)], value: String.fromCharCode(65 + i)}) )","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":13,"value":"knownArray_1d = [[3], [17], [13], [6], [9], [2], [10]].map((d,i) => ({key: d, value: String.fromCharCode(65 + i)}) )","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":5,"value":"knownArray_2d = [[2,3], [4,2], [4,5],[3,3], [1,5], [4,4]].map((d,i) => ({key: d, value: String.fromCharCode(65 + i)}) )","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":6,"value":"knownArray_3d = [[7, 8, 1], [17, 18, 2], [7, 15, 8], [2, 5, 1], [9, 1, 7], [2, 7, 3], [10, 4, 4]].map((d,i) => ({key: d, value: String.fromCharCode(65 + i)}) )","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":124,"value":"md`---\n## Imported Libraries\n---`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":107,"value":"_ = require(\"lodash\")","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"}],"files":"$W35","stdlib":"1","titling":"auto"}} 33:"$32:body"