JavaScript Flat one dimensional array to tree

Question

I have following objects stacked in a 1D array:

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 }

];

It's basically a quadtree structure, so you don't need to validate if you can build a tree from it or not.

Visually it looks like following illustration:

enter code here

The code for viz is very simple:

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);

});

The task is to build a tree out of these nodes in a fastest way as possible to get something like this:

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: [] },

    ] }

];

UPDATE:

ID's are generating by this logic—top-left is 1, top-right is 2, bottom-left is 3, bottom-right is 4.

So, i.e. left green square at the bottom is 4.3, its neighbour to the right is 4.4. The first magenta square is 4.1.1.

In initial 1D array level, x and y values are in charge of positioning and scaling partitions, so you could always get its level and parents by these values.

All I need to convert 1D array to 2D tree by using these level, x and y values.

I don't understand your question, which one is the actual array structure you want to convert from a 1D array to a 2D array and how would the items in the 2D array look like? also where is this ID {id: "0.1", children: null } coming from?, you need to give us more assertive and informative questions. — Bargros
– Bargros, Commented Jun 4, 2020 at 14:35
Seems like an interesting problem (and I'd like to solve it). I had not heard of quadtrees before just now (i2.wp.com/static.notdot.net/uploads/quadtree.png). I don't fully understand if or how your picture is a valid quadtree - can you explain? From all the example I see, perhaps it should look more like this - i.sstatic.net/kDNAe.png? (i.e. It seemed to me like you always have to split into 4 equal areas first before then continuing to do this recursively, or have I understood that incorrectly?) — Alex L
– Alex L, Commented Jun 4, 2020 at 16:07
You're right, it's not a classical quadtree, but have a very similar structure. — VVK
– VVK, Commented Jun 4, 2020 at 16:09
But it doesn't really matter, cause level, x and y determine each node position at tree. — VVK
– VVK, Commented Jun 4, 2020 at 17:46

Alex L · Accepted Answer · 2020-06-04 19:16:30Z

I am trying to understand and to build it, I have a solution that seems to work, but requires the levels not to "jump" (i.e. be continuous), so in your example, there is no level 3, is that valid? I created a slightly simplified example to show how this can work for continuous levels:

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; }

Output:

[
  {
    "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
      }
    ]
  }
]

Corresponding to this quadtree (32 x 32):

Here is a more complex example (but again continuous):

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; }

Output:

[
  {
    "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
      }
    ]
  }
]

Corresponding to this quadtree (32 x 32):

I have also found another solution, but your's better. Cheers.
It's pseudo quadtree and I don't need 3 level if it's not there. It's for geomap tiling based on simple LoD algorithm.
So my answer is helpful (if so please consider to up-vote) but not perfect as it only works for "strict" quadtrees? For your "pseudo" quadtree, my function would have to be adapted somehow... (I have some ideas but not 100% sure). Hopefully this at least leads you in the right direction. I will think more about non-contunuous quadtrees...

Collectives™ on Stack Overflow

JavaScript Flat one dimensional array to tree

1 Answer 1

3 Comments

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

3 Comments

Your Answer

Sign up or log in

Post as a guest

Linked

Related