Как сделать макет с направленным усилием без перекрытия краев узлов

Я пытаюсь улучшить алгоритм принудительной компоновки (для ориентированного графа) Базовый алгоритм работает, т.е. условие isStable в следующем коде выполняется и алгоритм завершается, но ребра и узлы могут перекрываться. Итак, я хочу добавить некоторую фиктивную вершину в середине ребер (как на следующем изображении), которая должна решить эту проблему, поскольку фиктивная вершина заставит ребро отталкивать другие ребра и узлы.

Я добавил метод addDummies, который для каждого ребра, не являющегося циклом, добавляет узел. Я назвал добавленные узлы midNodes.

Затем на каждой итерации (метод итерации) я устанавливаю положение 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.info("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--); 
},