如何为树中的每个ID设置坐标（x，y）

Question

当我尝试计算每个ID的位置时，我有一个问题，以便我可以从层次上将它们分布在画布上。 它可以是一棵树或许多树（我想它称为森林）。 不能是周期。 盒子需要吗？ 240 x 100。

我从获得的连接开始： ConnectionSarr 。

函数内部 graphWithTopleft 是我计算每个ID的位置的方式，在我的示例中，某些ID彼此顶部＆amp;它们之间的间距不是我想要的。

最后，我尝试在所有情况下都能得到这样的东西：

​

预先感谢那些帮助并会提供帮助的人。

代码示例： codesandbox ＆amp;也在这里。

const connectionsArr = [
  { sourceId: 1, targetId: 2 },
  { sourceId: 1, targetId: 3 },
  { sourceId: 1, targetId: 4 },

  { sourceId: 2, targetId: 5 },
  { sourceId: 2, targetId: 6 },
  { sourceId: 2, targetId: 7 },
  { sourceId: 2, targetId: 8 },
  { sourceId: 3, targetId: 10 },
  { sourceId: 3, targetId: 9 },
  { sourceId: 4, targetId: 11 },
  { sourceId: 4, targetId: 12 },
  { sourceId: 11, targetId: 12 },
  { sourceId: 13, targetId: 12 }
];
const WIDTH = 200;

//Find the roots id
function findParents(connections) {
  const parents = [];
  const notParents = [];
  connections.forEach((con1) => {
    const t = connections.filter((cf) => cf.targetId === con1.sourceId);
    t.forEach((t2) => notParents.push(t2.targetId));
  });

  const allIds = connections.map((con) => con.sourceId);
  const arrayWithDuplicate = allIds.filter((val) => !notParents.includes(val));
  arrayWithDuplicate.forEach((a, index) => {
    if (!parents.find((p) => a === p)) {
      parents.push(a);
    }
  });
  return parents;
}
//return arrays of objects (object is like a tree)
function getTrees(flatList) {
  const graph = [];
  flatList.forEach((item) => {
    if (!graph[item.sourceId]) {
      graph[item.sourceId] = {
        id: item.sourceId,
        children: []
      };
    }
    if (!graph[item.targetId]) {
      graph[item.targetId] = {
        id: item.targetId,
        children: []
      };
    }
    graph[item.sourceId].children.push(graph[item.targetId]);
  });
  return graph;
}
//function that return the number of the vertex all the way to the id given
function getAllIds(connections, id) {
  const result = [];
  connections.forEach((connection) => {
    if (connection.sourceId === id) {
      result.push(connection.targetId);
      result.push(...getAllIds(connections, connection.targetId));
    }
  });
  return result;
}
//function that return tree with levels
function updateLevels(trees, level) {
  for (let i = 0; i < trees.length; i++) {
    if (trees[i].children && trees[i].children.length) {
      updateLevels(trees[i].children, level + 1) //next level for children
    }
    trees[i].level = level;
  }
  return trees;
}
//get the max children in the level tree
function getMaxChildren(tree) {
  let max = 0;
  let id = 1;
  const getMax = (node) => {
    if (node.children) {
      if (node.children.length > max) {
        max = node.children.length;
        id = node.id;
      }
      node.children.forEach((child) => {
        getMax(child);
      });
    }
  };
  getMax(tree);
  return { max, id };
}

const parents = findParents(connectionsArr);
// console.log(parents);

const filterArray = getTrees(connectionsArr).filter(
  (f, index) =>
    f.id === parents[0] || f.id === parents[1] || f.id === parents[2]
);

const updated = updateLevels(filterArray, 0);
// console.log( JSON.stringify(updated, null, "   ") );

//get the tree hight
function getDepth(jsonTree) {
  let depth = 0;
  const recurse = (obj, currentDepth) => {
    if (obj.children) {
      depth = Math.max(depth, currentDepth);
      obj.children.forEach((child) => recurse(child, currentDepth + 1));
    }
  };
  recurse(jsonTree, 0);
  return depth;
}

