计算思维导图的径向几何

Question

我正在尝试以不重叠的方式间隔链接节点。生成位置的算法如下：

const span = 180 * Math.PI/180;

function genPositionsRecursive(node, depth=0) {
     if (node.children) {
        const radius = 1;
        const slice = depth === 0 ? 2 * Math.PI / node.children.length : span / (node.children.length  + 1)
        for (let i = 0; i < node.children.length; i++) {
            const child = node.children[i]
            const angle = depth === 0 ? slice * i : (node.angle) + slice*(i+1) - (span/2)
            child.angle = angle;
            child.x = node.x + (radius * Math.cos(angle));
            child.y = node.y + (radius * Math.sin(angle));

            genPositionsRecursive(child, depth+1)
        }
    }
}

问题在于它们可能重叠。

我有兴趣调整每个节点的半径（可能还有跨度）以防止节点重叠。

阻止相对较近的邻居重叠更简单。可以使用圆形或三角形计算重叠，并据此进行调整。

但是更困难的是更远的邻居重叠的情况，例如：

图像中的问题特别困难的是来自橙色分支的节点在其最左/最右分支上不重叠。

递归计算三角形（使用最左边/最右边的节点）是相当简单的，从最外面的分支开始，向内移动，边走边进行调整。但针对上述问题这样做会产生太大的三角形，从而在分支之间留下太多空间。

所以我想要一些关于如何计算节点位置的建议，以免它们重叠。

Answer 1

我认为您的解决方案几乎是正确的，并且将此类重叠视为其他通常正确的算法的例外是有意义的，也就是说，每当添加新段时，检查该段是否与先前添加的段重叠。如果您有一组已存在的段，您可以循环这些段并查看它们是否与新段重叠。

直线的可能方程：

• x = a（水平）
• y = b（垂直）
• y = cx + d（任何其他）

现在，所有旧线段都在这样一条线上，具有第一个方程，即 E1，而新线段则在由 E2 定义的线上。因此，您需要找出哪个 (x, y) 值同时符合 E1 和 E2，然后检查线的交汇点是否位于线段内部。

一段：

• x = a（水平），a1 <= y <= a2
• y = b（垂直），b1 <= x <= b2
• y = cx + d（任何其他）x1 <= x <= x2; y1 <= y <= y2

因此，解完直线方程后，应用线段约束并查看结果是否为空集。如果是这样，则新线段不会与旧线段重叠，否则它们会重叠，您需要调整至少其中之一。调整可以是重复旋转，直到没有重叠。

如果通过旋转无法解决，则还需要旋转该线段的父级，依此类推。但也许这没有必要。