main.js

function main() {
  const output = groupNode(node2);
  console.log(output);
}


/**
 * Case 1: Both rows can be middle alignment
 */
const node1 = {
  x: 0,
  y: 0,
  width: 1000,
  height: 1000,
  children: [
    { id: "1", x: 30, y: 30, width: 50, height: 30 },
    { id: "2", x: 400, y: 0, width: 100, height: 90 },
    { id: "3", x: 700, y: 20, width: 60, height: 50 },
    { id: "4", x: 500, y: 400, width: 50, height: 50 },
    { id: "5", x: 700, y: 200, width: 50, height: 450 },
  ]
}

/**
 * Case 2: First row can be middle alignment and second row can be top alignment
 */
const node2 = {
  x: 0,
  y: 0,
  width: 1000,
  height: 1000,
  children: [
    { id: "1", x: 30, y: 30, width: 50, height: 30 },
    { id: "2", x: 400, y: 0, width: 100, height: 90 },
    { id: "3", x: 700, y: 20, width: 60, height: 50 },
    { id: "4", x: 500, y: 400, width: 50, height: 50 },
    { id: "5", x: 700, y: 400, width: 50, height: 60 },
    { id: "6", x: 129, y: 192, width: 50, height: 60 },
  ]
}

/**
 * Case 3: First row can be middle alignment and second row can be bottom alignment
 */
const node3 = {
  x: 0,
  y: 0,
  width: 1000,
  height: 1000,
  children: [
    { id: "1", x: 30, y: 30, width: 50, height: 30 },
    { id: "3", x: 400, y: 0, width: 100, height: 90 },
    { id: "4", x: 700, y: 20, width: 60, height: 50 },
    { id: "5", x: 500, y: 400, width: 50, height: 50 },
    { id: "6", x: 700, y: 200, width: 50, height: 250 },
  ]
}

main();

solution.js

function groupNode(parent) {
  const nodes = parent.children.map(p => ({
    ...p,
    centroid: {
      x: p.x + p.width / 2,
      y: p.y + p.height / 2,
    },
  }));

  // a super set of elements in strategies
  const sets = [
    ...groupBy(nodes, item => item.x),                // left alignment
    ...groupBy(nodes, item => item.x + item.width),   // right alignment
    ...groupBy(nodes, item => item.centroid.x),       // center alignment
    ...groupBy(nodes, item => item.y),                // top alignment
    ...groupBy(nodes, item => item.y + item.height),  // bottom alignment
    ...groupBy(nodes, item => item.centroid.y),       // middle alignment
  ];

  // create a mapping: node.id => node
  const nodeMapping = nodes.reduce((prev, curr) => ({
    ...prev,
    [curr.id]: curr,
  }), {});
  const needCoveredIds = Object.keys(nodeMapping)

  /**
   * find list of sets:
   * - cover all of elements
   * - number of sets is minimum
   * - sets aren't collapsed
   */
  const optimalSolution = findMinSubsetCover(sets, needCoveredIds);
  return optimalSolution.reduce((prev, curr) => ([
    ...prev,
    Array.from(curr).map(id => nodeMapping[id])
  ]), []);
}

// Function to find the minimum subset cover using a greedy algorithm
function findMinSubsetCover(sets, items) {
  const uncoveredItems = items;
  const selectedSets = [];

  while (uncoveredItems.size > 0) {
    let maxCovered = 0;
    let bestSet = null;

    // Find the set that covers the maximum number of uncovered items
    for (const set of sets) {
      const coveredItems = new Set([...set].filter(item => uncoveredItems.has(item)));
      if (coveredItems.size > maxCovered) {
        maxCovered = coveredItems.size;
        bestSet = set;
      }
    }

    if (bestSet !== null) {
      selectedSets.push(new Set(bestSet)); // Store a copy of the set
      for (const item of bestSet) {
        uncoveredItems.delete(item);
      }
    } else {
      // No set covers any additional items, break the loop
      break;
    }
  }

  return selectedSets;
}

// Group elements by specific strategy
function groupBy(items, keyFunc) {
  const group = items.reduce((prev, item) => {
    const key = keyFunc(item);
    if (prev[key] === undefined) {
      prev[key] = new Set();
    }
    prev[key].add(item.id);

    return prev;
  }, {});
  return Object.values(group);
}

This function presents an approximate solution for non-collapsed nodes.

• Initially, it organizes elements into groups based on a specific strategy, such as left/right/top/... alignment.
• Subsequently, it combines these groups to generate an enhanced result.
  The combination algorithm constructs a group that covers/non-collapse all elements and minimize number of groups, ensuring a comprehensive and improved outcome.

In this solution, I have adopted the notion that a pixel serves as a unit in the 2D coordinate system, acknowledging its abstraction from real-world accuracy.

In reality, we may treat both positions (0, 0) and (3, 3) as referencing the same point. To address this, various techniques such as rounding or scaling for the desired axis can be employed.

For instance, in the following example, I apply rounding to the positions of four points: (492, 540), (494, 200), (370, 126), and (401, 128).
The transformed coordinates become (490, 540), (490, 200), (370, 130), and (400, 130).
This adjustment aids in aligning the points within the context of the coordinate system.

Due to the non-collapse nodes assumption, this solution is not designed to address collapse cases.

In practical scenarios, designers may create sibling nodes that should ideally be nested. To handle such cases, data preprocessing is recommended before passing it to this function.

To facilitate this, the function isRectangleContained is introduced below. It returns true if the inner rectangle is entirely contained within the outer rectangle; otherwise, it returns false.

function isRectangleContained(inner, outer) {
  return (
    inner.x >= outer.x &&
    inner.y >= outer.y &&
    inner.x + inner.width <= outer.x + outer.width &&
    inner.y + inner.height <= outer.y + outer.height
  );
}

We can use a function, that implements a brute-force algorithm that traverses all nodes for restructuring.

function perProcess(nodes) {
  const n = nodes.length;
  const removedNodes = new Set();
  for (const i = 0; i < n; ++i) {
    if (removedNodes.has(nodes[i].id)) continue;

    for (const j = 0; j < n; ++j) {
      if (i === j || removedNodes.has(nodes[j].id)) continue;

      if (isRectangleContained(nodes[i], nodes[j])) {
        nodes[j].children.push(nodes[i]);
        removedNodes.add(nodes[j].id);
      }
    }
  }
  return nodes.filter(node => !removedNodes.has(node.id));
}