Published
Edited
May 8, 2021
1 fork
2 stars
known_kdtree_1d_notBalanced = generateKdTreeFromArray(_.cloneDeep(knownArray_1d));
known_kdtree_1d_pseudoBalanced = generateKdTreeFromArray(pseudoSelectionSortForKdTree(_.cloneDeep(knownArray_1d)));
known_kdtree_1d_balancedByMedian = generateKdTreeFromArray(selectionSortForKdTree(_.cloneDeep(knownArray_1d)));
known_kdtree_2d_notBalanced = generateKdTreeFromArray(_.cloneDeep(knownArray_2d));
known_kdtree_2d_pseudoBalanced = generateKdTreeFromArray(pseudoSelectionSortForKdTree(_.cloneDeep(knownArray_2d)))
known_kdtree_2d_balancedByMedian = generateKdTreeFromArray(selectionSortForKdTree(_.cloneDeep(knownArray_2d)))
known_kdtree_3d = generateKdTreeFromArray(_.cloneDeep(knownArray_3d));
known_kdtree_3d_pseudoBalanced = generateKdTreeFromArray(pseudoSelectionSortForKdTree(_.cloneDeep(knownArray_3d)));
known_kdtree_3d_balancedByMedian = generateKdTreeFromArray(selectionSortForKdTree(_.cloneDeep(knownArray_3d)));
kdNearestNeighborsInRange(known_kdtree_1d_balancedByMedian, [13], 3).map(d => knownArray_1d[d])
kdNearestNeighborsInRange(known_kdtree_2d_pseudoBalanced, [4,3], 2).map(d => knownArray_2d[d])
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;
}
function generateKdTreeFromArray(in_array){
if(in_array.length < 1){
return [];
}
const numDims = in_array[0].key.length;
const kdtree = Array.from(in_array).map(d => {d.leftIdx = -1; d.rightIdx = -1; return d;});
// As root is at index 0, continue setting up the rest starting from index 1
for(let newItmIdx = 1; newItmIdx < in_array.length; ++newItmIdx){
let depth = 0;
let curIdx = 0;
while(curIdx < kdtree.length){
const curDim = depth % numDims;
if(kdtree[newItmIdx].key[curDim] < kdtree[curIdx].key[curDim]){
if(kdtree[curIdx].leftIdx == -1){
kdtree[curIdx].leftIdx = newItmIdx;
break;
}
curIdx = kdtree[curIdx].leftIdx;
}else{
if(kdtree[curIdx].rightIdx == -1){
kdtree[curIdx].rightIdx = newItmIdx;
break;
}
curIdx = kdtree[curIdx].rightIdx;
}
}
}
return kdtree;
}
function selectionSortForKdTree(in_array){
if(in_array.length < 1){
return in_array;
}
const numDims = in_array[0].key.length;
// One by one move boundary of unsorted subarray
for (let i = 0; i < in_array.length - 1; ++i){
// Find a central element in unsorted array
const dim = i % numDims;
for (let j = i+1; j < in_array.length - 1; ++j){
for(let k = i+1; k < in_array.length - 1 - j; ++k){
if( in_array[k+1].key[dim] < in_array[k].key[dim] ){
const tempkth = in_array[k];
in_array[k] = in_array[k+1];
in_array[k+1] = tempkth;
}
}
}
const mididx = Math.floor((in_array.length - i - 1) * 0.5) + i;
// Swap the found minimum element with the first element
const temp = in_array[mididx];
in_array[mididx] = in_array[i];
in_array[i] = temp;
}
return in_array;
}
function pseudoSelectionSortForKdTree(in_array){
if(in_array.length < 1){
return in_array;
}
const numDims = in_array[0].key.length;
// One by one move boundary of unsorted subarray
for (let i = 0; i < in_array.length - 1; ++i){
// Find a central element in unsorted array
const dim = i % numDims;
let sum = 0;
let mididx = 0;
for (let j = i+1; j < in_array.length; j++){
sum += in_array[j].key[dim];
const mean = sum / (j + 1);
if( Math.abs(in_array[j].key[dim] - mean) < Math.abs(in_array[mididx].key[dim] - mean) ){
mididx = j;
}
}
// Swap the found minimum element with the first element
const temp = in_array[mididx];
in_array[mididx] = in_array[i];
in_array[i] = temp;
}
return in_array;
}
function util_calcSquaredDistance(in_p, in_q){
if(in_p.length != in_q.length){
console.log("dimensions does not match : ", in_p, " : ", in_q);
}
let sqrSum = 0;
for(let dim = 0; dim < in_p.length; ++dim){
sqrSum += (in_p[dim] - in_q[dim]) * (in_p[dim] - in_q[dim]);
}
return sqrSum;
}
randomArray_1d = Array(10).fill(1).map((d,i) => ({key: [Math.floor(Math.random() * 10)], value: String.fromCharCode(65 + i)}) )
knownArray_1d = [[3], [17], [13], [6], [9], [2], [10]].map((d,i) => ({key: d, value: String.fromCharCode(65 + i)}) )
knownArray_2d = [[2,3], [4,2], [4,5],[3,3], [1,5], [4,4]].map((d,i) => ({key: d, value: String.fromCharCode(65 + i)}) )
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)}) )
_ = require("lodash")
Purpose-built for displays of data
Observable is your go-to platform for exploring data and creating expressive data visualizations. Use reactive JavaScript notebooks for prototyping and a collaborative canvas for visual data exploration and dashboard creation.
