我将以下对象堆叠在一维数组中:
var colors = ["#FF0000", "#00FF00", "#0000FF", "#FF00FF", "#00FFFF"];
var array1D = [
{ level: 1, x: 0, y: 0 },
{ level: 1, x: 0, y: 1 },
{ level: 1, x: 1, y: 0 },
{ level: 4, x: 8, y: 8 },
{ level: 4, x: 8, y: 9 },
{ level: 5, x: 18, y: 16 },
{ level: 5, x: 18, y: 17 },
{ level: 5, x: 19, y: 16 },
{ level: 5, x: 19, y: 17 },
{ level: 5, x: 18, y: 18 },
{ level: 5, x: 18, y: 19 },
{ level: 5, x: 19, y: 18 },
{ level: 5, x: 19, y: 19 },
{ level: 4, x: 8, y: 10 },
{ level: 4, x: 8, y: 11 },
{ level: 5, x: 18, y: 20 },
{ level: 5, x: 18, y: 21 },
{ level: 5, x: 19, y: 20 },
{ level: 5, x: 19, y: 21 },
{ level: 4, x: 9, y: 11 },
{ level: 5, x: 20, y: 16 },
{ level: 5, x: 20, y: 17 },
{ level: 5, x: 21, y: 16 },
{ level: 5, x: 21, y: 17 },
{ level: 5, x: 20, y: 18 },
{ level: 5, x: 20, y: 19 },
{ level: 5, x: 21, y: 18 },
{ level: 5, x: 21, y: 19 },
{ level: 4, x: 11, y: 8 },
{ level: 5, x: 22, y: 18 },
{ level: 5, x: 22, y: 19 },
{ level: 5, x: 23, y: 18 },
{ level: 5, x: 23, y: 19 },
{ level: 5, x: 20, y: 20 },
{ level: 5, x: 20, y: 21 },
{ level: 5, x: 21, y: 20 },
{ level: 5, x: 21, y: 21 },
{ level: 4, x: 10, y: 11 },
{ level: 5, x: 22, y: 20 },
{ level: 5, x: 22, y: 21 },
{ level: 5, x: 23, y: 20 },
{ level: 5, x: 23, y: 21 },
{ level: 4, x: 11, y: 11 },
{ level: 2, x: 2, y: 3 },
{ level: 2, x: 3, y: 2 },
{ level: 2, x: 3, y: 3 }
];
它基本上是一个四叉树结构,因此您不需要验证是否可以从中构建树。
外观上看起来像下面的插图:
viz的代码非常简单:
quad.sort(function(a_, b_){ return a_.level - b_.level; })
var canvas = document.createElement("canvas");
document.body.appendChild(canvas)
canvas.width = 512;
canvas.height = 512;
var ctx = canvas.getContext("2d");
quad.forEach(function(node_){
ctx.fillStyle = colors[node_.level - 1];
var w = 256;
for(var i = 0; i < node_.level; i++) { w /= 2; }
var x = 256;
for(var i = 0; i < node_.level; i++) { x /= 2; }
x *= node_.x;
var y = 256;
for(var i = 0; i < node_.level; i++) { y /= 2; }
y *= node_.y;
ctx.fillRect(x + 1, y + 1, w - 2, w - 2);
});
任务是以最快的方式从这些节点中构建树,以获得类似这样的内容:
var result = [
{id: "0.1", children: null },
{id: "0.2", children: null },
{id: "0.3", children: null },
{id: "0.4", children: [
{ id: "0.1.1", children: [
...
] },
{ id: "0.1.2", children: [] },
{ id: "0.1.3", children: [] },
{ id: "0.1.4", children: [] },
] }
];
更新:
ID是通过这种逻辑生成的-左上是1,右上是2,左下是3,右下是4。
因此,底部的左侧绿色方块是4.3,右侧的邻居是4.4。第一个洋红色正方形是4.1.1。
在初始一维数组级别中,x和y值负责定位和缩放分区,因此您始终可以通过这些值获取其级别和父级。
我需要使用这些级别,x和y值将一维数组转换为二维树。
我正在尝试理解并构建它,我有一个似乎可行的解决方案,但是要求级别不要“跳跃”(即连续),因此在您的示例中,没有级别3表示有效?我创建了一个稍微简化的示例,以说明如何在连续关卡中工作:
const colors = ["#FF0000", "#00FF00", "#0000FF", "#FF00FF", "#00FFFF"];
const array1D = [
{ level: 1, x: 0, y: 0 },
{ level: 1, x: 16, y: 0 },
{ level: 1, x: 0, y: 16 },
//*
//*
{ level: 3, x: 16, y: 16 },
{ level: 3, x: 20, y: 16 },
{ level: 3, x: 16, y: 20 },
{ level: 3, x: 20, y: 20 },
//*/
{ level: 2, x: 24, y: 16 },
{ level: 2, x: 16, y: 24 },
{ level: 2, x: 24, y: 24 }
//*
];
const arrayNested = createdNestedQuadTree(array1D);
console.log(arrayNested);
function createdNestedQuadTree(input, level) {
const nestedOutput = [];
//don't mutate input, call with shallow copy:
innerRecursive([...input], nestedOutput);
function innerRecursive(currArr, parentArr, level){
const currentLevel = level || 1;
const currentChildren = [];
const pointOfNesting = {};
for (let i of [1,2,3,4]){
const item = currArr[i-1];
//console.log(currentLevel, i, item);
if (currentLevel == item.level){
item.id = `${currentLevel}.${i}`;
item.children = null;
parentArr.push(item);
//console.log('output', nestedOutput);
}
else {
pointOfNesting.id = `${currentLevel}.${i}`;
pointOfNesting.children = [];
parentArr.push(pointOfNesting);
//console.log('parent', parentArr);
let child = currArr[i-1];
let j = i - 1;
let position = 1;
//console.log(child);
while (child && child.level > currentLevel){
//console.log('child', child);
currentChildren.push(child);
j +=1;
child = currArr[j];
}
currArr.splice(i-1, (j - (i-1) ) );
currArr.splice(i-1, 0, pointOfNesting);
//console.log('curr', currArr);
//console.log('parent', parentArr);
//console.log('children', currentChildren);
//console.log('output', nestedOutput);
innerRecursive([...currentChildren], pointOfNesting.children, currentLevel + 1)
}
}
}
return nestedOutput;
}
.as-console-wrapper { max-height: 100% !important; top: 0; }
输出:
[
{
"level": 1,
"x": 0,
"y": 0,
"id": "1.1",
"children": null
},
{
"level": 1,
"x": 16,
"y": 0,
"id": "1.2",
"children": null
},
{
"level": 1,
"x": 0,
"y": 16,
"id": "1.3",
"children": null
},
{
"id": "1.4",
"children": [
{
"id": "2.1",
"children": [
{
"level": 3,
"x": 16,
"y": 16,
"id": "3.1",
"children": null
},
{
"level": 3,
"x": 20,
"y": 16,
"id": "3.2",
"children": null
},
{
"level": 3,
"x": 16,
"y": 20,
"id": "3.3",
"children": null
},
{
"level": 3,
"x": 20,
"y": 20,
"id": "3.4",
"children": null
}
]
},
{
"level": 2,
"x": 24,
"y": 16,
"id": "2.2",
"children": null
},
{
"level": 2,
"x": 16,
"y": 24,
"id": "2.3",
"children": null
},
{
"level": 2,
"x": 24,
"y": 24,
"id": "2.4",
"children": null
}
]
}
]
对应于此四叉树(32 x 32):
这里是一个更复杂的示例(但又是连续的::]
const colors = ["#FF0000", "#00FF00", "#0000FF", "#FF00FF", "#00FFFF"]; const array1D = [ { level: 1, x: 0, y: 0 }, { level: 1, x: 16, y: 0 }, { level: 1, x: 0, y: 16 }, //* <level 2> //* <level 3> { level: 3, x: 16, y: 16 }, //* <level 4> { level: 4, x: 20, y: 16 }, //* <level 5> { level: 5, x: 22, y: 16 }, { level: 5, x: 23, y: 16 }, { level: 5, x: 22, y: 17 }, { level: 5, x: 23, y: 17 }, //*/ </level 5> { level: 4, x: 20, y: 18 }, { level: 4, x: 22, y: 18 }, //*/ </level 4> { level: 3, x: 16, y: 20 }, { level: 3, x: 20, y: 20 }, //*/ </level 3> { level: 2, x: 24, y: 16 }, { level: 2, x: 16, y: 24 }, { level: 2, x: 24, y: 24 } //* </level 2> ]; const arrayNested = createdNestedQuadTree(array1D); console.log(arrayNested); function createdNestedQuadTree(input, level) { const nestedOutput = []; //don't mutate input, call with shallow copy: innerRecursive([...input], nestedOutput); function innerRecursive(currArr, parentArr, level){ const currentLevel = level || 1; const currentChildren = []; const pointOfNesting = {}; for (let i of [1,2,3,4]){ const item = currArr[i-1]; //console.log(currentLevel, i, item); if (currentLevel == item.level){ item.id = `${currentLevel}.${i}`; item.children = null; parentArr.push(item); //console.log('output', nestedOutput); } else { pointOfNesting.id = `${currentLevel}.${i}`; pointOfNesting.children = []; parentArr.push(pointOfNesting); //console.log('parent', parentArr); let child = currArr[i-1]; let j = i - 1; let position = 1; //console.log(child); while (child && child.level > currentLevel){ //console.log('child', child); currentChildren.push(child); j +=1; child = currArr[j]; } currArr.splice(i-1, (j - (i-1) ) ); currArr.splice(i-1, 0, pointOfNesting); innerRecursive([...currentChildren], pointOfNesting.children, currentLevel + 1) } } } return nestedOutput; }
.as-console-wrapper { max-height: 100% !important; top: 0; }
输出:
[ { "level": 1, "x": 0, "y": 0, "id": "1.1", "children": null }, { "level": 1, "x": 16, "y": 0, "id": "1.2", "children": null }, { "level": 1, "x": 0, "y": 16, "id": "1.3", "children": null }, { "id": "1.4", "children": [ { "id": "2.1", "children": [ { "level": 3, "x": 16, "y": 16, "id": "3.1", "children": null }, { "id": "3.2", "children": [ { "level": 4, "x": 20, "y": 16, "id": "4.1", "children": null }, { "id": "4.2", "children": [ { "level": 5, "x": 22, "y": 16, "id": "5.1", "children": null }, { "level": 5, "x": 23, "y": 16, "id": "5.2", "children": null }, { "level": 5, "x": 22, "y": 17, "id": "5.3", "children": null }, { "level": 5, "x": 23, "y": 17, "id": "5.4", "children": null } ] }, { "level": 4, "x": 20, "y": 18, "id": "4.3", "children": null }, { "level": 4, "x": 22, "y": 18, "id": "4.4", "children": null } ] }, { "level": 3, "x": 16, "y": 20, "id": "3.3", "children": null }, { "level": 3, "x": 20, "y": 20, "id": "3.4", "children": null } ] }, { "level": 2, "x": 24, "y": 16, "id": "2.2", "children": null }, { "level": 2, "x": 16, "y": 24, "id": "2.3", "children": null }, { "level": 2, "x": 24, "y": 24, "id": "2.4", "children": null } ] } ]
对应于此四叉树(32 x 32):