The Problem of Continuously Inserting Large Area Rectangles

[zs782306174]

If the insert method is used to continuously insert a large area of rectangles, and each rectangle overlaps with four sub nodes, the insert method will be infinitely recursive

[timohausmann]

I see that insert runs very often but not infinitely, can you provide an example? It takes a long time to insert 100 objects that fill all nodes, maybe you could lower the max_levels or in that case the Quadtree isn't the right choice.

var amount = 100;
var width = 800;
var height = 600;
var max_objects = 10;
var max_levels = 4;

var myTree = new Quadtree({
	x: 0,
	y: 0,
	width: width,
	height: height
}, max_objects, max_levels);

var start = window.performance.now();
for(var i=0; i<amount;i++) {
	myTree.insert({
		x: 50,
		y: 50,
		width: width-100,
		height: height-100,
	});
}
var end = window.performance.now();
var time = end - start;
console.log('done inserting', amount, 'objects in', time, 'ms');