Add base code for Chapter 22 to git

marijnh · marijnh · commit 8d4444a4c50f · 2018-06-10T15:46:36.000+02:00
diff --git a/code/chapter/22_fast.js b/code/chapter/22_fast.js
@@ -0,0 +1,156 @@
+var GraphNode = class GraphNode {
+  constructor() {
+    this.pos = new Vec(Math.random() * 1000,
+                       Math.random() * 1000);
+    this.edges = [];
+  }
+  connect(other) {
+    this.edges.push(other);
+    other.edges.push(this);
+  }
+  hasEdge(other) {
+    return this.edges.includes(other);
+  }
+}
+
+function treeGraph(depth, branches) {
+  let graph = [new GraphNode()];
+  if (depth > 1) {
+    for (let i = 0; i < branches; i++) {
+      let subGraph = treeGraph(depth - 1, branches);
+      graph[0].connect(subGraph[0]);
+      graph = graph.concat(subGraph);
+    }
+  }
+  return graph;
+}
+
+var springLength = 40;
+var springStrength = 0.1;
+
+var repulsionStrength = 1500;
+
+function forceDirected_simple(graph) {
+  for (let node of graph) {
+    for (let other of graph) {
+      if (other == node) continue;
+      let apart = other.pos.minus(node.pos);
+      let distance = Math.max(1, apart.length);
+      let forceSize = -repulsionStrength / (distance * distance);
+      if (node.hasEdge(other)) {
+        forceSize += (distance - springLength) * springStrength;
+      }
+      let normalized = apart.times(1 / distance);
+      node.pos = node.pos.plus(normalized.times(forceSize));
+    }
+  }
+}
+
+function runLayout(implementation, graph) {
+  function run(steps, time) {
+    let startTime = Date.now();
+    for (let i = 0; i < 100; i++) {
+      implementation(graph);
+    }
+    time += Date.now() - startTime;
+    drawGraph(graph);
+
+    if (steps == 0) console.log(time);
+    else requestAnimationFrame(() => run(steps - 100, time));
+  }
+  run(4000, 0);
+}
+
+function forceDirected_noRepeat(graph) {
+  for (let i = 0; i < graph.length; i++) {
+    let node = graph[i];
+    for (let j = i + 1; j < graph.length; j++) {
+      let other = graph[j];
+      let apart = other.pos.minus(node.pos);
+      let distance = Math.max(1, apart.length);
+      let forceSize = -repulsionStrength / (distance * distance);
+      if (node.hasEdge(other)) {
+        forceSize += (distance - springLength) * springStrength;
+      }
+      let applied = apart.times(forceSize / distance);
+      node.pos = node.pos.plus(applied);
+      other.pos = other.pos.minus(applied);
+    }
+  }
+}
+
+var skipDistance = 175;
+
+function forceDirected_skip(graph) {
+  for (let i = 0; i < graph.length; i++) {
+    let node = graph[i];
+    for (let j = i + 1; j < graph.length; j++) {
+      let other = graph[j];
+      let apart = other.pos.minus(node.pos);
+      let distance = Math.max(1, apart.length);
+      let hasEdge = node.hasEdge(other);
+      if (!hasEdge && distance > skipDistance) continue;
+      let forceSize = -repulsionStrength / (distance * distance);
+      if (hasEdge) {
+        forceSize += (distance - springLength) * springStrength;
+      }
+      let applied = apart.times(forceSize / distance);
+      node.pos = node.pos.plus(applied);
+      other.pos = other.pos.minus(applied);
+    }
+  }
+}
+
+GraphNode.prototype.hasEdgeFast = function(other) {
+  for (let i = 0; i < this.edges.length; i++) {
+    if (this.edges[i] === other) return true;
+  }
+  return false;
+};
+
+function forceDirected_hasEdgeFast(graph) {
+  for (let i = 0; i < graph.length; i++) {
+    let node = graph[i];
+    for (let j = i + 1; j < graph.length; j++) {
+      let other = graph[j];
+      let apart = other.pos.minus(node.pos);
+      let distance = Math.max(1, apart.length);
+      let hasEdge = node.hasEdgeFast(other);
+      if (!hasEdge && distance > skipDistance) continue;
+      let forceSize = -repulsionStrength / (distance * distance);
+      if (hasEdge) {
+        forceSize += (distance - springLength) * springStrength;
+      }
+      let applied = apart.times(forceSize / distance);
+      node.pos = node.pos.plus(applied);
+      other.pos = other.pos.minus(applied);
+    }
+  }
+}
+
+function forceDirected_noVector(graph) {
+  for (let i = 0; i < graph.length; i++) {
+    let node = graph[i];
+    for (let j = i + 1; j < graph.length; j++) {
+      let other = graph[j];
+      let apartX = other.pos.x - node.pos.x;
+      let apartY = other.pos.y - node.pos.y;
+      let distance = Math.max(1, Math.sqrt(apartX * apartX + apartY * apartY));
+      let hasEdge = node.hasEdgeFast(other);
+      if (!hasEdge && distance > skipDistance) continue;
+      let forceSize = -repulsionStrength / (distance * distance);
+      if (hasEdge) {
+        forceSize += (distance - springLength) * springStrength;
+      }
+      let forceX = apartX * forceSize / distance;
+      let forceY = apartY * forceSize / distance;
+      node.pos.x += forceX; node.pos.y += forceY;
+      other.pos.x -= forceX; other.pos.y -= forceY;
+    }
+  }
+}
+
+var mangledGraph = treeGraph(4, 4);
+for (let node of mangledGraph) {
+  node[`p${Math.floor(Math.random() * 999)}`] = true;
+}
