QuadTrees with Rectangles
HTML
<script src="https://github.com/mikechambers/ExamplesByMesh/raw/master/JavaScript/QuadTree/src/QuadTree.js"></script>
<canvas id="canvas" height="300" width="300"></canvas>
<textarea id="output" cols="50" rows="10"></textarea>
JavaScript
var canvas = document.getElementById("canvas"),
ctx = canvas.getContext("2d");
var boundaries = {
x: 0,
y: 0,
width: canvas.width,
height: canvas.height
}
// False to set QuadTree to use points with boundaries
var tree = new QuadTree(boundaries, false);
// Inserts object with passed boundaries into quad tree.
// Also draws on canvas its boundaries.
function addRect(boundaries) {
ctx.strokeRect(
boundaries.x,
boundaries.y,
boundaries.width,
boundaries.height
);
tree.insert({
x: boundaries.x,
y: boundaries.y,
width: boundaries.width,
height: boundaries.height
});
};
function retrieve(boundaries) {
ctx.strokeStyle = "red";
ctx.strokeRect(
boundaries.x,
boundaries.y,
boundaries.width,
boundaries.height
);
return tree.retrieve({
x: boundaries.x,
y: boundaries.y,
width: boundaries.width,
height: boundaries.height
});
};
// Create vertal line across middle
ctx.beginPath();
ctx.lineTo(canvas.width / 2, 0);
ctx.lineTo(canvas.width / 2, canvas.height);
ctx.stroke();
// Create horizontal line across middle
ctx.beginPath();
ctx.lineTo(0, canvas.height / 2);
ctx.lineTo(canvas.width, canvas.height / 2);
ctx.stroke();
// Add 6 rectangles
addRect({ x:0, y:0, height:25, width:25 });
addRect({ x:50, y:50, height:25, width:25 });
addRect({ x:100, y:100, height:25, width:25 });
addRect({ x:125, y:25, height:25, width:50 });
addRect({ x:200, y:200, height:25, width:25 });
addRect({ x:250, y:250, height:25, width:25 });
// Point in quadrant I - returns 1 item as expected
// var items = retrieve({ x:175, y:75, height:1, width:1 });
// Point in quadrant II - returns 7 items - 3 duplicates
// var items = retrieve({ x:75, y:75, height:1, width:1 });
// Point in quadrant III - returns 1 item???
// var items = retrieve({ x:75, y:175, height:1, width:1 });
// Point in quadrant IV - Returns 4 items - 2 duplicates
// var items =...