Animated Quadtree.
A quadtree is a structure in which each node has less than or equal to 4 children.
From the visual 2-d perspective, it is usually illustrated in the form of quadrants, which follows the same strategy: if space gets more than 4 children, it is subsequently divided into 4 sub-quadrants or spaces.
| <!DOCTYPE html> | |
| <meta charset="utf-8"> | |
| <style> | |
| body { | |
| text-align: center; | |
| background-color: rgba(38, 67, 72, 1); | |
| } | |
| .node { | |
| opacity: 1; | |
| fill: yellowgreen; | |
| } | |
| svg { | |
| background: rgba(38, 67, 72, 1); | |
| } | |
| line { | |
| stroke: #FFB3A7; | |
| stroke-width: 1; | |
| } | |
| </style> | |
| <body> | |
| <script src="http://d3js.org/d3.v3.min.js"></script> | |
| <script> | |
| function random_(a, b) { | |
| var t = Math.random() * 10; | |
| if (t < 5) { | |
| return a - b; | |
| } else { | |
| return a + b; | |
| } | |
| } | |
| var width = 500; | |
| var height = 500; | |
| var n = 200; | |
| var p2q = {}; | |
| var svg = d3.select("body") | |
| .append("svg") | |
| .attr("width", width) | |
| .attr("height", height); | |
| var space_1 = svg.append("g"); | |
| var space_2 = svg.append("g"); | |
| var points = d3.range(n).map(function(d, i) { | |
| return { | |
| cx: random_(width / 2, Math.random() * 200), | |
| cy: Math.random() * height, | |
| r: 2, | |
| } | |
| }); | |
| function get_nearest_key(p) { | |
| var min_dist = Number.POSITIVE_INFINITY; | |
| var min_index = null; | |
| var min_item = null; | |
| var keys = Object.keys(p2q) | |
| .map(function(d, i) { | |
| return d.split(",").map(function(d, i) { | |
| return +d | |
| }) | |
| }); | |
| keys.map(function(u, f) { | |
| var dist = Math.sqrt(Math.pow(p.cx - u[0], 2) + Math.pow(p.cy - u[1], 2)); | |
| if (dist < min_dist) { | |
| min_dist = dist; | |
| min_index = f; | |
| min_item = u; | |
| } | |
| }); | |
| return p2q[min_item]; | |
| } | |
| function build_quadrant(obj) { | |
| //vertical one | |
| space_1.append("line") | |
| .attr("x1", (obj.min_x + obj.max_x) / 2) | |
| .attr("y1", (obj.min_y)) | |
| .attr("x2", (obj.min_x + obj.max_x) / 2) | |
| .attr("y2", (obj.max_y)); | |
| //horizontal one | |
| space_1.append("line") | |
| .attr("x1", (obj.min_x)) | |
| .attr("y1", (obj.min_y + obj.max_y) / 2) | |
| .attr("x2", (obj.max_x)) | |
| .attr("y2", (obj.min_y + obj.max_y) / 2); | |
| return true; | |
| } | |
| function objectify(spc) { | |
| var obj = {}; | |
| obj.min_x = spc[0][0]; | |
| obj.max_x = spc[2][0]; | |
| obj.min_y = spc[1][1]; | |
| obj.max_y = spc[0][1]; | |
| return obj; | |
| } | |
| function get_quadrants(obj, residents) { | |
| var quads = [ | |
| [ | |
| [obj.min_x, obj.max_y], | |
| [obj.min_x, (obj.min_y + obj.max_y) / 2], | |
| [(obj.min_x + obj.max_x) / 2, (obj.min_y + obj.max_y) / 2], | |
| [(obj.min_x + obj.max_x) / 2, obj.max_y], | |
| ], | |
| [ | |
| [obj.min_x, (obj.min_y + obj.max_y) / 2], | |
| [obj.min_x, obj.min_y], | |
| [(obj.min_x + obj.max_x) / 2, obj.min_y], | |
| [(obj.min_x + obj.max_x) / 2, (obj.min_y + obj.max_y) / 2] | |
| ], | |
| [ | |
| [(obj.min_x + obj.max_x) / 2, (obj.min_y + obj.max_y) / 2], | |
| [(obj.min_x + obj.max_x) / 2, obj.min_y], | |
| [obj.max_x, obj.min_y], | |
| [obj.max_x, (obj.min_y + obj.max_y) / 2] | |
| ], | |
| [ | |
| [(obj.min_x + obj.max_x) / 2, obj.max_y], | |
| [(obj.min_x + obj.max_x) / 2, (obj.min_y + obj.max_y) / 2], | |
| [obj.max_x, (obj.min_y + obj.max_y) / 2], | |
| [obj.max_x, obj.max_y] | |
| ] | |
| ]; | |
| //now register quadrants with residents | |
| residents.forEach(function(e, i) { | |
| var key = [e.cx, e.cy]; | |
| if (key in p2q) { | |
| quads.forEach(function(j, k) { | |
| p2q[key].push(objectify(j)); | |
| }); | |
| } else { | |
| p2q[key] = []; | |
| quads.forEach(function(j, k) { | |
| p2q[key].push(objectify(j)); | |
| }); | |
| } | |
| }); | |
| return quads; | |
| } | |
| function check_(obj) { | |
| var residents = points | |
| .filter(function(d_) { | |
| return (d_.cx >= obj.min_x && d_.cx <= obj.max_x) | |
| }); | |
| residents = residents.filter(function(d_) { | |
| return (d_.cy >= obj.min_y && d_.cy <= obj.max_y); | |
| }); | |
| if (residents.length > 4) { | |
| residents.forEach(function(k, i) { | |
| var key = [k.cx, k.cy]; | |
| if (key in p2q) { | |
| p2q[key].push(obj); | |
| } else { | |
| p2q[key] = []; | |
| p2q[key].push(obj); | |
| } | |
| }); | |
| return { | |
| status: true, | |
| residents: residents | |
| }; | |
| } | |
| return { | |
| status: false, | |
| residents: residents | |
| }; | |
| } | |
| space_2 | |
| .selectAll() | |
| .data(points) | |
| .enter() | |
| .append("circle") | |
| .attr("class", "node") | |
| .attr("r", function(d) { | |
| return d.r | |
| }) | |
| .attr("cx", function(d) { | |
| return d.cx | |
| }) | |
| .attr("cy", function(d) { | |
| return d.cy | |
| }); | |
| var spcs = [ | |
| [ | |
| [0, height], | |
| [0, 0], | |
| [width, 0], | |
| [width, height], | |
| ] | |
| ]; | |
| for (var i = 0; i < spcs.length; i++) { | |
| var d = spcs[i]; | |
| var obj = objectify(d); | |
| var indicator = check_(obj); | |
| if (indicator.status) { | |
| var quadrants = get_quadrants(obj, indicator.residents); | |
| var quad_built = build_quadrant(obj); | |
| quadrants.map(function(e, j) { | |
| spcs.push(e); | |
| }); | |
| } | |
| } | |
| function running() { | |
| var np = { | |
| cx: random_(width / 2, Math.random() * 200), | |
| cy: random_(height / 2, Math.random() * height), | |
| fill: "red", | |
| r: 2.5, | |
| }; | |
| var candidates = get_nearest_key(np); | |
| var candidates = candidates.filter(function(d) { | |
| return (np.cx >= d.min_x && np.cx <= d.max_x) && | |
| (np.cy >= d.min_y && np.cy <= d.max_y) | |
| }); | |
| if (candidates.length == 0) { | |
| return false; | |
| } | |
| points.push(np); | |
| space_2 | |
| .datum(np) | |
| .append("circle") | |
| .attr("class", "node") | |
| .attr("r", function(d) { | |
| return d.r | |
| }) | |
| .attr("cx", function(d) { | |
| return d.cx | |
| }) | |
| .attr("cy", function(d) { | |
| return d.cy | |
| }); | |
| var m_index = null; | |
| var m_distance = Number.POSITIVE_INFINITY; | |
| var m_item = null; | |
| candidates.forEach(function(g, i) { | |
| var dx = Math.abs(np.cx - g.max_x) + Math.abs(np.cx - g.min_x); | |
| var dy = Math.abs(np.cy - g.max_y) + Math.abs(np.cy - g.min_y); | |
| var dis = dx + dy; | |
| if (dis < m_distance) { | |
| m_distance = dis; | |
| m_index = i; | |
| m_item = g; | |
| } | |
| }); | |
| var indicator = check_(m_item); | |
| if (indicator.status) { | |
| var quadrants = get_quadrants(m_item, indicator.residents); | |
| var quad_built = build_quadrant(m_item); | |
| quadrants.map(function(e, j) { | |
| spcs.push(e); | |
| }); | |
| } | |
| return; | |
| } | |
| var runner = setInterval(running, 200); | |
| </script> | |
| </body> |
