Socket
Socket
Sign inDemoInstall

ngraph.quadtreebh

Package Overview
Dependencies
1
Maintainers
1
Versions
5
Alerts
File Explorer

Advanced tools

npm Scripts

Install Socket

Detect and block malicious and high-risk dependencies

Install

Comparing version 0.0.1 to 0.0.2

perf/updateBodyForce.js
test/huge.js

507

index.js
/**
* This is Barnes Hut simulation algorithm. Implementation
* is adopted to non-recursive solution, since certain browsers
* handle recursion extremly bad.
* This is Barnes Hut simulation algorithm for 2d case. Implementation
* is highly optimized (avoids recusion and gc pressure)
*

@@ -9,265 +8,305 @@ * http://www.cs.princeton.edu/courses/archive/fall03/cs126/assignments/barnes-hut.html

module.exports = function (options) {
options = options || {};
options.gravity = typeof options.gravity === 'number' ? options.gravity : -1;
options.theta = typeof options.theta === 'number' ? options.theta : 0.8;
module.exports = function(options) {
options = options || {};
options.gravity = typeof options.gravity === 'number' ? options.gravity : -1;
options.theta = typeof options.theta === 'number' ? options.theta : 0.8;
// we require deterministic randomness here
var random = require('ngraph.random').random(1984),
Node = require('./node'),
InsertStack = require('./insertStack'),
isSamePosition = require('./isSamePosition');
// we require deterministic randomness here
var random = require('ngraph.random').random(1984),
Node = require('./node'),
InsertStack = require('./insertStack'),
isSamePosition = require('./isSamePosition');
var gravity = options.gravity,
updateQueue = [],
insertStack = new InsertStack(),
theta = options.theta,
var gravity = options.gravity,
updateQueue = [],
insertStack = new InsertStack(),
theta = options.theta,
nodesCache = [],
currentInCache = 0,
newNode = function () {
// To avoid pressure on GC we reuse nodes.
var node = nodesCache[currentInCache];
if (node) {
node.quads[0] = null;
node.quads[1] = null;
node.quads[2] = null;
node.quads[3] = null;
node.body = null;
node.mass = node.massX = node.massY = 0;
node.left = node.right = node.top = node.bottom = 0;
} else {
node = new Node();
nodesCache[currentInCache] = node;
}
nodesCache = [],
currentInCache = 0,
newNode = function() {
// To avoid pressure on GC we reuse nodes.
var node = nodesCache[currentInCache];
if (node) {
node.quads[0] = null;
node.quads[1] = null;
node.quads[2] = null;
node.quads[3] = null;
node.body = null;
node.mass = node.massX = node.massY = 0;
node.left = node.right = node.top = node.bottom = 0;
} else {
node = new Node();
nodesCache[currentInCache] = node;
}
++currentInCache;
return node;
},
++currentInCache;
return node;
},
root = newNode(),
root = newNode(),
// Inserts body to the tree
insert = function (newBody) {
insertStack.reset();
insertStack.push(root, newBody);
// Inserts body to the tree
insert = function(newBody) {
insertStack.reset();
insertStack.push(root, newBody);
while (!insertStack.isEmpty()) {
var stackItem = insertStack.pop(),
node = stackItem.node,
body = stackItem.body;
while (!insertStack.isEmpty()) {
var stackItem = insertStack.pop(),
node = stackItem.node,
body = stackItem.body;
if (!node.body) {
// This is internal node. Update the total mass of the node and center-of-mass.
var x = body.pos.x;
var y = body.pos.y;
node.mass = node.mass + body.mass;
node.massX = node.massX + body.mass * x;
node.massY = node.massY + body.mass * y;
if (!node.body) {
// This is internal node. Update the total mass of the node and center-of-mass.
var x = body.pos.x;
var y = body.pos.y;
node.mass = node.mass + body.mass;
node.massX = node.massX + body.mass * x;
node.massY = node.massY + body.mass * y;
// Recursively insert the body in the appropriate quadrant.
// But first find the appropriate quadrant.
var quadIdx = 0, // Assume we are in the 0's quad.
left = node.left,
right = (node.right + left) / 2,
top = node.top,
bottom = (node.bottom + top) / 2;
// Recursively insert the body in the appropriate quadrant.
// But first find the appropriate quadrant.
var quadIdx = 0, // Assume we are in the 0's quad.
left = node.left,
right = (node.right + left) / 2,
top = node.top,
bottom = (node.bottom + top) / 2;
if (x > right) { // somewhere in the eastern part.
quadIdx = quadIdx + 1;
var oldLeft = left;
left = right;
right = right + (right - oldLeft);
}
if (y > bottom) { // and in south.
quadIdx = quadIdx + 2;
var oldTop = top;
top = bottom;
bottom = bottom + (bottom - oldTop);
}
if (x > right) { // somewhere in the eastern part.
quadIdx = quadIdx + 1;
var oldLeft = left;
left = right;
right = right + (right - oldLeft);
}
if (y > bottom) { // and in south.
quadIdx = quadIdx + 2;
var oldTop = top;
top = bottom;
bottom = bottom + (bottom - oldTop);
}
var child = node.quads[quadIdx];
if (!child) {
// The node is internal but this quadrant is not taken. Add
// subnode to it.
child = newNode();
child.left = left;
child.top = top;
child.right = right;
child.bottom = bottom;
child.body = body;
var child = node.quads[quadIdx];
if (!child) {
// The node is internal but this quadrant is not taken. Add
// subnode to it.
child = newNode();
child.left = left;
child.top = top;
child.right = right;
child.bottom = bottom;
child.body = body;
node.quads[quadIdx] = child;
} else {
// continue searching in this quadrant.
insertStack.push(child, body);
}
} else {
// We are trying to add to the leaf node.
// We have to convert current leaf into internal node
// and continue adding two nodes.
var oldBody = node.body;
node.body = null; // internal nodes do not cary bodies
node.quads[quadIdx] = child;
} else {
// continue searching in this quadrant.
insertStack.push(child, body);
}
} else {
// We are trying to add to the leaf node.
// We have to convert current leaf into internal node
// and continue adding two nodes.
var oldBody = node.body;
node.body = null; // internal nodes do not cary bodies
if (isSamePosition(oldBody.pos, body.pos)) {
// Prevent infinite subdivision by bumping one node
// anywhere in this quadrant
if (node.right - node.left < 1e-8) {
// This is very bad, we ran out of precision.
// if we do not return from the method we'll get into
// infinite loop here. So we sacrifice correctness of layout, and keep the app running
// Next layout iteration should get larger bounding box in the first step and fix this
return;
}
do {
var offset = random.nextDouble();
var dx = (node.right - node.left) * offset;
var dy = (node.bottom - node.top) * offset;
if (isSamePosition(oldBody.pos, body.pos)) {
// Prevent infinite subdivision by bumping one node
// anywhere in this quadrant
var retriesCount = 3;
do {
var offset = random.nextDouble();
var dx = (node.right - node.left) * offset;
var dy = (node.bottom - node.top) * offset;
oldBody.pos.x = node.left + dx;
oldBody.pos.y = node.top + dy;
// Make sure we don't bump it out of the box. If we do, next iteration should fix it
} while (isSamePosition(oldBody.pos, body.pos));
oldBody.pos.x = node.left + dx;
oldBody.pos.y = node.top + dy;
retriesCount -= 1;
// Make sure we don't bump it out of the box. If we do, next iteration should fix it
} while (retriesCount > 0 && isSamePosition(oldBody.pos, body.pos));
}
// Next iteration should subdivide node further.
insertStack.push(node, oldBody);
insertStack.push(node, body);
}
}
},
if (retriesCount === 0 && isSamePosition(oldBody.pos, body.pos)) {
// This is very bad, we ran out of precision.
// if we do not return from the method we'll get into
// infinite loop here. So we sacrifice correctness of layout, and keep the app running
// Next layout iteration should get larger bounding box in the first step and fix this
return;
}
}
// Next iteration should subdivide node further.
insertStack.push(node, oldBody);
insertStack.push(node, body);
}
}
},
update = function (sourceBody) {
var queue = updateQueue,
v,
dx,
dy,
r,
queueLength = 1,
shiftIdx = 0,
pushIdx = 1;
update = function(sourceBody) {
var queue = updateQueue,
v,
dx,
dy,
r, fx = 0,
fy = 0,
queueLength = 1,
shiftIdx = 0,
pushIdx = 1;
queue[0] = root;
queue[0] = root;
while (queueLength) {
var node = queue[shiftIdx],
body = node.body;
while (queueLength) {
var node = queue[shiftIdx],
body = node.body;
queueLength -= 1;
shiftIdx += 1;
// technically there should be external "if (body !== sourceBody) {"
// but in practice it gives slightghly worse performance, and does not
// have impact on layout correctness
if (body && body !== sourceBody) {
// If the current node is a leaf node (and it is not source body),
// calculate the force exerted by the current node on body, and add this
// amount to body's net force.
dx = body.pos.x - sourceBody.pos.x;
dy = body.pos.y - sourceBody.pos.y;
r = Math.sqrt(dx * dx + dy * dy);
queueLength -= 1;
shiftIdx += 1;
// technically there should be external "if (body !== sourceBody) {"
// but in practice it gives slightghly worse performance, and does not
// have impact on layout correctness
if (body && body !== sourceBody) {
// If the current node is a leaf node (and it is not source body),
// calculate the force exerted by the current node on body, and add this
// amount to body's net force.
dx = body.pos.x - sourceBody.pos.x;
dy = body.pos.y - sourceBody.pos.y;
r = Math.sqrt(dx * dx + dy * dy);
if (r === 0) {
// Poor man's protection against zero distance.
dx = (random.nextDouble() - 0.5) / 50;
dy = (random.nextDouble() - 0.5) / 50;
r = Math.sqrt(dx * dx + dy * dy);
}
if (r === 0) {
// Poor man's protection against zero distance.
dx = (random.nextDouble() - 0.5) / 50;
dy = (random.nextDouble() - 0.5) / 50;
r = Math.sqrt(dx * dx + dy * dy);
}
// This is standard gravition force calculation but we divide
// by r^3 to save two operations when normalizing force vector.
v = gravity * body.mass * sourceBody.mass / (r * r * r);
sourceBody.force.x += v * dx;
sourceBody.force.y += v * dy;
} else {
// Otherwise, calculate the ratio s / r, where s is the width of the region
// represented by the internal node, and r is the distance between the body
// and the node's center-of-mass
dx = node.massX / node.mass - sourceBody.pos.x;
dy = node.massY / node.mass - sourceBody.pos.y;
r = Math.sqrt(dx * dx + dy * dy);
// This is standard gravition force calculation but we divide
// by r^3 to save two operations when normalizing force vector.
v = gravity * body.mass * sourceBody.mass / (r * r * r);
fx += v * dx;
fy += v * dy;
} else {
// Otherwise, calculate the ratio s / r, where s is the width of the region
// represented by the internal node, and r is the distance between the body
// and the node's center-of-mass
dx = node.massX / node.mass - sourceBody.pos.x;
dy = node.massY / node.mass - sourceBody.pos.y;
r = Math.sqrt(dx * dx + dy * dy);
if (r === 0) {
// Sorry about code duplucation. I don't want to create many functions
// right away. Just want to see performance first.
dx = (random.nextDouble() - 0.5) / 50;
dy = (random.nextDouble() - 0.5) / 50;
r = Math.sqrt(dx * dx + dy * dy);
}
// If s / r < θ, treat this internal node as a single body, and calculate the
// force it exerts on body b, and add this amount to b's net force.
if ((node.right - node.left) / r < theta) {
// in the if statement above we consider node's width only
// because the region was squarified during tree creation.
// Thus there is no difference between using width or height.
v = gravity * node.mass * sourceBody.mass / (r * r * r);
sourceBody.force.x += v * dx;
sourceBody.force.y += v * dy;
} else {
// Otherwise, run the procedure recursively on each of the current node's children.
if (r === 0) {
// Sorry about code duplucation. I don't want to create many functions
// right away. Just want to see performance first.
dx = (random.nextDouble() - 0.5) / 50;
dy = (random.nextDouble() - 0.5) / 50;
r = Math.sqrt(dx * dx + dy * dy);
}
// If s / r < θ, treat this internal node as a single body, and calculate the
// force it exerts on sourceBody, and add this amount to sourceBody's net force.
if ((node.right - node.left) / r < theta) {
// in the if statement above we consider node's width only
// because the region was squarified during tree creation.
// Thus there is no difference between using width or height.
v = gravity * node.mass * sourceBody.mass / (r * r * r);
fx += v * dx;
fy += v * dy;
} else {
// Otherwise, run the procedure recursively on each of the current node's children.
// I intentionally unfolded this loop, to save several CPU cycles.
if (node.quads[0]) { queue[pushIdx] = node.quads[0]; queueLength += 1; pushIdx += 1; }
if (node.quads[1]) { queue[pushIdx] = node.quads[1]; queueLength += 1; pushIdx += 1; }
if (node.quads[2]) { queue[pushIdx] = node.quads[2]; queueLength += 1; pushIdx += 1; }
if (node.quads[3]) { queue[pushIdx] = node.quads[3]; queueLength += 1; pushIdx += 1; }
}
}
// I intentionally unfolded this loop, to save several CPU cycles.
if (node.quads[0]) {
queue[pushIdx] = node.quads[0];
queueLength += 1;
pushIdx += 1;
}
},
if (node.quads[1]) {
queue[pushIdx] = node.quads[1];
queueLength += 1;
pushIdx += 1;
}
if (node.quads[2]) {
queue[pushIdx] = node.quads[2];
queueLength += 1;
pushIdx += 1;
}
if (node.quads[3]) {
queue[pushIdx] = node.quads[3];
queueLength += 1;
pushIdx += 1;
}
}
}
}
insertBodies = function (bodies) {
var x1 = Number.MAX_VALUE,
y1 = Number.MAX_VALUE,
x2 = Number.MIN_VALUE,
y2 = Number.MIN_VALUE,
i,
max = bodies.length;
sourceBody.force.x += fx;
sourceBody.force.y += fy;
},
// To reduce quad tree depth we are looking for exact bounding box of all particles.
i = max;
while (i--) {
var x = bodies[i].pos.x;
var y = bodies[i].pos.y;
if (x < x1) { x1 = x; }
if (x > x2) { x2 = x; }
if (y < y1) { y1 = y; }
if (y > y2) { y2 = y; }
}
insertBodies = function(bodies) {
var x1 = Number.MAX_VALUE,
y1 = Number.MAX_VALUE,
x2 = Number.MIN_VALUE,
y2 = Number.MIN_VALUE,
i,
max = bodies.length;
// Squarify the bounds.
var dx = x2 - x1,
dy = y2 - y1;
if (dx > dy) { y2 = y1 + dx; } else { x2 = x1 + dy; }
// To reduce quad tree depth we are looking for exact bounding box of all particles.
i = max;
while (i--) {
var x = bodies[i].pos.x;
var y = bodies[i].pos.y;
if (x < x1) {
x1 = x;
}
if (x > x2) {
x2 = x;
}
if (y < y1) {
y1 = y;
}
if (y > y2) {
y2 = y;
}
}
currentInCache = 0;
root = newNode();
root.left = x1;
root.right = x2;
root.top = y1;
root.bottom = y2;
// Squarify the bounds.
var dx = x2 - x1,
dy = y2 - y1;
if (dx > dy) {
y2 = y1 + dx;
} else {
x2 = x1 + dy;
}
i = max - 1;
if (i > 0) {
root.body = bodies[i];
}
while (i--) {
insert(bodies[i], root);
}
};
currentInCache = 0;
root = newNode();
root.left = x1;
root.right = x2;
root.top = y1;
root.bottom = y2;
return {
insertBodies : insertBodies,
updateBodyForce : update,
options : function (newOptions) {
if (newOptions) {
if (typeof newOptions.gravity === 'number') { gravity = newOptions.gravity; }
if (typeof newOptions.theta === 'number') { theta = newOptions.theta; }
i = max - 1;
if (i > 0) {
root.body = bodies[i];
}
while (i--) {
insert(bodies[i], root);
}
};
return this;
}
return {
insertBodies: insertBodies,
updateBodyForce: update,
options: function(newOptions) {
if (newOptions) {
if (typeof newOptions.gravity === 'number') {
gravity = newOptions.gravity;
}
if (typeof newOptions.theta === 'number') {
theta = newOptions.theta;
}
return {gravity : gravity, theta : theta};
}
};
return this;
}
return {
gravity: gravity,
theta: theta
};
}
};
};

7

insertStack.js
module.exports = InsertStack;
/**
* Our implmentation of QuadTree is non-recursive (recursion handled not really
* well in old browsers). This data structure represent stack of elemnts
* which we are trying to insert into quad tree. It also avoids unnecessary
* memory pressue when we are adding more elements
* Our implmentation of QuadTree is non-recursive to avoid GC hit
* This data structure represent stack of elements
* which we are trying to insert into quad tree.
*/

