Monday, July 04, 2011

Spatial Hash in Javascript, for 2D.

var SpatialHash = function(cellSize) {
this.idx = {};
this.cellSize = cellSize;
}

SpatialHash.prototype.insert = function(x, y, obj) {
var cell = [];
var keys = this.keys(x,y);
for(var i in keys) {
var key = keys[i];
if(key in this.idx) {
cell = this.idx[key];
} else {
this.idx[key] = cell;
}
if(cell.indexOf(obj) == -1)
cell.push(obj);
}
}

SpatialHash.prototype.query = function(x, y) {
var key = this.key(x, y);
if(this.idx[key] != undefined)
return this.idx[key];
return [];
}

SpatialHash.prototype.keys = function (x, y) {
var o = this.cellSize / 2;
return [this.key(x-o, y+0),
this.key(x-0, y+0),
this.key(x+o, y+0),
this.key(x-o, y+o),
this.key(x-0, y+o),
this.key(x+o, y+o),
this.key(x-o, y-o),
this.key(x-0, y-o),
this.key(x+o, y-o)];
}

SpatialHash.prototype.key = function(x, y) {
var cellSize = this.cellSize;
x = Math.floor(x/cellSize)*cellSize;
y = Math.floor(y/cellSize)*cellSize;
return x.toString() + ":" + y.toString();
}

3 comments:

Anonymous said...

Thanks for bring oarsome. Can you maek a 3d version?

Anonymous said...

would be interesting to see a comparison of how different hash functions perform

ExpertVs said...

This looks great! Sorry to bother, but I was wonderingif you have a working example\demo of this? I'm new to the whole Javscript development thing, and while I can just about follow this code, making that leap into an application is proving tricky!
Thanks in advance!:)

Popular Posts