可视化节点树（排斥？）

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结构...Tree的x和y值用来得到应该绘制树根的位置，而 Node 的 direction 属性存储角度，Node 应该根据 parent角度....

现在我的问题是：我需要一个 Tree.prototype 的函数 draw(context)，它可以使用给定的 canvas 上下文绘制 Tree。

下面是这样一个 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

有什么link这个？

我使用后代的数量将节点推离它们各自的根。这与基于级别的一些角度修改相结合，使得获得重叠音符的可能性很小，但并非不可能。

var Branch = (function() {
  function Branch(parent, key, data) {
    if (parent === void 0) {
      parent = null;
    }
    if (key === void 0) {
      key = "test";
    }
    if (data === void 0) {
      data = "null";
    }
    this.parent = parent;
    this.key = key;
    this.data = data;
    this.children = [];
    this.pos = {
      x: 0,
      y: 0
    };
    if (this.parent != null) {
      this.parent.children.push(this);
    }
  }
  Branch.prototype.level = function() {
    if (this.parent != null) {
      return this.parent.level() + 1;
    }
    return 0;
  };
  Branch.prototype.descendants = function() {
    var count = 0;

    function descent(target) {
      count += target.children.length;
      for (var i = 0; i < target.children.length; i++) {
        descent(target.children[i]);
      }
    }
    descent(this);
    return count;
  };
  return Branch;
}());
var Tree = (function() {
  function Tree(pos, node) {
    this.pos = pos;
    this.node = node;
    this.node.pos = this.pos;
  }
  Tree.prototype.render = function(canvas, padding, nodeSize, longpath, showText) {
    if (padding === void 0) {
      padding = 100;
    }
    if (nodeSize === void 0) {
      nodeSize = 10;
    }
    if (longpath === void 0) {
      longpath = 4;
    }
    if (showText === void 0) {
      showText = true;
    }
    var ctx = canvas.getContext("2d");
    //flatten
    var flattened = [];

    function getLevel(branch) {
      flattened.push(branch);
      for (var index = 0; index < branch.children.length; index++) {
        getLevel(branch.children[index]);
      }
    }
    getLevel(this.node);
    //disperse
    function disperseLevel(branch) {
      if (branch.parent != null) {
        branch.pos.x = branch.parent.pos.x;
        branch.pos.y = branch.parent.pos.y;
        var angle = (((360 / (branch.parent.children.length + branch.level())) * branch.parent.children.indexOf(branch)) + (branch.level() * 10)) * Math.PI / 180;
        branch.pos.x += Math.cos(angle) * (padding * (branch.descendants() / longpath + 1));
        branch.pos.y += Math.sin(angle) * (padding * (branch.descendants() / longpath + 1));
      }
      for (var index = 0; index < branch.children.length; index++) {
        disperseLevel(branch.children[index]);
      }
    }
    disperseLevel(this.node);
    //draw
    for (var index = 0; index < flattened.length; index++) {
      var branch = flattened[index];
      ctx.fillStyle = "rgba(" + (255 - ((branch.level()) * 48) % 255).toString() + ',0,0,1)';
      ctx.strokeStyle = "rgba(" + (255 - ((branch.level()) * 48) % 255).toString() + ',0,0,1)';
      ctx.fillRect(branch.pos.x - (0.5 * nodeSize), branch.pos.y - (0.5 * nodeSize), nodeSize, nodeSize);
      if (branch.parent != null) {
        ctx.beginPath();
        ctx.moveTo(branch.pos.x, branch.pos.y);
        ctx.lineTo(branch.parent.pos.x, branch.parent.pos.y);
        ctx.closePath();
        ctx.stroke();
      }
      if (showText === true) {
        ctx.strokeText(branch.key + ': ' + branch.data, branch.pos.x, branch.pos.y);
      }
    }
  };
  return Tree;
}());
//TEST
//setup canvas
var c = document.body.appendChild(document.createElement("canvas"));
var ctx = c.getContext("2d");
c.width = 3000;
c.height = 3000;
ctx.textAlign = "center";
ctx.font = "14px Arial";
//create nodes
var key = 1;
var nodes = [
  new Branch(null, (key++).toString(), "ROOT")
];
//create tree
var tree = new Tree({
  x: 1000,
  y: 1000
}, nodes[0]);
//render tree using canvas
setInterval(function() {
  if (nodes.length > 50) {
    return true;
  }
  ctx.clearRect(0, 0, c.width, c.height);
  nodes.push(new Branch(nodes[Math.floor(Math.random() * (nodes.length - 1))], (key++).toString()));
  tree.render(c, 100, 10, 4, true);
}, 100);

Answer 2

我真的有自己的想法了！

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>

出于某种原因，这棵树有时会一直旋转，而且并不是每次我创建一棵树时它都会展开...但希望您能对此进行扩展！

可视化节点树（排斥？）

Visualizing a Node Tree (Repulsion?)

javascript

tree

visualization

data-structures