Я пытаюсь улучшить алгоритм силового ориентированного макета (для ориентированного графа). Базовый алгоритм работает, т.е. выполняется условие isStable в следующем коде, и алгоритм завершается, но ребра и узлы могут перекрываться.Поэтому я хочу добавить фиктивную вершину в середине ребер (как на следующем рисунке), которая должна решить эту проблему, так как фиктивная вершина заставит ребро отталкивать другие ребра и узлы.
Я добавил метод addDummies, который для каждого ребра, которое не является петлей, добавляет узел.Добавленные узлы я назвал midNodes.
Затем на каждой итерации (метод итерации) я устанавливаю положение midNodes в середине ребра.Остальное - старый алгоритм.
Я получаю лучшую компоновку без наложения ребер, но конечное условие никогда не выполняется, и, кроме того, рисунок не так хорош, поскольку средние узлы образуют своего рода «пончик» вокруг центрального узла, как вы можетесм. изображение ниже (средние узлы находятся внутри красного круга)
Я ищу подробное описание алгоритма, который использует фиктивные узлы наребра или любое предложение сделать алгоритм завершенным и иметь лучшие рисунки (я бы хотел, чтобы средние узлы не отталкивали другие узлы в направлении внешней области)
Должен ли я добавить новые ребра из средних узлов встарые узлы?
Решением может быть изменение условия isStable, но это число обычно гарантирует, что график правильно выстроен, поэтому я бы не хотел его трогать.
Редактировать:Я использую следующий код следующим образом:
var layouter = new Graph.Layout.Spring();
while !(layouter.isStable()) {
layouter.iterate(1);
}
Ниже приводится выдержка из текущего кода
Graph.Layout.Spring = function() {
this.maxRepulsiveForceDistance = 10;
this.maxRepulsiveForceDistanceQ = this.maxRepulsiveForceDistance * this.maxRepulsiveForceDistance;
this.k = 2.5;
this.k2 = this.k * this.k;
this.c = 0.01;
this.maxVertexMovement = 0.2;
this.damping = 0.7;
};
Graph.Layout.Spring.prototype = {
resetForUpdate : function() {
this.addDummies();
this.currentIteration = 0;
this.resetVelocities();
},
reset : function() {
this.pastIterations = 0;
this.currentIteration = 0;
this.layoutPrepare();
this.resetForUpdate();
},
isStable: function() {
var nARR= this.graph.nodeArray;
var i = nARR.length -1;
do {
var vel = nARR[i].velocity;
var vx = vel.x;
var vy = vel.y;
var v = vx*vx+vy*vy;
if (v > 0.0002) {
return false;
}
} while (i--);
return true;
},
addDummies: function() {
for (e in this.graph.edges) {
var edge = this.graph.edges[e];
var s = edge.source;
var t = edge.target;
var id = s.id+"#"+t.id;
console.log("adding ", id);
if (!this.graph.nodes[id]) {
if (s.id != t.id) {
this.graph.addNode(id, "");
var node = this.graph.nodes[id];
node.dummy = true;
node.fx = 0;
node.fy = 0;
node.next1id = s.id;
node.next2id = t.id;
node.velocity = {
x: 0,
y: 0
};
}
}
}
},
layoutPrepare : function() {
for ( var i = 0; i < this.graph.nodeArray.length; ++i) {
var node = this.graph.nodeArray[i];
var x = -1+Math.random()*2;
var y = -1+Math.random()*2;
node.layoutPosX = x;
node.layoutPosY = y;
node.fx = 0;
node.fy = 0;
node.velocity = {
x: 0,
y: 0
};
}
},
resetVelocities: function() {
for ( var i = 0; i < this.graph.nodeArray.length; ++i) {
var node = this.graph.nodeArray[i];
node.velocity = {
x: 0,
y: 0
};
}
},
iterate: function(iterations) {
var SQRT = Math.sqrt;
var RAND = Math.random;
var maxRFQ = this.maxRepulsiveForceDistanceQ;
var l_k2 = this.k2;
var it = iterations-1,
i, j, node1, node2;
var L_GRAPH = this.graph;
var L_EDGES = L_GRAPH.edges;
var nodeArray = L_GRAPH.nodeArray;
var L_NLEN = nodeArray.length;
/*
* addition: update midnodes position
*/
for (e in L_GRAPH.edges) {
var edge = L_GRAPH.edges[e];
var s = edge.source;
var t = edge.target;
if (s != t) {
var id = s.id+"#"+t.id;
var midNode = L_GRAPH.nodes[id];
if (midNode) {
var dx = s.layoutPosX - t.layoutPosX;
var dy = s.layoutPosY - t.layoutPosY;
midNode.layoutPosX = s.layoutPosX - dx/2;
midNode.layoutPosY = s.layoutPosY - dy/2;
}
}
}
/*
* repulsive
*/
do {
for (i = 0; i < L_NLEN; ++i) {
node1 = nodeArray[i];
for (j = i+1; j < L_NLEN; ++j) {
node2 = nodeArray[j];
// per cappio
if (node1 === node2)
continue;
var dx = node2.layoutPosX - node1.layoutPosX;
var dy = node2.layoutPosY - node1.layoutPosY;
var d2 = dx * dx + dy * dy;
if (d2 < 0.001) {
dx = 0.1 * RAND() + 0.1;
dy = 0.1 * RAND() + 0.1;
d2 = dx * dx + dy * dy;
}
if (d2 < maxRFQ) {
var d = SQRT(d2);
var f = 2*(l_k2 / d2);
var xx = f * dx / d;
var yy = f * dy / d;
node2.fx += xx;
node2.fy += yy;
node1.fx -= xx;
node1.fy -= yy;
}
} // for j
} // for i
/*
* Attractive
*/
i = (L_EDGES.length)-1;
if (i >= 0) {
do {
var edge = L_EDGES[i];
var node1 = edge.source;
var node2 = edge.target;
// evita self-force, che cmq andrebbe a zero
if (node1 === node2)
continue;
var dx = node2.layoutPosX - node1.layoutPosX;
var dy = node2.layoutPosY - node1.layoutPosY;
var d2 = dx * dx + dy * dy;
if (d2 < 0.01) {
dx = 0.1 * RAND() + 0.1;
dy = 0.1 * RAND() + 0.1;
d2 = dx * dx + dy * dy;
}
d = SQRT(d2);
var f = (l_k2-d2)/l_k2;
var n2d = node2.edges.length;
if (n2d > 2) {
n2d = 2;
}
var n1d = node1.edges.length;
if (n1d > 2) {
n1d = 2;
}
var xcomp = f * dx/d;
var ycomp = f * dy/d;
node2.fx += xcomp / n2d;
node2.fy += ycomp / n2d;
node1.fx -= xcomp / n1d;
node1.fy -= ycomp / n1d;
} while (i--);
} // if i>=0
/*
* Move by the given force
*/
var max = this.maxVertexMovement;
var d = this.damping;
var c = this.c;
var i = L_NLEN-1;
do {
var node = nodeArray[i];
var xmove,
ymove;
var v = node.velocity;
v.x = v.x * d + node.fx * c;
v.y = v.y * d + node.fy * c;
xmove = v.x;
ymove = v.y;
if (xmove > max)
xmove = max;
else if (xmove < -max)
xmove = -max;
if (ymove > max)
ymove = max;
else if (ymove < -max)
ymove = -max;
if (node.isNailed !== undefined) {
v.x = 0;
v.y = 0;
} else {
v.x = xmove;
v.y = ymove;
node.layoutPosX += xmove;
node.layoutPosY += ymove;
}
node.fx = 0;
node.fy = 0;
} while (i--);
} while (it--);
},