以下のデモでは、単にkd-treeによる検索だけではなく、kd-tree構築の速度と、総当たりの場合の速度の比較もできるようにしてあります。10,000点ぐらいだと、その差を顕著に感じることが出来るでしょう。100,000点ぐらいあると、感動的なほど差が出ます。それだけあってもkd-treeの方はほぼ1ms以内に検索が終わるのですから(ただしこの場合、デモの実行に合計10秒以上かかるので注意!)。

ただし、treeの構築にはやはりそれなりの時間と記憶容量が必要なこともわかります。10,000点で500ms以上。この場合に総当たりで検索にかかる時間は10msほどなので、およそ60回検索すれば「元が取れる」ことになります。

divide & conquer マンセーといったところでしょうか。

Dan the Binary Searcher

Point = function(x, y){
    this.x = x;
    this.y = y;
};

Point.prototype = {
    toString:function(){
        return '(' + this.x + ', ' + this.y + ')';
    },
    dsquare:function(p){
        var dx = this.x - p.x;
        var dy = this.y - p.y;
        return dx*dx + dy*dy;
    },
    distance:function(p){
        return Math.sqrt(this.dsquare(p));
    },
    within:function(p, d){
        return this.dsquare(p) < d * d;
    },
    sorted_by_distance:function(ary){
        var result = ary.slice();
        var self = this;
        result.sort(function(a, b){
            return self.dsquare(a) - self.dsquare(b);
        });
        return result;
    },
    nearest:function(ary){
        var result = ary[0];
        var l = ary.length;
        if (l < 2) return result;
        var md = this.dsquare(ary[0]);
        for (var i = 0; i < l; i++){
            var d = this.dsquare(ary[i]);
            if (d < md){
                result = ary[i];
                md = d;
            }
        }
        return result;
    },
    closer:function(a, b){
        return this.dsquare(a) < this.dsquare(b) ? a : b;
    }
};

pts2kdtree = function(ary, depth){
    if (ary.length == 0) return null;
    if (ary.length == 1) return ary[0];
    var result = {};
    var axis = depth % 2 ? 'y' : 'x';
    var copy = ary.slice();
    copy.sort(function(a, b){ return a[axis] - b[axis] });
    var mid = copy.length >>> 1;
    result.mid = copy[mid];
    result.head = arguments.callee(copy.slice(0, mid), depth+1);
    result.tail = arguments.callee(copy.slice(mid+1),  depth+1);
    return result;
};

kdtree_find = function(qt, pt, depth){
    var axis = depth % 2 ? 'y' : 'x';
    if (!qt) return null;
    if (qt instanceof Point) return qt;
    var leaf;
    if (pt[axis] < qt.mid[axis]){
        leaf = qt.head ? qt.head instanceof Point ? qt.head
               : arguments.callee(qt.head, pt, depth+1)
               : arguments.callee(qt.tail, pt, depth+1);
        if (qt.head && qt.tail 
            && pt.dsquare(leaf) > Math.pow(pt[axis] - qt.mid[axis], 2))
            leaf = pt.closer(leaf, arguments.callee(qt.tail, pt, depth+1));
    }else{
        leaf = qt.tail ? qt.tail instanceof Point ? qt.tail
               : arguments.callee(qt.tail, pt, depth+1)
               : arguments.callee(qt.head, pt, depth+1);
        if (qt.tail && qt.head
            && pt.dsquare(leaf) > Math.pow(pt[axis] - qt.mid[axis], 2))
            leaf = pt.closer(leaf, arguments.callee(qt.head, pt, depth+1));
    }
    return pt.closer(qt.mid, leaf);
};

randpoints = function(n, xmax, ymax){
    var result = [];
    for (var i = 0; i < n; i++){
        result[i] = new Point(
            Math.floor(Math.random()*xmax), Math.floor(Math.random()*ymax)
        );
    }
    return result;
};

points2str = function(pts){
    var result = [];
    for (var i = 0, l = pts.length; i < l; i++){
        result[i] = '(' + pts[i].x + ', ' + pts[i].y + ')';
    }
    return result.join(', ');
}