逻辑将策略性地将项目放置在具有最小重叠连接的容器中
这更像是一个算法问题。 我有一个页面，使用javaScript通过绘制从源到目标的箭头连接显示项目和项目与其他项目的关系（想想jsPlumb）。 每个项目可以有0个或更多连接。 我面临的挑战是以最佳方式战略性地将div /圈放置在容器中。
- 最佳：最少连接数（连接两个圆圈的箭头）重叠
可视示例：下图是未经优化的显示版本，已将圆圈随机放置在容器内。
请注意，在上图中，连接（箭头）重叠的数量不必要地高。 下图是一个优化的解决方案，在这个小例子中，圆圈位于更好的位置，导致连接没有重叠：
放置物品的容器尺寸为1020×800。 存在大量圆圈的地方总会有重叠，因此我们的想法是尽量减少连接重叠的数量。 我希望能够做到这一点的例子，因为我发现阅读算法文章有点令人生畏:(。
方法1
用于布局图的一类非常好的算法是基于仿真的算法。 在这些算法中，您可以将图形建模为具有物理属性的物理对象。
在这种情况下，想象图形的节点是相互排斥的球，而边缘是弹簧或橡胶，将图形保持在一起。 节点彼此越接近，例如它们的距离的倒数平方，排斥力越强，并且每个弹簧的张力与其长度成比例。 排斥力将使节点尽可能远离其他节点，并且图形将解开。 当然，你必须稍微试验系数才能获得最佳效果（但我保证 – 这很有趣）。
这种方法的主要优点是：
- 易于编码 – 嵌套循环计算每个节点 – 节点对之间的力并更新节点位置
- 适用于各种平面或非平面图形
- 很有趣的实验
- 如果你让它互动，例如允许用户用鼠标移动节点 – 它吸引人们，每个人都想“玩图形”
这种方法的缺点是：
- 它可能会陷入局部能量最低限度（摇动或帮助手动帮助）
- 它不是非常快（但可以做一个很好的动画）
类似的方法可用于布局/解开结。
示例代码
您可以在此处查看此代码的工作原理。 刷新页面以获取不同的图形。 当然，有时它找不到全局最小值并且有更多的交叉边缘 - 所以如果结果不满足你，你可以添加随机抖动。
方法2
这个问题类似于PCB设计中的布线问题。 如果您对方法1提供的简单易用的解决方案不满意，可以使用自动布线方法改进解决方案。 例如，您可以将节点放在网格上，然后使用A *算法查找连接它们的最短路径。
- 使用方法1找到次优的初始解决方案（可选）。
- 删除所有边缘。 将节点放在网格上（将其坐标向上舍入）。 网格必须具有足够的分辨率，以便没有两个节点重叠。
- 按升序近似长度对边缘进行排序（使用欧几里得或曼哈顿度量）。
- 对于每个边缘使用A *算法来查找连接节点的最短路径。 作为成本函数，不仅使用距离源节点的距离，而且还为步进到先前已路由的任何边缘已经采用的任何网格点上添加足够大的代价。
- 将上一步中找到的路径上的网格点标记为“已拍摄”，因此所有下一条边将有利于不踩踏/与此路径相交的路径。
上面的算法是一种贪婪的启发式算法，遗憾的是它并不能保证最优解，因为结果取决于路由边缘的顺序。 您可以通过移除跨越另一条边的随机边缘并重新路由它来进一步改进解决方案。
步骤1.是可选的，使图形布局更加规则，并使平均连接距离变小，但不应影响交叉点的数量（如果网格具有足够的分辨率）。
它看起来像简单的闭合多边形提取给我。 尝试这个：
- 忘记连接方向删除所有冗余连接（双向连接是重复的）
-
找到所有闭环
起始点始终是容器，具有多于2个连接（或仅与1），因此循环通过未使用的相邻容器，直到返回起始点（将此路径设置为已使用）或直到到达端点（仅1个连接，也将此路径设置为使用）或直到到达十字路口（连接> 2，也设置此路径使用）。
-
重复，直到容器之间没有未使用的线。
在此之后，您将图形分解为非交叉部分。
现在将它们连接在一起，因此没有连接相交。 共享连接在内部，非共享连接在外部。 开环（带端点）可以在任何地方。
我希望这有帮助
我认为基于仿真的算法是最好的选择，但是，因为你的目标是最小化重叠弧而不是优化节点的分布，你应该在弧之间（不在节点之间）应用排斥力并将节点用作弹簧。
迭代：
- 对于图中的每个弧计算其中心点（平均起点与终点）
- 对于每对弧线，在它们的中心之间施加排斥（弧的两个极端相应地移动）
- 对于图中的每个节点，将其新位置计算为连接弧的平均值，并更新弧的相关端点
您还可以添加收缩阶段，其中节点被吸引到图形的中间（所有节点的坐标的平均值）。
达到某个稳定性阈值时停止迭代。