JAVASCRIPT   11

kdtree.js

Guest on 10th May 2021 05:03:51 PM

  1. /*
  2. K-d tree implementation in Javascript
  3. Thomas Grill, 2011
  4. http://grrrr.org
  5.  
  6. Licensed under the MIT License
  7.  
  8. Version 0.1: original implementation
  9.  
  10. Originally by Matteo Dell'Amico
  11. http://code.activestate.com/recipes/577497-kd-tree-for-nearest-neighbor-search-in-a-k-dimensi
  12.  
  13. --
  14.  
  15. A tree for nearest neighbor search in a k-dimensional space.
  16.  
  17. For information about the implementation, see
  18. http://en.wikipedia.org/wiki/Kd-tree
  19.  
  20. Usage:
  21. t = KDTree(objects)
  22. {point, label, distance} = t.nearest_neighbor(destination)
  23. */
  24.  
  25. function square_distance(a, b) {
  26.     var s = 0.,d;
  27.     for(var i = 0; i < a.length; ++i) {
  28.         d = a[i] - b[i];
  29.         s += d * d;
  30.     }
  31.     return s;
  32. }
  33.  
  34. function build_tree(objects,axis) {
  35.     if(objects == null || !objects.length) return null;
  36.  
  37.     qsort(objects,null,null,function(a,b) { return a[0][axis] < b[0][axis]; });
  38.    
  39.     var median_idx = Math.floor(objects.length/2);
  40.     var median_point = objects[median_idx][0];
  41.     var median_label = objects[median_idx][1];
  42.     var k = median_point.length;
  43.  
  44.     var next_axis = (axis + 1) % k;
  45.     // return node
  46.     return {
  47.         point: median_point,
  48.         axis: axis,
  49.         label: median_label,
  50.         left: build_tree(objects.slice(0,median_idx), next_axis),
  51.         right: build_tree(objects.slice(median_idx + 1), next_axis)
  52.     };
  53. }
  54.  
  55. function KDTree(objects)
  56. {
  57.     this.root = build_tree(objects,0);
  58. }
  59.  
  60. KDTree.prototype = new Object();
  61.  
  62. KDTree.prototype.nearest_neighbor = function(destination)
  63. {
  64.     var best = [null, null, Infinity];
  65.     // state of search: best point found, its label,
  66.     // lowest squared distance
  67.  
  68.     recursive_search = function(here) {
  69.         if(here == null) return;
  70.        
  71.         var point = here.point;
  72.         var axis = here.axis;
  73.         var label = here.label;
  74.         var left = here.left;
  75.         var right = here.right;
  76.  
  77.         var here_sd = square_distance(point, destination);
  78.         if(here_sd < best[2])
  79.             best = [point, label, here_sd];
  80.  
  81.         var diff = destination[axis] - point[axis];
  82.         var close,away;
  83.         if(diff <= 0) {
  84.             close = left;
  85.             away = right;
  86.         }
  87.         else {
  88.             close = right;
  89.             away = left;
  90.         }
  91.            
  92.         recursive_search(close);
  93.         if(diff*diff < best[2])
  94.             recursive_search(away);
  95.     }
  96.  
  97.     recursive_search(this.root);
  98.     return {point: best[0], label: best[1], distance: Math.sqrt(best[2])};
  99. }

Raw Paste


Login or Register to edit or fork this paste. It's free.