如果有超过 10-20 个节点，Javascript HTML canvas 标签会强制定向图崩溃，否则会起作用

Question

我使用 javascript 和 html canvas 使用胡克斯定律和哥伦布定律原理开发了一个强制有向图。我面临的问题是，如果节点超过 10-20 个，它就会崩溃!否则工作正常..有人可以帮忙吗？

var myCanvas = document.getElementById('myCanvas');
    var ctx = myCanvas.getContext('2d');

    myCanvas.width = window.innerWidth;
    myCanvas.height = window.innerHeight;

    ctx.fillStyle = '#006FB9';
    ctx.strokeStyle = '#006FB9';

    var time = 0;  //track total consumed time

    function Graph(){               
        this.width = window.innerWidth;
        this.height = window.innerHeight;

        this.vertices = {};
        this.forcex = {};
        this.forcey = {};
        this.stepSize = 0.0005;
        this.iteration = 0;
        this.task = null;

        this.repulsion = 200000;
        this.spring_length = 20;
    }           

    Graph.prototype.createVertex = function(name){
        var vertex = {};

        vertex.posx = Math.random() * (this.width * 0.8) + (this.width * 0.1);
        vertex.posy = Math.random() * (this.height * 0.8) + (this.height * 0.1);                
        vertex.edges = new Array();

        this.vertices[name] = vertex;               
    };

    Graph.prototype.createEdge = function(a,b){ 
        this.vertices[a].edges[b] = {'dest' : b};
        this.vertices[b].edges[a] = {'dest' : a};               
    };

    Graph.prototype.updateLayout = function(){
        for(i in g.vertices){                   
            g.forcex[i] = 0;
            g.forcey[i] = 0;
            for(j in g.vertices){                       
                if(i !== j){
                    var deltax = g.vertices[j].posx - g.vertices[i].posx;
                    var deltay = g.vertices[j].posy - g.vertices[i].posy;
                    var d2 = deltax * deltax + deltay * deltay;

                    //add jitter if d^2 is very small
                    if(d2 < 0.01){
                        deltax = 0.1 * Math.random() + 0.1;
                        deltay = 0.1 * Math.random() + 0.1;
                        d2 = deltax * deltax + deltay * deltay;                         
                    }                           

                    //columb's
                    g.forcex[i] -= (g.repulsion / d2) * deltax;
                    g.forcey[i] -= (g.repulsion / d2) * deltay;

                    //hooke's
                    if(g.vertices[i].edges[j]){
                        var distance = Math.sqrt(d2);
                        this.forcex[i] += (distance - g.spring_length) * deltax;
                        this.forcey[i] += (distance - g.spring_length) * deltay;
                    }
                }   
            }                   
        }

        for(i in g.vertices){
            //vertices
            g.vertices[i].posx += g.forcex[i] * g.stepSize;
            g.vertices[i].posy += g.forcey[i] * g.stepSize;
        }

        Graph.iteration++;              
        if(Graph.iteration > 300){
            g.quit();                   
        }       
    };

    Graph.prototype.quit = function(){
        //draw vertices
        for(i in g.vertices){

            ctx.beginPath();
            ctx.arc(g.vertices[i].posx, g.vertices[i].posy, 5, 0, Math.PI * 2);
            ctx.fill(); 
            //draw edges 
            for (j in g.vertices[i].edges){
                ctx.moveTo(g.vertices[i].posx, g.vertices[i].posy);
                    ctx.lineTo(g.vertices[g.vertices[i].edges[j].dest].posx, g.vertices[g.vertices[i].edges[j].dest].posy);
                    ctx.stroke();
            }                                       
        }       

        window.clearInterval(Graph.task);
        Graph.task = null;

        console.log('Start Time : ' + time + ' / End Time : ' + Date.now());
        };

        Graph.prototype.go = function(){
            if(this.task){
                return;
            }

            time = Date.now();  

            Graph.iteration = 0;                
            Graph.task = window.setInterval(function(){g.updateLayout();},1);
        }

        var g = new Graph();

        //invoke
        (function(){
            for (var i = 0; i < 10; i++){
                g.createVertex(i);

                if (i > 0){
                    g.createEdge('0',i);
                }
            }               
            g.go();
        })();

Answer 1

您已经构建了具有二次运行时间的算法。当您需要 x 微秒来处理一个节点时，则需要 x * n² 微秒来处理 n 个节点。这意味着处理时间随着要添加的节点数量而迅速增加。

但是，您可以使用 window.setInterval 强制模拟每 1ms 模拟一帧。使用 setInterval 来安排可能的处理密集型任务是一个坏主意，特别是当您的间隔长度非常短时。当您在一毫秒内处理的节点太多时，这根本无法工作，因为您请求浏览器处理模拟的速度比其物理能力更快。

要允许您的应用程序以每秒更少的帧数为代价处理更多数量的节点，您可以使用 window.requestAnimationFrame(function) .

将 setInterval 调用替换为

window.requestAnimationFrame(g.updateLayout);

并在g.updateLayout末尾放置同一行，以便在浏览器完成绘制最后一帧后立即请求下一帧。