使用solidJS实现力导向图
力导向图参考:https://segmentfault.com/a/1190000016384506
力算法代码:
/**
* @desc 力算法
*/
function force(data, ctx, size) {
const { nodes, links } = data;
// 需要参数
const maxInterval = 300; // 平衡位置间距
const maxOffset = 10; // 最大变化位移
const minOffset = 0; // 最小变化位移
const count = 100; // force次数
const attenuation = 40; // 力衰减
const doforce = () => {
// 计算开始
nodes.forEach(d => {
let [x1, y1] = d.position;
nodes.forEach(e => {
if (d.id === e.id) {
return;
}
let [x2, y2] = e.position;
// 计算两点距离
let interval = Math.sqrt((x2 - x1) * (x2 - x1) + (y2 - y1) * (y2 - y1));
// console.log('interval', d.id + '-' + e.id, interval);
// 力衰减变量
let forceOffset = 0;
let x3, y3;
// 如果大于平横间距,靠拢,如果小于平衡间距,排斥。这里计算第三点的坐标用到了相似三角形原理
if (interval > maxInterval) {
forceOffset = (interval - maxInterval) / attenuation; // 力衰减
forceOffset = forceOffset > maxOffset ? maxOffset : forceOffset;
forceOffset = forceOffset < minOffset ? minOffset : forceOffset;
forceOffset += e.childs.length / attenuation;
// console.log('如果大于平横间距,靠拢', interval, d.id + '-' + e.id, ~~forceOffset);
let k = forceOffset / interval;
x3 = k * (x1 - x2) + x2;
y3 = k * (y1 - y2) + y2;
} else if (interval < maxInterval && interval > 0) { // 如果小于平横间距,分开
forceOffset = (maxInterval - interval) / attenuation; // 力衰减
forceOffset = forceOffset > maxOffset ? maxOffset : forceOffset;
forceOffset = forceOffset < minOffset ? minOffset : forceOffset;
forceOffset += e.childs.length / attenuation;
// console.log('如果小于平横间距,分开', interval, d.id + '-' + e.id, ~~forceOffset);
let k = forceOffset / (interval + forceOffset);
x3 = (k * x1 - x2) / (k - 1);
y3 = (k * y1 - y2) / (k - 1);
} else {
x3 = x2;
y3 = y2;
}
// 边界设置
x3 > size ? x3 -= 10 : null;
x3 < 0 ? x3 += 10 : null;
y3 > size ? y3 -= 10 : null;
y3 < 0 ? y3 += 10 : null;
e.position = [x3, y3];
});
})
}
let countForce = 0;
const forceRun = () => {
setTimeout(() => {
countForce++;
if (countForce > count) {
return;
}
doforce();
render(ctx, data, size);
forceRun();
}, 1000 / 30)
// requestAnimationFrame(forceRun);
}
forceRun();
}
GPT分析
这个力算法是用于处理图节点的布局,特别是通过计算节点之间的距离来调整它们的位置,以实现力导向布局。以下是对这个算法的分析:
算法流程
-
初始设置:
maxInterval
: 节点之间的平衡距离,超过这个距离节点会彼此靠近,低于这个距离节点会彼此排斥。maxOffset
和minOffset
: 节点位置调整的最大和最小偏移量,以避免调整过大或过小。count
: 迭代次数,即算法将运行多少次。attenuation
: 力的衰减因子,用于控制节点之间的吸引或排斥力的衰减程度。
-
核心计算 (
doforce
函数):- 对每个节点
d
,遍历所有其他节点e
。 - 计算
d
和e
之间的距离interval
。 - 基于节点之间的距离来调整节点的位置:
- 吸引力 (
interval > maxInterval
): 如果两个节点之间的距离超过了设定的平衡距离,则节点d
会朝着节点e
靠近,调整的力度与interval - maxInterval
成正比。 - 排斥力 (
interval < maxInterval
): 如果两个节点之间的距离小于平衡距离,则节点d
会远离节点e
。
- 吸引力 (
- 利用相似三角形原理计算新的节点位置
(x3, y3)
,从而确定节点应移动的方向和距离。 - 调整后的节点位置受到
maxOffset
和minOffset
的限制,确保位置的变化在合理范围内。 - 边界检查: 确保节点不会移出边界,如果超出边界,位置会被适当调整。
- 对每个节点
-
迭代执行:
- 通过
forceRun
函数在一段时间内不断执行doforce
函数,以逐步调整节点的位置,直到达到指定的count
次迭代。
- 通过
优点
- 逐步逼近: 通过多次迭代,每次小幅度调整节点的位置,有助于实现稳定的布局,避免单次调整过大导致布局失控。
- 力衰减机制: 通过
attenuation
控制力的衰减,防止节点间的力过于强烈,导致位置剧烈变动。
潜在改进
-
效率问题:
- 双重循环 (
nodes.forEach(d => { nodes.forEach(e => { ... }) }
) 的复杂度为 O(n²),对于节点数较多的情况,性能可能会成为瓶颈。可以考虑引入四叉树或空间分割等算法来优化邻近节点的计算。
- 双重循环 (
-
边界条件处理:
- 边界条件的处理方式比较简单,只是单纯地调整 10 个单位,可以考虑更智能的边界处理方法,比如反弹或更复杂的边界策略。
-
多线程或并行计算:
- 如果节点数较多,考虑将力计算放到 Web Worker 中,以免阻塞主线程,提升用户体验。
-
力算法的多样性:
- 目前算法只考虑了线性吸引和排斥力,可以引入更加复杂的物理力模型,比如库仑力或弹簧力,以模拟更加真实的物理环境。
总之,这个算法通过对节点之间的距离进行判断和调整,实现了一个基本的力导向布局。它的设计简单易懂,并且通过多次迭代逐步逼近平衡状态,但在处理大规模数据时可能需要优化其效率。
标签:interval,forceOffset,maxInterval,SolidJS,x3,forceDirectedGraph,y3,节点 From: https://www.cnblogs.com/Frey-Li/p/18345955