A test and a problem #5

plopidou · 2012-05-01T13:27:29Z

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

The text was updated successfully, but these errors were encountered:

Provide feedback

Saved searches

Use saved searches to filter your results more quickly

A test and a problem #5

A test and a problem #5

plopidou commented May 1, 2012

A test and a problem #5

A test and a problem #5

Comments

plopidou commented May 1, 2012