我正在尝试基于 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();
});
最佳答案
这不起作用的至少一个原因是您未正确实现 Spring 。 ( Hooke's law )
也就是说，你现在有两点之间的 Spring 一直把它们拉在一起。 Spring 实际上做的是它有两个参数，一个自然长度和一个 Spring 常数 k。如果 Spring 被拉伸(stretch)，它将以 (length-naturalLength)*springConstant 的力向内拉。如果 Spring 被压缩，它将以 -(length-naturalLength)*springConstant 的力向外推。
打印出所有内容的最终位置给你的调试信息很少。我强烈建议，如果您仍然遇到问题，现在就编写您的显示代码(无论如何您都必须这样做)，这样您就可以想象发生了什么。或者，您应该只跟踪 2 个粒子的运动，它们之间有一个 Spring ，在每个时间步输出调试信息。您应该将打印出的内容限制为仅一个感兴趣的矢量。
此外，如果您进一步遇到麻烦，您可以减少时间步长。
关于javascript - 理解和实现基于力的图形布局算法，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/10037974/