Javascript 伪四叉树的邻接矩阵
Javascript Adjacency matrix at pseudo quadtree
我有一个伪四叉树算法，它将 space 除以到当前鼠标位置的距离。
为什么是伪造的？它不会创建适当的树，其中每个节点都有 4 个子节点或 none（如果它是终端节点）。取而代之的是，该算法按顺时针顺序将分区替换为其四个子项。
我需要为每个分区轻松获取邻居，并且非常确定我需要为所有节点创建和更新邻接矩阵。很确定它必须在 Quadtree.splitNode() 函数内。
到目前为止，我还不知道如何制作我。
我附上了交互式 canvas 和 table 的片段，应该使用邻接矩阵进行更新。
var mouse = {x: 0, y: 0}, colors = ['#e6194b', '#3cb44b', '#ffe119', '#4363d8', '#f58231', '#911eb4', '#46f0f0', '#f032e6', '#bcf60c', '#fabebe', '#008080', '#e6beff', '#9a6324', '#fffac8', '#800000', '#aaffc3', '#808000', '#ffd8b1', '#000075', '#808080', '#ffffff', '#000000'];
class Node{
constructor(level_, index_, centerX_, centerY_, width_, height_, resolution_){
this.level = level_;
this.index = index_;
this.w = width_;
this.h = height_;
this.x = centerX_;
this.y = centerY_;
this.resolution = resolution_;
this.edges = this.getEdges();
}
getEdges = function(){
return [
{x: this.x - this.w / 2, y: this.y - this.h / 2},
{x: this.x + this.w / 2, y: this.y - this.h / 2},
{x: this.x + this.w / 2, y: this.y + this.h / 2},
{x: this.x - this.w / 2, y: this.y + this.h / 2}
];
}
getAdjacency = function(){
return [
{x: this.x - this.w / 2, y: this.y - this.h / 2},
{x: this.x + this.w / 2, y: this.y - this.h / 2},
{x: this.x + this.w / 2, y: this.y + this.h / 2},
{x: this.x - this.w / 2, y: this.y + this.h / 2}
];
}
}
class Quadtree{
constructor(root_, levels_, distance_){
var this_ = this;
this.levels = levels_;
this.distance = distance_;
this.root = root_;
this.nodes = [];
this.nodes = this.splitNode(0, this.root, false);
this.generateLevels();
this.last = [...this.nodes];
this.tiles = {};
this.debug = {};
this.points = [];
this.adjacency = [
["-", 0, 1, 2, 3],
[0, 0, 1, 0, 1 ],
[1, 1, 0, 1, 0],
[2, 0, 1, 0, 1],
[3, 1, 0, 1, 0]
];
}
generateLevels = function(){
for(var i = 0; i < this.levels; i++){
var tmpNodes = [];
for(var j = 0; j < this.nodes.length; j++){
tmpNodes.push(...this.splitNode(j, this.nodes[j], true));
}
this.nodes = tmpNodes;
}
}
update = function(){
var this_ = this;
this.nodes = [];
this.nodes = this.splitNode(0, this.root, false);
this.generateLevels();
this.debug = {};
this.last = [...this.nodes];
}
splitNode = function(index_, parent_, check_){
if((parent_.level < this.levels && this.sqrtDistance(parent_) < this.distance) || !check_){
var lt = new Node(parent_.level + 1, { x: parent_.index.x * 2, y: parent_.index.y * 2 }, parent_.x - parent_.w / 4, parent_.y - parent_.h / 4, parent_.w / 2, parent_.h / 2, parent_.resolution / 2);
var rt = new Node(parent_.level + 1, { x: parent_.index.x * 2, y: parent_.index.y * 2 + 1 }, parent_.x + parent_.w / 4, parent_.y - parent_.h / 4, parent_.w / 2, parent_.h / 2, parent_.resolution / 2);
var rb = new Node(parent_.level + 1, { x: parent_.index.x * 2 + 1, y: parent_.index.y * 2 + 1 }, parent_.x + parent_.w / 4, parent_.y + parent_.h / 4, parent_.w / 2, parent_.h / 2, parent_.resolution / 2);
var lb = new Node(parent_.level + 1, { x: parent_.index.x * 2 + 1, y: parent_.index.y * 2 }, parent_.x - parent_.w / 4, parent_.y + parent_.h / 4, parent_.w / 2, parent_.h / 2, parent_.resolution / 2);
return [lt, rt, rb, lb];
}
return [parent_];
}
sqrtDistance = function(node_){
var target = mouse;
var x1 = node_.x - node_.w / 2.0;
var y1 = node_.y - node_.h / 2.0;
var x2 = node_.x + node_.w / 2.0;
var y2 = node_.y + node_.h / 2.0;
var rx = (x1 + x2) / 2.0;
var ry = (y1 + y2) / 2.0;
var rwidth = node_.w;
var rheight = node_.h;
var dx = Math.max(Math.abs(target.x - rx) - rwidth / 2, 0);
var dy = Math.max(Math.abs(target.y - ry) - rheight / 2, 0);
return Math.sqrt(dx * dx + dy * dy);
}
}
var root = new Node(0, {x: 0, y: 0}, 512, 512, 992, 992, 1);
var quad = new Quadtree(root, 5, 16.0);
quad.update();
var canvas = document.getElementById("quad");
var ctx = canvas.getContext("2d");
generateAdjacencyTable();
function drawQuad(){
ctx.clearRect(0, 0, canvas.width, canvas.height);
quad.nodes.forEach(function(node_, i_){
//contours
var points = node_.getEdges();
ctx.beginPath();
ctx.moveTo(points[0].x, points[0].y);
for(var i = 1; i < points.length; i++){ ctx.lineTo(points[i].x, points[i].y); }
ctx.lineTo(points[0].x, points[0].y);
//ctx.strokeStyle = colors[i_ % 20];
ctx.stroke();
})
}
function generateAdjacencyTable(){
if(document.getElementById("adjTable") != undefined){
var oldTbl = document.getElementById("adjTable");
oldTbl.parentNode.removeChild(oldTbl);
}
var body = document.getElementsByTagName("body")[0];
var tbl = document.createElement("table");
tbl.style = "margin: 8px;";
tbl.id = "adjTable";
var tblBody = document.createElement("tbody");
for(var j = 0; j < quad.adjacency.length; j++) {
var row = document.createElement("tr");
for(var i = 0; i < quad.adjacency[j].length; i++) {
var cell = document.createElement("td");
var cellText = document.createTextNode(quad.adjacency[i][j]);
cell.appendChild(cellText);
row.appendChild(cell);
}
tblBody.appendChild(row);
}
tbl.appendChild(tblBody);
body.appendChild(tbl);
tbl.setAttribute("border", "1");
}
document.addEventListener("mousemove", onMouseMoveEvent, false);
function onMouseMoveEvent(event_){
var rect = canvas.getBoundingClientRect();
mouse = {
x: (event_.clientX - rect.left) * 2,
y: (event_.clientY - rect.top) * 2
};
quad.update();
drawQuad();
}
body { margin: 0; }
tbody td:first-child, tr:first-child { background: rgb(192, 192, 192); }
<!DOCTYPE html>
<html>
<head>
<meta charset="utf-8" />
</head>
<body>
<canvas id="quad" width="1024" height="1024" style="width: 512px; height: 512px;"></canvas>
</body>
</html>
这是一个临时解决方案。
var mouse = {x: 600, y: 600};
Number.prototype.between = function(a_, b_) {
var min = Math.min.apply(Math, [a_, b_]),
max = Math.max.apply(Math, [a_, b_]);
return this >= min && this <= max;
};
class Node{
constructor(id_, level_, index_, centerX_, centerY_, width_, height_, resolution_){
this.id = id_;
this.level = level_;
this.index = index_;
this.w = width_;
this.h = height_;
this.x = centerX_;
this.y = centerY_;
this.resolution = resolution_;
this.edges = this.getEdges();
}
getEdges = function(){
return [
{x: this.x - this.w / 2, y: this.y - this.h / 2},
{x: this.x + this.w / 2, y: this.y - this.h / 2},
{x: this.x + this.w / 2, y: this.y + this.h / 2},
{x: this.x - this.w / 2, y: this.y + this.h / 2}
];
}
getAdjacency = function(){
return [
{x: this.x - this.w / 2, y: this.y - this.h / 2},
{x: this.x + this.w / 2, y: this.y - this.h / 2},
{x: this.x + this.w / 2, y: this.y + this.h / 2},
{x: this.x - this.w / 2, y: this.y + this.h / 2}
];
}
}
class Quadtree{
constructor(root_, levels_, distance_){
var this_ = this;
this.adjacency = [ ];
this.pattern = [
[0, 1, 0, 1],
[1, 0, 1, 0],
[0, 1, 0, 1],
[1, 0, 1, 0]
];
this.levels = levels_;
this.distance = distance_;
this.root = root_;
this.nodes = [];
this.nodes = this.splitNode(0, this.root, false);
this.generateLevels();
this.last = [...this.nodes];
this.tiles = {};
this.debug = {};
this.points = [];
}
generateLevels = function(){
for(var i = 0; i < this.levels; i++){
for(var j = 0; j < this.nodes.length; j++){
var tmp = this.splitNode(j, this.nodes[j], true);
//array.splice(2, 1, ...array2);
this.nodes.splice(j, 1, ...tmp);
}
}
}
update = function(){
this.adjacency = [
];
var this_ = this;
this.nodes = [];
this.nodes = this.splitNode(0, this.root, false);
this.generateLevels();
this.debug = {};
this.last = [...this.nodes];
}
splitNode = function(index_, parent_, check_){
if((parent_.level < this.levels && this.sqrtDistance(parent_) < this.distance) || !check_){
var lt = new Node(parent_.id + "0.", parent_.level + 1, { x: parent_.index.x * 2, y: parent_.index.y * 2 }, parent_.x - parent_.w / 4, parent_.y - parent_.h / 4, parent_.w / 2, parent_.h / 2, parent_.resolution / 2);
var rt = new Node(parent_.id + "1.", parent_.level + 1, { x: parent_.index.x * 2, y: parent_.index.y * 2 + 1 }, parent_.x + parent_.w / 4, parent_.y - parent_.h / 4, parent_.w / 2, parent_.h / 2, parent_.resolution / 2);
var rb = new Node(parent_.id + "2.", parent_.level + 1, { x: parent_.index.x * 2 + 1, y: parent_.index.y * 2 + 1 }, parent_.x + parent_.w / 4, parent_.y + parent_.h / 4, parent_.w / 2, parent_.h / 2, parent_.resolution / 2);
var lb = new Node(parent_.id + "3.", parent_.level + 1, { x: parent_.index.x * 2 + 1, y: parent_.index.y * 2 }, parent_.x - parent_.w / 4, parent_.y + parent_.h / 4, parent_.w / 2, parent_.h / 2, parent_.resolution / 2);
if(check_) { this.extend2D(index_); } else { this.adjacency = [
[0, 1, 0, 1],
[1, 0, 1, 0],
[0, 1, 0, 1],
[1, 0, 1, 0]
]; }
return [lt, rt, rb, lb];
}
return [parent_];
}
extend2D = function(index_){
var tmp = Array(this.adjacency.length + this.pattern.length - 1).fill().map(() => Array(this.adjacency[0].length + this.pattern[0].length - 1));
for(var i = 0; i < tmp.length; i++){
for(var j = 0; j < tmp[i].length; j++){
var pi, pj, ni, nj;
i < index_ ? pi = i : pi = i - this.pattern.length;
j < index_ ? pj = j : pj = j - this.pattern[0].length;
ni = i - index_;
nj = j - index_;
//exclude themselfves
if(i == j) { tmp[i][j] = 0; continue; }
else if(!i.between(index_, index_ + this.pattern.length - 1) && !j.between(index_, index_ + this.pattern[0].length - 1)){
tmp[i][j] = tmp[j][i] = this.adjacency[pi][pj];
}
else if(i.between(index_, index_ + this.pattern.length - 1) && j.between(index_, index_ + this.pattern[0].length - 1)){
tmp[i][j] = tmp[j][i] = this.pattern[ni][nj];
continue;
}
else if(i.between(index_, index_ + this.pattern.length - 1)){
if(this.adjacency[index_][pj] == 0) { tmp[i][j] = tmp[j][i] = 0; }
else{
var dir;
var theta = Math.atan2(this.nodes[pj].y - this.nodes[index_].y, this.nodes[pj].x - this.nodes[index_].x);
if( theta > -Math.PI / 4.0 * 3.0 && theta < -Math.PI / 4.0) { dir = [1, 1, 0, 0]; }
else if(theta < Math.PI / 4.0) { dir = [0, 1, 1, 0]; }
else if(theta < Math.PI / 4.0 * 3.0) { dir = [0, 0, 1, 1]; }
else { dir = [1, 0, 0, 1]; }
tmp[i][j] = tmp[j][i] = dir[i - index_];
}
}
}
}
this.adjacency = [...tmp];
}
sqrtDistance = function(node_){
var target = mouse;
var x1 = node_.x - node_.w / 2.0;
var y1 = node_.y - node_.h / 2.0;
var x2 = node_.x + node_.w / 2.0;
var y2 = node_.y + node_.h / 2.0;
var rx = (x1 + x2) / 2.0;
var ry = (y1 + y2) / 2.0;
var rwidth = node_.w;
var rheight = node_.h;
var dx = Math.max(Math.abs(target.x - rx) - rwidth / 2, 0);
var dy = Math.max(Math.abs(target.y - ry) - rheight / 2, 0);
return Math.sqrt(dx * dx + dy * dy);
}
}
var root = new Node("", 0, {x: 0, y: 0}, 512, 512, 992, 992, 1);
var quad = new Quadtree(root, 3, 16.0);
quad.update();
var canvas = document.getElementById("quad");
var ctx = canvas.getContext("2d");
var index = 6;
function checkNeighbour(index_, index2_, array_){
return array_[index2_][index_] == 1 ? true : false;
}
function drawQuad(index_){
ctx.clearRect(0, 0, canvas.width, canvas.height);
quad.nodes.forEach(function(node_, i_){
if(index_ < quad.nodes.length && index_ == i_) { ctx.fillStyle = "#FF00FF"; }
else if(index_ < quad.nodes.length && checkNeighbour(i_, index_, quad.adjacency)) { ctx.fillStyle = "#00FFFF"; }
else { ctx.fillStyle = "transparent"; }
//contours
var points = node_.getEdges();
ctx.beginPath();
ctx.moveTo(points[0].x, points[0].y);
for(var i = 1; i < points.length; i++){ ctx.lineTo(points[i].x, points[i].y); }
ctx.lineTo(points[0].x, points[0].y);
ctx.fill();
ctx.strokeStyle = "#000000";
ctx.stroke();
})
}
function generateAdjacencyTable(){
var adjacencyTbl = [];
for(var x = 0; x < quad.adjacency.length + 1; x++){
adjacencyTbl[x] = [];
for(var y = 0; y < quad.adjacency[0].length + 1; y++){
if(x == 0 && y == 0) { adjacencyTbl[x][y] = "-"; }
else if(x == 0) { adjacencyTbl[x][y] = quad.nodes[y - 1].id; }
else if(y == 0) { adjacencyTbl[x][y] = quad.nodes[x - 1].id; }
else { adjacencyTbl[x][y] = quad.adjacency[x - 1][y - 1]; }
}
}
if(document.getElementById("adjTable") != undefined){
var oldTbl = document.getElementById("adjTable");
oldTbl.parentNode.removeChild(oldTbl);
}
var body = document.getElementsByTagName("body")[0];
var tbl = document.createElement("table");
tbl.style = "margin: 8px;";
tbl.id = "adjTable";
var tblBody = document.createElement("tbody");
for(var j = 0; j < adjacencyTbl.length; j++) {
var row = document.createElement("tr");
for(var i = 0; i < adjacencyTbl[j].length; i++) {
var cell = document.createElement("td");
var cellText = document.createTextNode(adjacencyTbl[i][j]);
cell.appendChild(cellText);
row.appendChild(cell);
}
tblBody.appendChild(row);
}
tbl.appendChild(tblBody);
body.appendChild(tbl);
tbl.setAttribute("border", "1");
}
document.addEventListener("mousemove", onMouseMoveEvent, false);
function onMouseMoveEvent(event_){
var rect = canvas.getBoundingClientRect();
mouse = {
x: (event_.clientX - rect.left) * 2,
y: (event_.clientY - rect.top) * 2
};
quad.update();
drawQuad(6);
generateAdjacencyTable();
}
body { margin: 0; }
tbody td:first-child, tr:first-child { background: rgb(192, 192, 192); }
<!DOCTYPE html>
<html>
<head>
<meta charset="utf-8" />
</head>
<body>
<canvas id="quad" width="1024" height="1024" style="width: 512px; height: 512px;"></canvas>
</body>
</html>
我有一个伪四叉树算法，它将 space 除以到当前鼠标位置的距离。
为什么是伪造的？它不会创建适当的树，其中每个节点都有 4 个子节点或 none（如果它是终端节点）。取而代之的是，该算法按顺时针顺序将分区替换为其四个子项。
我需要为每个分区轻松获取邻居，并且非常确定我需要为所有节点创建和更新邻接矩阵。很确定它必须在 Quadtree.splitNode() 函数内。
到目前为止，我还不知道如何制作我。
我附上了交互式 canvas 和 table 的片段，应该使用邻接矩阵进行更新。
var mouse = {x: 0, y: 0}, colors = ['#e6194b', '#3cb44b', '#ffe119', '#4363d8', '#f58231', '#911eb4', '#46f0f0', '#f032e6', '#bcf60c', '#fabebe', '#008080', '#e6beff', '#9a6324', '#fffac8', '#800000', '#aaffc3', '#808000', '#ffd8b1', '#000075', '#808080', '#ffffff', '#000000'];
class Node{
constructor(level_, index_, centerX_, centerY_, width_, height_, resolution_){
this.level = level_;
this.index = index_;
this.w = width_;
this.h = height_;
this.x = centerX_;
this.y = centerY_;
this.resolution = resolution_;
this.edges = this.getEdges();
}
getEdges = function(){
return [
{x: this.x - this.w / 2, y: this.y - this.h / 2},
{x: this.x + this.w / 2, y: this.y - this.h / 2},
{x: this.x + this.w / 2, y: this.y + this.h / 2},
{x: this.x - this.w / 2, y: this.y + this.h / 2}
];
}
getAdjacency = function(){
return [
{x: this.x - this.w / 2, y: this.y - this.h / 2},
{x: this.x + this.w / 2, y: this.y - this.h / 2},
{x: this.x + this.w / 2, y: this.y + this.h / 2},
{x: this.x - this.w / 2, y: this.y + this.h / 2}
];
}
}
class Quadtree{
constructor(root_, levels_, distance_){
var this_ = this;
this.levels = levels_;
this.distance = distance_;
this.root = root_;
this.nodes = [];
this.nodes = this.splitNode(0, this.root, false);
this.generateLevels();
this.last = [...this.nodes];
this.tiles = {};
this.debug = {};
this.points = [];
this.adjacency = [
["-", 0, 1, 2, 3],
[0, 0, 1, 0, 1 ],
[1, 1, 0, 1, 0],
[2, 0, 1, 0, 1],
[3, 1, 0, 1, 0]
];
}
generateLevels = function(){
for(var i = 0; i < this.levels; i++){
var tmpNodes = [];
for(var j = 0; j < this.nodes.length; j++){
tmpNodes.push(...this.splitNode(j, this.nodes[j], true));
}
this.nodes = tmpNodes;
}
}
update = function(){
var this_ = this;
this.nodes = [];
this.nodes = this.splitNode(0, this.root, false);
this.generateLevels();
this.debug = {};
this.last = [...this.nodes];
}
splitNode = function(index_, parent_, check_){
if((parent_.level < this.levels && this.sqrtDistance(parent_) < this.distance) || !check_){
var lt = new Node(parent_.level + 1, { x: parent_.index.x * 2, y: parent_.index.y * 2 }, parent_.x - parent_.w / 4, parent_.y - parent_.h / 4, parent_.w / 2, parent_.h / 2, parent_.resolution / 2);
var rt = new Node(parent_.level + 1, { x: parent_.index.x * 2, y: parent_.index.y * 2 + 1 }, parent_.x + parent_.w / 4, parent_.y - parent_.h / 4, parent_.w / 2, parent_.h / 2, parent_.resolution / 2);
var rb = new Node(parent_.level + 1, { x: parent_.index.x * 2 + 1, y: parent_.index.y * 2 + 1 }, parent_.x + parent_.w / 4, parent_.y + parent_.h / 4, parent_.w / 2, parent_.h / 2, parent_.resolution / 2);
var lb = new Node(parent_.level + 1, { x: parent_.index.x * 2 + 1, y: parent_.index.y * 2 }, parent_.x - parent_.w / 4, parent_.y + parent_.h / 4, parent_.w / 2, parent_.h / 2, parent_.resolution / 2);
return [lt, rt, rb, lb];
}
return [parent_];
}
sqrtDistance = function(node_){
var target = mouse;
var x1 = node_.x - node_.w / 2.0;
var y1 = node_.y - node_.h / 2.0;
var x2 = node_.x + node_.w / 2.0;
var y2 = node_.y + node_.h / 2.0;
var rx = (x1 + x2) / 2.0;
var ry = (y1 + y2) / 2.0;
var rwidth = node_.w;
var rheight = node_.h;
var dx = Math.max(Math.abs(target.x - rx) - rwidth / 2, 0);
var dy = Math.max(Math.abs(target.y - ry) - rheight / 2, 0);
return Math.sqrt(dx * dx + dy * dy);
}
}
var root = new Node(0, {x: 0, y: 0}, 512, 512, 992, 992, 1);
var quad = new Quadtree(root, 5, 16.0);
quad.update();
var canvas = document.getElementById("quad");
var ctx = canvas.getContext("2d");
generateAdjacencyTable();
function drawQuad(){
ctx.clearRect(0, 0, canvas.width, canvas.height);
quad.nodes.forEach(function(node_, i_){
//contours
var points = node_.getEdges();
ctx.beginPath();
ctx.moveTo(points[0].x, points[0].y);
for(var i = 1; i < points.length; i++){ ctx.lineTo(points[i].x, points[i].y); }
ctx.lineTo(points[0].x, points[0].y);
//ctx.strokeStyle = colors[i_ % 20];
ctx.stroke();
})
}
function generateAdjacencyTable(){
if(document.getElementById("adjTable") != undefined){
var oldTbl = document.getElementById("adjTable");
oldTbl.parentNode.removeChild(oldTbl);
}
var body = document.getElementsByTagName("body")[0];
var tbl = document.createElement("table");
tbl.style = "margin: 8px;";
tbl.id = "adjTable";
var tblBody = document.createElement("tbody");
for(var j = 0; j < quad.adjacency.length; j++) {
var row = document.createElement("tr");
for(var i = 0; i < quad.adjacency[j].length; i++) {
var cell = document.createElement("td");
var cellText = document.createTextNode(quad.adjacency[i][j]);
cell.appendChild(cellText);
row.appendChild(cell);
}
tblBody.appendChild(row);
}
tbl.appendChild(tblBody);
body.appendChild(tbl);
tbl.setAttribute("border", "1");
}
document.addEventListener("mousemove", onMouseMoveEvent, false);
function onMouseMoveEvent(event_){
var rect = canvas.getBoundingClientRect();
mouse = {
x: (event_.clientX - rect.left) * 2,
y: (event_.clientY - rect.top) * 2
};
quad.update();
drawQuad();
}
body { margin: 0; }
tbody td:first-child, tr:first-child { background: rgb(192, 192, 192); }
<!DOCTYPE html>
<html>
<head>
<meta charset="utf-8" />
</head>
<body>
<canvas id="quad" width="1024" height="1024" style="width: 512px; height: 512px;"></canvas>
</body>
</html>
这是一个临时解决方案。
var mouse = {x: 600, y: 600};
Number.prototype.between = function(a_, b_) {
var min = Math.min.apply(Math, [a_, b_]),
max = Math.max.apply(Math, [a_, b_]);
return this >= min && this <= max;
};
class Node{
constructor(id_, level_, index_, centerX_, centerY_, width_, height_, resolution_){
this.id = id_;
this.level = level_;
this.index = index_;
this.w = width_;
this.h = height_;
this.x = centerX_;
this.y = centerY_;
this.resolution = resolution_;
this.edges = this.getEdges();
}
getEdges = function(){
return [
{x: this.x - this.w / 2, y: this.y - this.h / 2},
{x: this.x + this.w / 2, y: this.y - this.h / 2},
{x: this.x + this.w / 2, y: this.y + this.h / 2},
{x: this.x - this.w / 2, y: this.y + this.h / 2}
];
}
getAdjacency = function(){
return [
{x: this.x - this.w / 2, y: this.y - this.h / 2},
{x: this.x + this.w / 2, y: this.y - this.h / 2},
{x: this.x + this.w / 2, y: this.y + this.h / 2},
{x: this.x - this.w / 2, y: this.y + this.h / 2}
];
}
}
class Quadtree{
constructor(root_, levels_, distance_){
var this_ = this;
this.adjacency = [ ];
this.pattern = [
[0, 1, 0, 1],
[1, 0, 1, 0],
[0, 1, 0, 1],
[1, 0, 1, 0]
];
this.levels = levels_;
this.distance = distance_;
this.root = root_;
this.nodes = [];
this.nodes = this.splitNode(0, this.root, false);
this.generateLevels();
this.last = [...this.nodes];
this.tiles = {};
this.debug = {};
this.points = [];
}
generateLevels = function(){
for(var i = 0; i < this.levels; i++){
for(var j = 0; j < this.nodes.length; j++){
var tmp = this.splitNode(j, this.nodes[j], true);
//array.splice(2, 1, ...array2);
this.nodes.splice(j, 1, ...tmp);
}
}
}
update = function(){
this.adjacency = [
];
var this_ = this;
this.nodes = [];
this.nodes = this.splitNode(0, this.root, false);
this.generateLevels();
this.debug = {};
this.last = [...this.nodes];
}
splitNode = function(index_, parent_, check_){
if((parent_.level < this.levels && this.sqrtDistance(parent_) < this.distance) || !check_){
var lt = new Node(parent_.id + "0.", parent_.level + 1, { x: parent_.index.x * 2, y: parent_.index.y * 2 }, parent_.x - parent_.w / 4, parent_.y - parent_.h / 4, parent_.w / 2, parent_.h / 2, parent_.resolution / 2);
var rt = new Node(parent_.id + "1.", parent_.level + 1, { x: parent_.index.x * 2, y: parent_.index.y * 2 + 1 }, parent_.x + parent_.w / 4, parent_.y - parent_.h / 4, parent_.w / 2, parent_.h / 2, parent_.resolution / 2);
var rb = new Node(parent_.id + "2.", parent_.level + 1, { x: parent_.index.x * 2 + 1, y: parent_.index.y * 2 + 1 }, parent_.x + parent_.w / 4, parent_.y + parent_.h / 4, parent_.w / 2, parent_.h / 2, parent_.resolution / 2);
var lb = new Node(parent_.id + "3.", parent_.level + 1, { x: parent_.index.x * 2 + 1, y: parent_.index.y * 2 }, parent_.x - parent_.w / 4, parent_.y + parent_.h / 4, parent_.w / 2, parent_.h / 2, parent_.resolution / 2);
if(check_) { this.extend2D(index_); } else { this.adjacency = [
[0, 1, 0, 1],
[1, 0, 1, 0],
[0, 1, 0, 1],
[1, 0, 1, 0]
]; }
return [lt, rt, rb, lb];
}
return [parent_];
}
extend2D = function(index_){
var tmp = Array(this.adjacency.length + this.pattern.length - 1).fill().map(() => Array(this.adjacency[0].length + this.pattern[0].length - 1));
for(var i = 0; i < tmp.length; i++){
for(var j = 0; j < tmp[i].length; j++){
var pi, pj, ni, nj;
i < index_ ? pi = i : pi = i - this.pattern.length;
j < index_ ? pj = j : pj = j - this.pattern[0].length;
ni = i - index_;
nj = j - index_;
//exclude themselfves
if(i == j) { tmp[i][j] = 0; continue; }
else if(!i.between(index_, index_ + this.pattern.length - 1) && !j.between(index_, index_ + this.pattern[0].length - 1)){
tmp[i][j] = tmp[j][i] = this.adjacency[pi][pj];
}
else if(i.between(index_, index_ + this.pattern.length - 1) && j.between(index_, index_ + this.pattern[0].length - 1)){
tmp[i][j] = tmp[j][i] = this.pattern[ni][nj];
continue;
}
else if(i.between(index_, index_ + this.pattern.length - 1)){
if(this.adjacency[index_][pj] == 0) { tmp[i][j] = tmp[j][i] = 0; }
else{
var dir;
var theta = Math.atan2(this.nodes[pj].y - this.nodes[index_].y, this.nodes[pj].x - this.nodes[index_].x);
if( theta > -Math.PI / 4.0 * 3.0 && theta < -Math.PI / 4.0) { dir = [1, 1, 0, 0]; }
else if(theta < Math.PI / 4.0) { dir = [0, 1, 1, 0]; }
else if(theta < Math.PI / 4.0 * 3.0) { dir = [0, 0, 1, 1]; }
else { dir = [1, 0, 0, 1]; }
tmp[i][j] = tmp[j][i] = dir[i - index_];
}
}
}
}
this.adjacency = [...tmp];
}
sqrtDistance = function(node_){
var target = mouse;
var x1 = node_.x - node_.w / 2.0;
var y1 = node_.y - node_.h / 2.0;
var x2 = node_.x + node_.w / 2.0;
var y2 = node_.y + node_.h / 2.0;
var rx = (x1 + x2) / 2.0;
var ry = (y1 + y2) / 2.0;
var rwidth = node_.w;
var rheight = node_.h;
var dx = Math.max(Math.abs(target.x - rx) - rwidth / 2, 0);
var dy = Math.max(Math.abs(target.y - ry) - rheight / 2, 0);
return Math.sqrt(dx * dx + dy * dy);
}
}
var root = new Node("", 0, {x: 0, y: 0}, 512, 512, 992, 992, 1);
var quad = new Quadtree(root, 3, 16.0);
quad.update();
var canvas = document.getElementById("quad");
var ctx = canvas.getContext("2d");
var index = 6;
function checkNeighbour(index_, index2_, array_){
return array_[index2_][index_] == 1 ? true : false;
}
function drawQuad(index_){
ctx.clearRect(0, 0, canvas.width, canvas.height);
quad.nodes.forEach(function(node_, i_){
if(index_ < quad.nodes.length && index_ == i_) { ctx.fillStyle = "#FF00FF"; }
else if(index_ < quad.nodes.length && checkNeighbour(i_, index_, quad.adjacency)) { ctx.fillStyle = "#00FFFF"; }
else { ctx.fillStyle = "transparent"; }
//contours
var points = node_.getEdges();
ctx.beginPath();
ctx.moveTo(points[0].x, points[0].y);
for(var i = 1; i < points.length; i++){ ctx.lineTo(points[i].x, points[i].y); }
ctx.lineTo(points[0].x, points[0].y);
ctx.fill();
ctx.strokeStyle = "#000000";
ctx.stroke();
})
}
function generateAdjacencyTable(){
var adjacencyTbl = [];
for(var x = 0; x < quad.adjacency.length + 1; x++){
adjacencyTbl[x] = [];
for(var y = 0; y < quad.adjacency[0].length + 1; y++){
if(x == 0 && y == 0) { adjacencyTbl[x][y] = "-"; }
else if(x == 0) { adjacencyTbl[x][y] = quad.nodes[y - 1].id; }
else if(y == 0) { adjacencyTbl[x][y] = quad.nodes[x - 1].id; }
else { adjacencyTbl[x][y] = quad.adjacency[x - 1][y - 1]; }
}
}
if(document.getElementById("adjTable") != undefined){
var oldTbl = document.getElementById("adjTable");
oldTbl.parentNode.removeChild(oldTbl);
}
var body = document.getElementsByTagName("body")[0];
var tbl = document.createElement("table");
tbl.style = "margin: 8px;";
tbl.id = "adjTable";
var tblBody = document.createElement("tbody");
for(var j = 0; j < adjacencyTbl.length; j++) {
var row = document.createElement("tr");
for(var i = 0; i < adjacencyTbl[j].length; i++) {
var cell = document.createElement("td");
var cellText = document.createTextNode(adjacencyTbl[i][j]);
cell.appendChild(cellText);
row.appendChild(cell);
}
tblBody.appendChild(row);
}
tbl.appendChild(tblBody);
body.appendChild(tbl);
tbl.setAttribute("border", "1");
}
document.addEventListener("mousemove", onMouseMoveEvent, false);
function onMouseMoveEvent(event_){
var rect = canvas.getBoundingClientRect();
mouse = {
x: (event_.clientX - rect.left) * 2,
y: (event_.clientY - rect.top) * 2
};
quad.update();
drawQuad(6);
generateAdjacencyTable();
}
body { margin: 0; }
tbody td:first-child, tr:first-child { background: rgb(192, 192, 192); }
<!DOCTYPE html>
<html>
<head>
<meta charset="utf-8" />
</head>
<body>
<canvas id="quad" width="1024" height="1024" style="width: 512px; height: 512px;"></canvas>
</body>
</html>