function graphWithTopLeft(
  trees,
  newPositionNodes= [],
  index = 0,
  depth = 0,
  parent = 0
) {
  const findLevel = trees
    .filter((lev) => lev.level === index)
    .sort((a, b) =>
      getAllIds(connectionsArr, a.id).length <
      getAllIds(connectionsArr, b.id).length
        ? 1
        : -1
    );

  findLevel.forEach((node, indexLevel) => {
    if (node.level === 0) {
      const y = 0;
      const x =
        indexLevel === 0
          ? 0
          : indexLevel *
            getAllIds(connectionsArr, findLevel[indexLevel].id).length *
            findLevel.length *
            200;

      newPositionNodes.push({
        id: node.id,
        name: `Node${node.id}`,
        left: x,
        top: y,
        isDragging: false
      });
    }
    if (node.level === 1) {
      const getMaxChildInLevel = getMaxChildren(node);
      const findParent = newPositionNodes.find((f) => f.id === parent);
      const axisX =
        Math.pow(findLevel.length, depth - 1) * getMaxChildInLevel.max;
      const y = node.level * WIDTH;
      const x =
        indexLevel === 0
          ? -(axisX / 3) - (indexLevel * WIDTH + WIDTH)
          : axisX / 3 + indexLevel <= 1
          ? (findParent?.left ) +
            indexLevel *
              WIDTH *
              (node.children.length > 0 ? node.children.length : 1)
          : (newPositionNodes[indexLevel - 1]?.left) +
            indexLevel * WIDTH * node.children.length;

      if (axisX === 0 && indexLevel === 0) {
        if (!newPositionNodes.find((n) => n.id === node.id)) {
          const findParent = newPositionNodes.find((f) => f.id === parent);
          newPositionNodes.push({
            id: node.id,
            name: `Node${node.id}`,
            left: findParent?.left ,
            top: y,
            isDragging: false
          });
        }
      } else if (!newPositionNodes.find((n) => n.id === node.id)) {
        newPositionNodes.push({
          id: node.id,
          name: `Node${node.id}`,
          left: x,
          top: y,
          isDragging: false
        });
      }
    } else {
      if (!newPositionNodes.find((n) => n.id === node.id)) {
        const findParent = newPositionNodes.find((f) => f.id === parent);
        const y = (node.level ) * WIDTH;
        const x =
          indexLevel === 0
            ? (findParent?.left) - WIDTH
            : indexLevel <= 1
            ? (findParent?.left) +
              indexLevel *
                WIDTH *
                (node.children.length > 0 ? node.children.length : 1)
            : (newPositionNodes[indexLevel - 1]?.left) +
              indexLevel * WIDTH * node.children.length;

        if (findLevel.length <= 1) {
          newPositionNodes.push({
            id: node.id,
            name: `Node${node.id}`,
            left: findParent?.left,
            top: y,
            isDragging: false
          });
        } else {
          newPositionNodes.push({
            id: node.id,
            name: `Node${node.id}`,
            left: x,
            top: y,
            isDragging: false
          });
        }
      }
    }
  });

  for (let i = 0; i < trees.length; i++) {
    const depth = getDepth(trees[i]);
    if (trees[i].children && trees[i].children?.length > 0) {
      graphWithTopLeft(
        trees[i].children,
        newPositionNodes,
        index + 1,
        depth,
        trees[i].id
      );
    }
  }

  return newPositionNodes;
}

const display = graphWithTopLeft(updated, [], 0);

console.log(display);

// <------------------------------Canvas------------------------------>

const canvas = document.querySelector("#paper");

const WIDTHcA = canvas.width;
const HEIGHTCA = canvas.height;
// drag related variables
let dragok = false;
let startX;
let startY;


const ctx = canvas.getContext("2d");

function clear() {
  ctx.clearRect(0, 0, WIDTHcA, HEIGHTCA);
}

function drawLine(
  ctx,
  begin,
  end,
  stroke = "black",
  width = 1
) {
  if (stroke) {
    ctx.strokeStyle = stroke;
  }

  if (width) {
    ctx.lineWidth = width;
  }

  ctx.beginPath();
  ctx.moveTo(begin[0] + 100, begin[1] + 100);
  ctx.lineTo(end[0] + 100, end[1]);
  ctx.stroke();
}

const draw = (t) => {
  clear();
  ctx.translate(600, 100);

  ctx.stroke();
  for (let i = 0; i < display.length; i++) {
    const x = display[i].left;
    const y = display[i].top;
    ctx.fillStyle = "red";
    ctx.fillRect(x, y, 200, 100);
    ctx.fillStyle = "white";

    ctx.font = "24px Arial";
    ctx.fillText(display[i].name, display[i].left, display[i].top);
  }

  //draw line
  for (let i = 0; i < connectionsArr.length; i++) {
    const sourcePaths = connectionsArr.filter(
      (f) => f.sourceId === connectionsArr[i].sourceId
    );
    const from = display.find((f) => f.id === connectionsArr[i].sourceId);
    sourcePaths.forEach((s) => {
      const to = display.find((f) => f.id === s.targetId);

      if (to && from)
        drawLine(ctx, [from?.left, from?.top], [to.left, to.top], "green", 1);
    });
  }
};

