Skip to content

Instantly share code, notes, and snippets.

@madelfio

madelfio/README.md

Last active December 19, 2015 19:28
Show Gist options
  • Save madelfio/6005974 to your computer and use it in GitHub Desktop.
Save madelfio/6005974 to your computer and use it in GitHub Desktop.
Download ZIP
Loose Quadtree Illustration
Raw
README.md

Demonstrates the relationship between rectangles and their enclosing quadtree blocks, for a loose quadtree with variable size and expansion factor.

Raw
index.html
<!doctype html>
<meta charset="utf-8">
<style>
body {position: relative;}
canvas, svg {position: absolute;}
.brush .extent {
stroke: #fff;
fill-opacity: .125;
shape-rendering: crispEdges;
}
.qbound, .qbound-loose {
fill: none;
stroke: black;
}
.qbound-loose {
opacity: 0.4;
}
div {
display: inline-block;
vertical-align: top;
}
</style>
<body>
<div id="container">
<canvas></canvas>
<svg></svg>
</div>
<div>
<div>
<label>Expansion Factor (p=<span id="p-val"></span>):<br />
<input type="number" id='p' min="0.00001" max="2.0" value="0.25" step="0.01" onchange="updatePVal(this.value);"/>
</label><br />
<button id="update" style="margin-left:auto; margin-right:auto;">Update</button>
</div>
</div>
</body>
<script src="http://d3js.org/d3.v3.min.js"></script>
<script src="quadtree.js"></script>
Raw
quadtree.js
var side = 512;
var lvls = {};
var first_time = true;
var p = 0.03,
rect_w = 40,
rect_h = 45;
var ERROR = 20000,
OUTSIDE = 10000,
raw_color = d3.scale.linear()
//.domain([0, -5, -10])
//.range(['#E5F5F9', '#2C726F']);
.domain([16, 9, 6, 3, -3])
.range(['#FFFFCC', '#EDF8B1', '#7FCDBB', '#2C7FB8', '#253494']);
function color(v) {
if (v == ERROR) {return 'orange';}
if (v == OUTSIDE) {return '#eee';}
return raw_color(v);
}
var container = d3.select('#container')
.style('width', side + 'px')
.style('height', side + 'px');
var canvas = d3.select('canvas')
.attr('width', side)
.attr('height', side)
.style('width', side)
.style('height', side)
.call(drawImage);
var svg = d3.select('svg')
.attr('width', side)
.attr('height', side);
var brush = d3.svg.brush()
.x(d3.scale.identity().domain([0, side]))
.y(d3.scale.identity().domain([0, side]))
.on('brush', moveBrush)
.on('brushend', resizeBrush)
.extent([[100, 100], [100 + rect_w, 100 + rect_h]]);
shapes = svg.append('g')
.attr('class', 'shapes');
svg.append('g')
.attr('class', 'brush')
.call(brush);
function moveBrush() {
var extent = brush.extent();
cx = (extent[1][0] + extent[0][0]) / 2;
cy = (extent[1][1] + extent[0][1]) / 2;
shapes.selectAll('circle').remove();
shapes.append('circle')
.attr('cx', cx)
.attr('cy', cy)
.attr('r', 3)
.attr('fill', 'blue');
var vals = getMBQB(cx, cy, rect_w, rect_h);
shapes.selectAll('rect').remove();
shapes.append('rect')
.attr('x', vals[1])
.attr('y', vals[2])
.attr('width', vals[0])
.attr('height', vals[0])
.attr('class', 'qbound');
shapes.append('rect')
.attr('x', vals[1] - p * vals[0] / 2)
.attr('y', vals[2] - p * vals[0] / 2)
.attr('width', vals[0] * (1 + p))
.attr('height', vals[0] * (1 + p))
.attr('class', 'qbound-loose');
}
function resizeBrush() {
var extent = brush.extent();
rect_w = extent[1][0] - extent[0][0];
rect_h = extent[1][1] - extent[0][1];
console.log(rect_w);
console.log(rect_h);
if (rect_w > 0 && rect_h > 0) {
update();
moveBrush();
}
}
function drawImage(canvas) {
var context = canvas.node().getContext('2d');
context.clearRect( 0, 0, side, side);
var image = context.createImageData(side, side);
for (var y = 0, idx = -1; y < side; ++y) {
for (var x = 0; x < side; ++x) {
var lvl = getLevel(x, y, rect_w, rect_h),
c = d3.rgb(color(lvl));
lvls[lvl] = true;
image.data[++idx] = c.r;
image.data[++idx] = c.g;
image.data[++idx] = c.b;
image.data[++idx] = 255;
}
}
context.putImageData(image, 0, 0);
console.log(lvls);
}
function L(v) {
return Math.ceil(Math.log(v) / Math.log(2));
}
function M(v) {
return Math.pow(2, Math.ceil(Math.log(v) / Math.log(2)));
}
function getLevel(x, y, w, h) {
var r = Math.max(w, h) / 2,
min_lvl = L(2*r/(1+p)),
max_lvl = L(4*r/p);
if (first_time) {
console.log(r);
console.log(min_lvl, max_lvl);
//raw_color.domain([500, max_lvl, Math.floor((max_lvl + min_lvl)/2), min_lvl, -500]);
first_time = false;
}
//if (x - w/2 < -p/2 || x + w/2 > side + p/2 ||
// y - h/2 < -p/2 || y + h/2 > side + p/2) {
// return OUTSIDE;
//}
for (qlvl = min_lvl; qlvl <= max_lvl; qlvl++) {
var qw = Math.pow(2, qlvl),
qx = Math.floor(x / qw) * qw,
qy = Math.floor(y / qw) * qw;
if ((qx - p*qw/2 <= x - w/2) && (qx + qw + p*qw/2 > x + w/2) &&
(qy - p*qw/2 <= y - h/2) && (qy + qw + p*qw/2 > y + h/2)) {
return qlvl;
}
}
//console.log(x, y, w, h);
//console.log(r, min_lvl, max_lvl);
return ERROR;
}
d3.select('#update').on('click', update);
function update() {
//rect_w = rect_h = +d3.select('#s').property('value') || 16;
first_time = true;
d3.select('canvas').call(drawImage);
}
function getMBQB(x, y, w, h) {
var r = Math.max(w, h) / 2,
min_lvl = L(2*r/(1+p)),
max_lvl = L(4*r/p);
if (x - w/2 < -p/2 || x + w/2 > side + p/2 ||
y - h/2 < -p/2 || y + h/2 > side + p/2) {
return OUTSIDE;
}
for (qlvl = min_lvl; qlvl <= max_lvl; qlvl++) {
var qw = Math.pow(2, qlvl),
qx = Math.floor(x / qw) * qw,
qy = Math.floor(y / qw) * qw;
if ((qx - p*qw/2 <= x - w/2) && (qx + qw + p*qw/2 > x + w/2) &&
(qy - p*qw/2 <= y - h/2) && (qy + qw + p*qw/2 > y + h/2)) {
return [qw, qx, qy];
}
}
//console.log(x, y, w, h);
//console.log(r, min_lvl, max_lvl);
return ERROR;
}
function updatePVal(val) {
p = +val || +d3.select('#p').property('value') || 0.1;
d3.select('#p-val').text(p);
}
updatePVal();
moveBrush();
resizeBrush();
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment