2

我正在尝试实现基于http://en.wikipedia.org/wiki/Force-based_algorithms_(graph_drawing )的强制基础图形布局算法

我的第一次尝试没有成功,所以我看了看

http://blog.ivank.net/force-based-graph-drawing-in-javascript.html

https://github.com/dhotson/springy

我根据我认为我从这两个方面理解的内容更改了我的实现,但我没有设法让它正确,我希望有人能提供帮助?JavaScript 不是我的强项,所以要温柔……如果您想知道为什么要编写我自己的。实际上,我没有真正的理由自己编写我只是想了解算法是如何实现的。尤其是在我的第一个链接中,该演示非常出色。

这就是我想出的

    //support function.bind - https://developer.mozilla.org/en/JavaScript/Reference/Global_Objects/Function/bind#Compatibility
if (!Function.prototype.bind) {
    Function.prototype.bind = function (oThis) {
        if (typeof this !== "function") {
            // closest thing possible to the ECMAScript 5 internal IsCallable function
            throw new TypeError("Function.prototype.bind - what is trying to be bound is not callable");
        }
        var aArgs = Array.prototype.slice.call(arguments, 1),
        fToBind = this,
        fNOP = function () {},
        fBound = function () {
            return fToBind.apply(this instanceof fNOP
                ? this
                : oThis || window,
                aArgs.concat(Array.prototype.slice.call(arguments)));
        };
        fNOP.prototype = this.prototype;
        fBound.prototype = new fNOP();
        return fBound;
    };
}
(function() {
    var lastTime = 0;
    var vendors = ['ms', 'moz', 'webkit', 'o'];
    for(var x = 0; x < vendors.length && !window.requestAnimationFrame; ++x) {
        window.requestAnimationFrame = window[vendors[x]+'RequestAnimationFrame'];
        window.cancelAnimationFrame =
        window[vendors[x]+'CancelAnimationFrame'] || window[vendors[x]+'CancelRequestAnimationFrame'];
    }
    if (!window.requestAnimationFrame)
        window.requestAnimationFrame = function(callback, element) {
            var currTime = new Date().getTime();
            var timeToCall = Math.max(0, 16 - (currTime - lastTime));
            var id = window.setTimeout(function() {
                callback(currTime + timeToCall);
            },
            timeToCall);
            lastTime = currTime + timeToCall;
            return id;
        };
    if (!window.cancelAnimationFrame)
        window.cancelAnimationFrame = function(id) {
            clearTimeout(id);
        };
}());
function Graph(o){
    this.options=o;
    this.vertices={};
    this.edges={};//form {vertexID:{edgeID:edge}}
}
/**
 *Adds an edge to the graph. If the verticies in this edge are not already in the
 *graph then they are added
 */
Graph.prototype.addEdge=function(e){
    //if vertex1 and vertex2 doesn't exist in this.vertices add them
    if(typeof(this.vertices[e.vertex1])==='undefined')
        this.vertices[e.vertex1]=new Vertex(e.vertex1);
    if(typeof(this.vertices[e.vertex2])==='undefined')
        this.vertices[e.vertex2]=new Vertex(e.vertex2);
    //add the edge
    if(typeof(this.edges[e.vertex1])==='undefined')
        this.edges[e.vertex1]={};
    this.edges[e.vertex1][e.id]=e;
}
/**
 * Add a vertex to the graph. If a vertex with the same ID already exists then
 * the existing vertex's .data property is replaced with the @param v.data
 */
Graph.prototype.addVertex=function(v){
    if(typeof(this.vertices[v.id])==='undefined')
        this.vertices[v.id]=v;
    else
        this.vertices[v.id].data=v.data;
}

function Vertex(id,data){
    this.id=id;
    this.data=data?data:{};
    //initialize to data.[x|y|z] or generate random number for each
    this.x = this.data.x?this.data.x:-100 + Math.random()*200;
    this.y = this.data.y?this.data.y:-100 + Math.random()*200;
    this.z = this.data.y?this.data.y:-100 + Math.random()*200;
    //set initial velocity to 0
    this.velocity = new Point(0, 0, 0);
    this.mass=this.data.mass?this.data.mass:Math.random();
    this.force=new Point(0,0,0);
}
function Edge(vertex1ID,vertex2ID){
    vertex1ID=vertex1ID?vertex1ID:Math.random()
    vertex2ID=vertex2ID?vertex2ID:Math.random()
    this.id=vertex1ID+"->"+vertex2ID;
    this.vertex1=vertex1ID;
    this.vertex2=vertex2ID;
}
function Point(x, y, z)
{
    this.x = x;
    this.y = y;
    this.z = z;
}
Point.prototype.plus=function(p){
    this.x +=p.x
    this.y +=p.y
    this.z +=p.z
}
function ForceLayout(o){
    this.repulsion  = o.repulsion?o.repulsion:200;
    this.attraction = o.attraction?o.attraction:0.06;
    this.damping    = o.damping?o.damping:0.9;
    this.graph          = o.graph?o.graph:new Graph();
    this.total_kinetic_energy =0;
    this.animationID=-1;
}
ForceLayout.prototype.draw=function(){
    //vertex velocities initialized to (0,0,0) when a vertex is created
    //vertex positions initialized to random position when created
  cc=0;  do{
        this.total_kinetic_energy =0;
        //for each vertex
        for(var i in this.graph.vertices){
            var thisNode=this.graph.vertices[i];
            // running sum of total force on this particular node
            var netForce=new Point(0,0,0)
            //for each other node
            for(var j in this.graph.vertices){
                if(thisNode!=this.graph.vertices[j]){
                    //net-force := net-force + Coulomb_repulsion( this_node, other_node )
                    netForce.plus(this.CoulombRepulsion( thisNode,this.graph.vertices[j]))
                }
            }
            //for each spring connected to this node
            for(var k in this.graph.edges[thisNode.id]){
                //(this node, node its connected to)
                //pass id of this node and the node its connected to so hookesattraction
                //can update the force on both vertices and return that force to be
                //added to the net force
                this.HookesAttraction(thisNode.id,
                    this.graph.edges[thisNode.id][k].vertex2
                    )
            }
            // without damping, it moves forever
            //         this_node.velocity := (this_node.velocity + timestep * net-force) * damping
            thisNode.velocity.x=(thisNode.velocity.x+thisNode.force.x)*this.damping;
            thisNode.velocity.y=(thisNode.velocity.y+thisNode.force.y)*this.damping;
            thisNode.velocity.z=(thisNode.velocity.z+thisNode.force.z)*this.damping;
            //this_node.position := this_node.position + timestep * this_node.velocity
            thisNode.x=thisNode.velocity.x;
            thisNode.y=thisNode.velocity.y;
            thisNode.z=thisNode.velocity.z;
            //normalize x,y,z???
            //total_kinetic_energy := total_kinetic_energy + this_node.mass * (this_node.velocity)^2
            this.total_kinetic_energy +=thisNode.mass*((thisNode.velocity.x+thisNode.velocity.y+thisNode.velocity.z)*
            (thisNode.velocity.x+thisNode.velocity.y+thisNode.velocity.z))
        }
        cc+=1;
    }while(this.total_kinetic_energy >0.5)
    console.log(cc,this.total_kinetic_energy,this.graph)
    this.cancelAnimation();
}
ForceLayout.prototype.HookesAttraction=function(v1ID,v2ID){
    var a=this.graph.vertices[v1ID]
    var b=this.graph.vertices[v2ID]
    var force=new Point(this.attraction*(b.x - a.x),this.attraction*(b.y - a.y),this.attraction*(b.z - a.z))
    //  hook's attraction
    a.force.x += force.x;
    a.force.y += force.y;
    a.force.z += force.z;
    b.force.x += this.attraction*(a.x - b.x);
    b.force.y += this.attraction*(a.y - b.y);
    b.force.z += this.attraction*(a.z - b.z);
    return force;
}
ForceLayout.prototype.CoulombRepulsion=function(vertex1,vertex2){
    //http://en.wikipedia.org/wiki/Coulomb's_law
    // distance squared = ((x1-x2)*(x1-x2)) + ((y1-y2)*(y1-y2)) + ((z1-z2)*(z1-z2))
    var distanceSquared =
    (
        (vertex1.x-vertex2.x)*(vertex1.x-vertex2.x)+
        (vertex1.y-vertex2.y)*(vertex1.y-vertex2.y)+
        (vertex1.z-vertex2.z)*(vertex1.z-vertex2.z)
        );
    if(distanceSquared==0) distanceSquared = 0.001;
    var coul = this.repulsion / distanceSquared;
    return new Point(coul * (vertex1.x-vertex2.x),coul * (vertex1.y-vertex2.y), coul * (vertex1.z-vertex2.z));
}
ForceLayout.prototype.animate=function(){
    if(this.animating)
        this.animationID=requestAnimationFrame(this.animate.bind(this));
    this.draw();
}
ForceLayout.prototype.cancelAnimation=function(){
    cancelAnimationFrame(this.animationID);
    this.animating=false;
}
ForceLayout.prototype.redraw=function(){
    this.animating=true;
    this.animate();
}
$(document).ready(function(){
    var g= new Graph();
    for(var i=0;i<=100;i++){
        var v1=new Vertex(Math.random(), {})
        var v2=new Vertex(Math.random(), {})
        var e1= new Edge(v1.id,v2.id);
        g.addEdge(e1);
    }
    console.log(g);
    var l=new ForceLayout({
        graph:g
    });
    l.redraw();
});
4

1 回答 1

2

这不起作用的至少一个原因是您错误地实现了弹簧。(胡克定律

也就是说,你现在有两个点之间的弹簧一直把它们拉在一起。弹簧实际上做的是它有两个参数,一个自然长度和一个弹簧常数k。如果弹簧被拉伸,它会以(length-naturalLength)*springConstant. 如果弹簧被压缩,它会以 0 的力向外推-(length-naturalLength)*springConstant

打印出所有东西的最终位置给你的调试信息很少。我强烈建议如果您仍然遇到问题,请立即编写显示代码(无论如何您都必须这样做),这样您就可以直观地看到正在发生的事情。或者,您应该只跟踪 2 个粒子的运动,它们之间有一个弹簧,在每个时间步输出调试信息。您应该将打印的内容限制为仅一个感兴趣的向量。

此外,如果您进一步遇到麻烦,您可以减少您的时间步长。

于 2012-04-06T18:03:29.993 回答