requestAnimationFrame(draw);

<html>
  <head>
    <title>Sandbox</title>
    <meta charset="UTF-8" />
    <style>
      body {
        background: black;
        margin: 0;
      }
    </style>
  </head>

  <body>
    <canvas id="paper" width="10000" height="10000"></canvas>
    <script src="src/index.ts"></script>
  </body>
</html>

Answer 1

请原谅我的答案，以获取真正的扩展评论。评论框太久了。

这是一个似乎满足您给我们的所有要求的答案：

const unique = (xs) => [... new Set (xs)]

const vertices = (edges) => 
  unique (edges .flatMap (({sourceId, targetId}) => [sourceId, targetId])) .sort ((a, b) => a - b)

const coordinates = (edges) =>
  vertices (edges) .map (v => ({id: v, location: {x: 0, y: 0}}))

const connectionsArr = [{sourceId: 1, targetId: 2}, {sourceId: 1, targetId: 9}, {sourceId: 9, targetId: 3}, {sourceId: 3, targetId: 5}, {sourceId: 3, targetId: 7}, {sourceId: 5, targetId: 6}, {sourceId: 6, targetId: 10}, {sourceId: 11, targetId: 12}]

console .log (coordinates (connectionsArr))

.as-console-wrapper {max-height: 100% !important; top: 0}

对于图中的每个顶点，我们返回一个带有ID和位置属性的元素，后者本身包含数字x和y <y < /代码>属性。结果看起来像这样：

[
  {id: 1,  location: {x: 0, y: 0}},
  {id: 2,  location: {x: 0, y: 0}},
  {id: 3,  location: {x: 0, y: 0}},
  {id: 5,  location: {x: 0, y: 0}},
  {id: 6,  location: {x: 0, y: 0}},
  {id: 7,  location: {x: 0, y: 0}},
  {id: 9,  location: {x: 0, y: 0}},
  {id: 10, location: {x: 0, y: 0}},
  {id: 11, location: {x: 0, y: 0}},
  {id: 12, location: {x: 0, y: 0}},
]

我感到异议。盒子不能全部在同一地点吗？好吧，你为什么不这么说？我们可以很容易地解决该问题。只需将坐标更改为

const coordinates = (edges) =>
  vertices (edges) .map ((v, i) => ({id: v, location: {x: i, y: i}}))

现在它们处于不同的位置，正如我们可以看到的

[
  {id: 1,  location: {x: 0, y: 0}},
  {id: 2,  location: {x: 1, y: 1}},
  {id: 3,  location: {x: 2, y: 2}},
  {id: 5,  location: {x: 3, y: 3}},
  {id: 6,  location: {x: 4, y: 4}},
  {id: 7,  location: {x: 5, y: 5}},
  {id: 9,  location: {x: 6, y: 6}},
  {id: 10, location: {x: 7, y: 7}},
  {id: 11, location: {x: 8, y: 8}},
  {id: 12, location: {x: 9, y: 9}},
]

那样，那是什么？他们不能重叠？好吧，只要使盒子变得足够小，它们不会重叠。你不能那样做吗？好吧，你为什么不这么说呢？盒子需要多大？你不知道吗？好的，我们可以使其成为参数。但是首先，如果我们尝试使用50 x 50怎么样？

哦，等等，您不希望它们排队吗？好的。我们也可以解决这个问题。这是另一种尝试：

const coordinates = (edges) => {
  const vs = vertices (edges)
  const angle = 2 * Math.PI / vs .length
  return vs .map ((v, i) => ({id: v, location: {
    x: Math .round (150 * Math .cos (i * angle)) + 300, 
    y: Math .round (150 * Math .sin (i * angle)) + 300, 
  }}))
}

现在它们根本不会重叠，给我们类似的东西：

这不是您想要的？到目前为止，每个步骤都满足到目前为止给出的所有要求。也许您需要更好的要求：

• 您知道边缘是否形成树？森林？如果是，它是二进制树 /森林吗？< /p>

• 或可能有周期？

• 您知道您的图是平面吗？ （也就是说，它可以在没有边缘的平面上绘制）

• 您希望如何布置节点？甚至与代码示例不匹配的图形的图片几乎没有帮助。

您需要对自己的需求进行更多的思考，并在我们真正帮助您之前进行尝试。