A test and a problem #5
Description
Hi all,
First of all thanks for the code - really useful! :-)
Now I hope there owner is still looking at the issues here.
Below is the test code I am running to simulate moving Line of sight MBRs on an area. And test whether any of these MBRs comprise a point, whose coordinates on the area can be defined via a click.
One strange thing is that after a little while, all areas stop moving. I suspect this has to do with how I run the tree.remove() and tree.insert() methods from within the los.move() method, but if anyone has a clue, I will gladly hear about it!
<!DOCTYPE html>
<html>
<head>
<title>Visual R-tree</title>
<style>
*{margin:0;padding:0;font-family:Arial;}
</style>
</head>
<body>
<canvas id="world" style="display:block;margin:50px auto 0 auto;border:1px solid #eee;" height="400" width="400"></canvas>
<div style="margin:10px auto 0 auto;width:400px;">
<p id="tracked"></p>
<p id="over">0,0</p>
<p id="count"></p>
<p id="draw"></p>
<p id="leaf_drawn"></p>
<p id="non_leaf_drawn"></p>
<p id="frame"></p>
</div>
<script src="rtree.js"></script>
<script>
// http://stackulator.com/rtree/
var world = [400,400];
var tree = new RTree();
// line of sight
var los = function(center,radius){
this.center = center || [];
this.radius = radius || 1;
this.mbr = this.get_mbr();
this.hit = null;
this.velocity = [2,2];
};
los.prototype.get_mbr = function(){
return {
"x":this.center[0] - this.radius,
"y":this.center[1] - this.radius,
"w":this.radius*2,
"h":this.radius*2
};
};
los.prototype.move = function(){
var m = Math;
var self = this;
var removed = tree.remove(
this.mbr,
self
);
//console.log(removed);
if(removed.length == 1) {
this.center = [
(m.random()>0.5) ? this.center[0]+m.random()*this.velocity[0] : this.center[0]-m.random()*this.velocity[0] ,
(m.random()>0.5) ? this.center[1]+m.random()*this.velocity[1] : this.center[1]-m.random()*this.velocity[1]
];
//this.radius = this.radius+(m.random()/10);
tree.insert(
this.get_mbr(),
self
);
}
};
// insert los items into tree
var nb_los = 100;
var my_los;
for( var i=0; i<nb_los; i++ ){
var m = Math;
my_los = new los(
[
m.random()*world[0],
m.random()*world[1]
],
Math.random()*20+8
);
tree.insert(
{
"x":my_los.mbr.x,
"y":my_los.mbr.y,
"w":my_los.mbr.w,
"h":my_los.mbr.h
},
my_los
);
}
console.log(tree.get_tree());
var tracked_point = [200,200];
var frame = 0;
var count = 0;
var tree_time;
var average_velocity = [0,0];
document.getElementById('tracked').innerHTML = tracked_point;
// get click coordinates on canvas
document.getElementById('world').addEventListener('click', function(e){
tracked_point = getMousePos(document.getElementById('world'), e);
document.getElementById('tracked').innerHTML = tracked_point;
}, false);
document.getElementById('world').addEventListener('mousemove', function(e){
document.getElementById('over').innerHTML = getMousePos(document.getElementById('world'), e);
}, false);
// update tracked point coordinates
var getMousePos = function(el,e){
// get canvas position
var top = 0;
var left = 0;
while (el && el.tagName.toLowerCase() != 'body') {
top += el.offsetTop;
left += el.offsetLeft;
el = el.offsetParent;
}
// return relative mouse position
var mouseX = e.clientX - left + window.pageXOffset;
var mouseY = e.clientY - top + window.pageYOffset;
return [mouseX,mouseY];
};
var get_los_hits = function(){
var start = Date.now();
var hits = tree.search({
x:tracked_point[0],
y:tracked_point[1],
// 0 is for small size units! CAN BE MUCH BIGGER
w:1,
h:1
});
for(var i=0,n=hits.length; i<n; i++){
hits[i].hit = tracked_point;
}
var end = Date.now();
tree_time = end-start;
count = hits.length;
};
var go = function(){
get_los_hits();
var c = document.getElementById('world');
// clear
c.width = c.width;
var ctx = c.getContext('2d');
ctx.strokeStyle = "rgba(20,20,20,0.05)";
ctx.fillStyle = "rgba(225,155,155,0)";
ctx.font = '10pt Calibri';
var hit_stack = [];
hit_stack.push(tree.get_tree().nodes);
var leaf_stack = [];
var non_leaf_drawn = 0;
var ltree;
var start = Date.now();
do{
var nodes = hit_stack.pop();
for(var i = nodes.length-1; i >= 0; i--){
ltree = nodes[i];
if("nodes" in ltree){ // Not a Leaf
hit_stack.push(ltree.nodes);
non_leaf_drawn++;
}
else{
leaf_stack.push(ltree);
}
}
}
while(hit_stack.length > 0);
var leaf,
leaf_drawn = 0;
do{
leaf = leaf_stack.pop();
// a hit
if(leaf.leaf.hit && leaf.leaf.hit[0] === tracked_point[0] && leaf.leaf.hit[1] === tracked_point[1]){
ctx.fillStyle = "rgba(155,255,155,0.4)";
}
// a miss
else{
ctx.fillStyle = "rgba(225,155,155,0.2)";
}
// reset for next frame
leaf.leaf.hit = null;
// draw
ctx.fillRect(
leaf.x,
leaf.y,
leaf.w,
leaf.h
);
// draw "real" LOS
/*ctx.fillStyle = "rgba(20,20,20,0.1)";
ctx.beginPath();
ctx.arc(leaf.leaf.center[0], leaf.leaf.center[1], leaf.leaf.radius, 0, Math.PI*2, true);
ctx.closePath();
ctx.fill();*/
leaf_drawn++;
leaf.leaf.move();
}
while(leaf_stack.length > 0);
var end = Date.now();
// draw tracked point to make it visible
ctx.fillStyle = "rgba(20,20,20,0.5)";
ctx.beginPath();
ctx.arc(tracked_point[0]-1.5, tracked_point[1]-1.5, 3, 0, Math.PI*2, true);
ctx.fillText(count+' ['+tree_time+'ms]', tracked_point[0]+3, tracked_point[1]+2.3);
ctx.closePath();
ctx.fill();
document.getElementById('leaf_drawn').innerHTML = 'Drawn los: '+leaf_drawn+' [max is '+nb_los+']';
document.getElementById('non_leaf_drawn').innerHTML = 'Branch nodes: '+non_leaf_drawn;
document.getElementById('count').innerHTML = count+ ' hits (tree search in '+tree_time+' ms)';
document.getElementById('draw').innerHTML = 'Pick & draw time: '+(end-start)+' ms';
frame++;
document.getElementById('frame').innerHTML = 'Frame #'+frame;
window.setTimeout(go,20);
};
go();
</script>
</body>
</html>
Cheers,
Plop