javascript - 可视化节点树(斥力？)

Question

我需要可视化我正在处理的项目的节点树...数据结构如下所示:

构造函数:

function Tree(x,y,node){
    this.root = node;
    this.x = x;
    this.y = y;
}

function Node(key,parent,data){
    this.children = new Array();
    this.key = key;
    this.parent = parent;
    this.data = data;
    this.direction = ???;
}

每个children数组可以容纳更多的节点，这样我就得到了一个Tree结构...x和y Tree 的值用于获取应绘制树根的位置，而 direction Node的属性(property)存储 Angular ，其中Node应根据 parent 绘制 Angular ....

现在我的问题是:我需要一个函数 draw(context)对于Tree.prototype可以画出Tree使用给定的 Canvas 上下文。

这里是一个例子，说明这样的 Tree 是如何实现的应该看起来像:

我实际上知道这样的算法如何工作，但我无法将其转换为代码......这里是:

每个节点都会推开其他节点。力取决于节点之间的距离及其级别(根节点为级别 0，它的子节点为级别 1，依此类推...)。

我想，经过几次迭代后，将会创建一棵漂亮的树......

非常感谢您，如果您尝试帮助我，甚至尝试创建这样的算法......

编辑:

这是我迄今为止尝试过的:

Tree.prototype.repulsion = function(){
    if(this.root){
        this.root.repulsion();
    }
};
Node.prototype.repulsion = function(){
    var force = {
        x: 0,
        y: 0
    };
    var pos = {
        x: this.x,
        y: this.y
    };
    var oldDirection = this.direction;
    for(var i=0;i<nodes.length;i++){
        var node = nodes[i];
        if(node!=this){
            var distance = Math.sqrt(Math.pow(pos.x-node.x,2)+Math.pow(pos.y-node.y,2));
            var direction = Math.atan((this.y-node.y)/(this.x-node.x));
            var magnitude = 1/Math.pow(distance,2);
            if(pos.x<node.x){
                direction *= -1;
                force.x -= Math.cos(direction)*magnitude;
            }else{
                force.x += Math.cos(direction)*magnitude;
            }
            force.y += Math.sin(direction)*magnitude;
        }
    }
    force.x *= repulsionFactor;
    force.y *= repulsionFactor;
    var newPos = {
        x: pos.x+force.x,
        y: pos.y+force.y
    };
    var newDirection = Math.atan((newPos.y-this.parent.y)/(newPos.x-this.parent.x));
    if(force.x<0){
        newDirection += Math.PI;
    }
    this.direction = newDirection;
    this.direction %= 2*Math.PI;
    for(var i=0;i<this.children.length;i++){
        this.children[i].repulsion();
    }
};

Answer 1

我实际上有了自己的想法!

var tree, width, height, clock, lastCalledTime, root, node, 
	repulsionFactor = 10000,
	nodes = new Array();

function setup(){
	tree = new Tree(200,200);
	tree.repulsionFactor = 10000;
	for(var i=0;i<5;i++){
		tree.addRandomChild();
	}
	for(var i=0;i<10;i++){
		tree.addRandomChild(1);
	}
	for(var i=0;i<15;i++){
		tree.addRandomChild(2);
	}
	root = tree.root;
	node = root.children[0];
	var canvas = document.getElementById('canvas');
	width = 400;
	height = 400;
	canvas.width = width;
	canvas.height = height;
	canvasSize = {x:window.innerWidth-5,y:window.innerHeight-5};
	ctx = canvas.getContext('2d');
	clock = requestAnimationFrame(main);
	//clock = setInterval(main,200);
}

function main(){
	if(!lastCalledTime) {
		lastCalledTime = Date.now();
	}
	ctx.clearRect(0,0,width,height);
	tree.repulsion();
	tree.draw();
	var delta = (Date.now() - lastCalledTime)/1000;
	lastCalledTime = Date.now();
	var fps = 1/delta;
    tree.repulsionFactor*=0.99;
	clock = requestAnimationFrame(main);
}

function Tree(x,y){
	this.x = x;
	this.y = y;
	this.nodeColor = "gray";
	this.lineColor = "black";
	this.size = 20;
	this.lineWidth = 3;
	this.linkLength = 100;
	this.nodes = new Array();
	this.repulsionFactor = 10000;
	this.root = new Node(this,this,"root");
}

