quadtree-js 1.2.0 performance test

Quadtree 1.2 now stores objects exclusively on leaf nodes. Objects, that overlap into multiple subnodes are now referenced in each matching subnode instead of their parent node. This drastically reduces the collision candidates. Prior to 1.2, overlapping objects were stored in parent nodes (1.1.3 Demo).

Because objects may now be present in multiple nodes, nodes will split rather soon (depending on the max_objects value, default = 10 objects per node).

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++) {
  myOldTree.insert(myObjects[i]);
}
var candidates = myOldTree.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.