@@ -9,0 +8,0 @@ function InsertStack () {

3

node.js

@@ -27,5 +27,2 @@ /**

this.right = 0;
// Node is internal when it is not a leaf
this.isInternal = false;
};

5

package.json
{
"name": "ngraph.quadtreebh",
"version": "0.0.1",
"version": "0.0.2",
"description": "Quad tree data structure for Barnes-Hut simulation",

@@ -25,3 +25,4 @@ "main": "index.js",

"tap": "~0.4.4",
"ngraph.physics.primitives": "0.0.2"
"ngraph.physics.primitives": "0.0.2",
"benchmark": "~1.0.0"
},

@@ -28,0 +29,0 @@ "dependencies": {

8

perf/perfresults.txt

@@ -1,5 +0,3 @@

Oct 22:
Node: 0.10.16, v8: 3.14.5.9
Creating tree: 13222ms
Calculating NBody for 1000000 bodies. Theta: 1.2; time: 18577ms
Bodies #10000
Theta 1.2 x 12.71 ops/sec ±5.48% (36 runs sampled)
Theta 0.8 x 8.65 ops/sec ±5.20% (26 runs sampled)
perf/1m.js
SocketSocket SOC 2 Logo

Product

  • Package Alerts
  • Integrations
  • Docs
  • Pricing
  • FAQ
  • Roadmap

About

Packages

Stay in touch

Get open source security insights delivered straight into your inbox.

  • Terms
  • Privacy
  • Security

Made with ⚡️ by Socket Inc