书名：代码本色：用编程模拟自然系统
作者：Daniel Shiffman
译者：周晗彬
ISBN：978-7-115-36947-5
目录

5.19　相连的系统II：力导向图

1、力导向图

  力导向图（Force-Directed Graph），是绘图的一种算法。在二维或三维空间里配置节点，节点之间用线连接，称为连线。各连线的长度几乎相等，且尽可能不相交。节点和连线都被施加了力的作用，力是根据节点和连线的相对位置计算的。根据力的作用，来计算节点和连线的运动轨迹，并不断降低它们的能量，最终达到一种能量很低的安定状态。

  力导向图能表示节点之间的多对多的关系。

2、如何实现力导向图

  在力导向图中，我们把相互连接的元素称为节点，这些节点的位置并不是人为设置的，而是根据力的作用排布的。可以使用各种力构建力导向图的布局，弹簧力就是典型的力，因此toxiclibs适合用在此类场景。

• 首先，我们需要一个节点（Node）类，实现节点类很容易，可以让它继承自VerletParticle2D。我们已经在前面实现过这样的类，只需要将类名从Particle改为Node。

class Node extends VerletParticle2D {
    Node(Vec2D pos) {
        super(pos);
    }
  void display() {
      fill(0,150);
      stroke(0);
      ellipse(x,y,16,16);
    }
}

• 下面，我们要实现一个Cluster类，它的作用是描述节点列表。

class Cluster {
    ArrayList<Node> nodes;
    float diameter; 用这个变量表示节点之间的静止距离
    Cluster(int n, float d, Vec2D center) {
        nodes = new ArrayList<Node>();
        diameter = d;
        for (int i = 0; i < n; i++) {
          nodes.add(new Node(center.add(Vec2D.randomVector())));
          如果所有节点对象的起始位置都相同，程序就会出问题。因此我们在中心位置加上一个}
  }

• 在Cluster类中添加一个draw()函数，它的作用是绘制所有节点；然后在setup()函数中创建一个Cluster对象，在draw()中绘制Cluster。完成上述操作后，运行Sketch，你不会看到任何效果。为什么？因为我们忘了这是一个力导向图，还应该用力将粒子相连。假设有4个节点，我们打算用下面方式将它们相连。
  节点0和节点1相连
  节点0和节点2相连
  节点0和节点3相连
  节点1和节点2相连
  节点1和节点3相连
  节点2和节点3相连

在以上连接方式中，请你注意两个细节。

• 节点不会和自身相连。 我们不会将节点0和节点0相连，也不会将节点1和节点1相连。
• 不需要反过来重复连接两个节点。 换句话说，如果节点0已经和节点1相连，我们就不需要反过来让节点1和节点0相连，因为它们已经连接在一起了。

那么，如何用代码实现上面的连接？

• 让我们看看左边的节点，它们的下标分别为：000 11 2。因此，我们需要遍历列表中的每个节点，从下标0到下标N-1。

for (int i = 0; i < nodes.size()-1; i++) {
    VerletParticle2D ni = nodes.get(i);

• 现在，我们需要将节点0和节点1、节点2、节点3相连，将节点1和节点2、3相连，将节点2和节点3相连。可以总结出这样的规律：对每个节点i，我们需要从i + 1遍历到列表的末尾。

      for (int j = i+1; j < nodes.size(); j++) {　　从i + 1开始遍历
          VerletParticle2D nj = nodes.get(j);

• 对以上循环中的每两个节点，我们都需要用弹簧将它们相连。

      physics.addSpring(new VerletSpring2D(ni,nj,diameter,0.01));　　用弹簧将ni和nj连在一起　
    }
}

假设这些连接是在Cluster类的构造函数中建立的，我们可以在主程序中创建Cluster对象

3、示例

代码5-12　Cluster

import toxi.geom.*;
import toxi.physics2d.*;

// Reference to physics world
VerletPhysics2D physics;

// A list of cluster objects
Cluster cluster;

// Boolean that indicates whether we draw connections or not
boolean showPhysics = true;
boolean showParticles = true;

// Font
PFont f;

void setup() {
  size(640, 360);
  f = createFont("Georgia", 12, true);

  // Initialize the physics
  physics=new VerletPhysics2D();
  physics.setWorldBounds(new Rect(10, 10, width-20, height-20));

  // Spawn a new random graph
  cluster = new Cluster(8, 100, new Vec2D(width/2, height/2));
}

void draw() {

  // Update the physics world
  physics.update();

  background(255);

  // Display all points
  if (showParticles) {
    cluster.display();
  }

  // If we want to see the physics
  if (showPhysics) {
    cluster.showConnections();
  }

  // Instructions
  fill(0);
  textFont(f);
  text("'p' to display or hide particles\n'c' to display or hide connections\n'n' for new graph",10,20);
}

// Key press commands
void keyPressed() {
  if (key == 'c') {
    showPhysics = !showPhysics;
    if (!showPhysics) showParticles = true;
  } 
  else if (key == 'p') {
    showParticles = !showParticles;
    if (!showParticles) showPhysics = true;
  } 
  else if (key == 'n') {
    physics.clear();
    cluster = new Cluster(int(random(2, 20)), random(10, width/2), new Vec2D(width/2, height/2));
  }
}

4、运行结果