Tree.prototype.addRandomChild = function(level=0){
	var node = this.root;
	for(var i=0;i<level;i++){
		if(node.children.length>0){
			var randIndex = Math.floor(node.children.length*Math.random());
			node = node.children[randIndex];
		}else{
			return false;
		}
	}
	node.addChild();
};

Tree.prototype.draw = function(){
	this.root.draw();
}

Tree.prototype.repulsion = function(){
	this.root.repulsion();
};

Tree.prototype.level = -1;
Tree.prototype.direction = 0;

function Node(parent,tree,key,data,direction){
	this.children = new Array();
	this.parent = parent;
	this.tree = tree;
	this.key = key;
	this.data = data;
	if(direction){
		this.direction = direction;
	}else{
		this.direction = this.parent.direction+Math.random()/10;
	}
	this.tree.nodes.push(this);
}

Node.prototype.addChild = function(key,data){
	this.children.push(new Node(this,this.tree,key,data));
};

Node.prototype.draw = function(){
	ctx.fillStyle = this.nodeColor;
	ctx.strokeStyle = this.lineColor;
	ctx.lineWidth = this.lineWidth;
	if(this.key!="root"){
		ctx.beginPath();
		ctx.moveTo(this.x,this.y);
		ctx.lineTo(this.parent.x,this.parent.y);
		ctx.stroke();
	}
	for(var i=0;i<this.children.length;i++){
		this.children[i].draw();
	}
	ctx.beginPath();
	ctx.arc(this.x,this.y,this.size,0,2*Math.PI,false);
	ctx.fill();
	ctx.stroke();
}

Node.prototype.repulsion = function(){
	if(this.key!="root"){
		var force = {
			x: 0,
			y: 0
		};
		var pos = {
			x: this.x,
			y: this.y
		};
		var nodes = this.tree.nodes;
		for(var i=0;i<nodes.length;i++){
			var node = nodes[i];
			if(node!=this){
				var distance = Math.sqrt(Math.pow(pos.x-node.x,2)+Math.pow(pos.y-node.y,2));
				var direction = Math.atan2((pos.y-node.y),(pos.x-node.x));
				var magnitude = 1/Math.pow(distance,2)/(node.level+1);
				force.x += Math.cos(direction)*magnitude;
				force.y += Math.sin(direction)*magnitude;
			}
		}
		force.x *= this.tree.repulsionFactor;
		force.y *= this.tree.repulsionFactor;
		var newPos = {
			x: pos.x+force.x,
			y: pos.y+force.y
		};
		var newDirection = Math.atan2((newPos.y-this.parent.y),(newPos.x-this.parent.x));
		this.direction = newDirection;
	}else{
		this.direction = this.parent.direction;
	}
	for(var i=0;i<this.children.length;i++){
		this.children[i].repulsion();
	}
};



Object.defineProperty(Node.prototype,"x",{
	get: function x(){
		if(this.key=="root"){
			return this.parent.x;
		}
		return Math.cos(this.direction)*this.linkLength+this.parent.x;
	}
});

Object.defineProperty(Node.prototype,"y",{
	get: function y(){
		if(this.key=="root"){
			return this.parent.y;
		}
		return Math.sin(this.direction)*this.linkLength+this.parent.y;
	}
});

Object.defineProperty(Node.prototype,"level",{
	get: function level(){
		return this.parent.level+1;
	}
});

Object.defineProperty(Node.prototype,"nodeColor",{
	get: function nodeColor(){
		return this.parent.nodeColor;
	}
});

Object.defineProperty(Node.prototype,"lineColor",{
	get: function lineColor(){
		return this.parent.lineColor;
	}
});

Object.defineProperty(Node.prototype,"lineWidth",{
	get: function lineWidth(){
		return this.parent.lineWidth;
	}
});

Object.defineProperty(Node.prototype,"size",{
	get: function size(){
		return this.parent.size*0.8;
	}
});

Object.defineProperty(Node.prototype,"linkLength",{
	get: function linkLength(){
		return this.parent.linkLength*0.8;
	}
});

<!DOCTYPE html>
<html>
	<head>
		<meta charset="utf-8">
		<title>Node Tree</title>
	</head>
	<body onload="setup()">
		<canvas id="canvas"></canvas>
	</body>
</html>

出于某种原因，树有时会不断旋转，而且并不是每次我创建树时它都会展开......但希望您可以对此进行扩展!