quadtree-js 1.1.3 performance test

Quadtree 1.1.3 stored objects on parent nodes if they could not fully fit in a single subnode. This left alot of objects on high level nodes every time an object overlapped into two or more nodes. As a result, the retrieved candidates included alot of nodes that are actually far away.

Quadtree 1.2 fixes this by not storing objects on parent nodes, but only on leaf nodes (the lowest level).

Heart of the test code:

var amount = 10000;
var myObjects = [];
for(var i=0; i<amount;i++) {
	myObjects.push({
	x: randMinMax(0, 800-maxObjectSize),
	y: randMinMax(0, 600-maxObjectSize),
	width: randMinMax(4, maxObjectSize),
	height: randMinMax(4, maxObjectSize)
	});
}

//time measure starts here
var start = window.performance.now();

var myTree = new Quadtree({
	x: 0,
	y: 0,
	width: 800,
	height: 600
}, 10, 4);

for(var i=0; i<amount;i++) {
  myTree.insert(myObjects[i]);
}
var candidates = myTree.retrieve(myCursor);

//time measure ends here
var end = window.performance.now();
var time = end - start;

To see the full example code please check the page source or visit GitHub.