1 package org.simantics.debug.graphical.layout;
3 public class BarnesHut {
11 public Bounds(double minX, double minY, double maxX, double maxY) {
19 private static Bounds computeOctreeBounds(double[] posX, double[] posY) {
20 double minX = posX[0];
21 double minY = posY[0];
22 double maxX = posX[0];
23 double maxY = posY[0];
25 for(int i=1;i<posX.length;++i) {
38 double diff = (maxX - minX) - (maxY - minY);
48 return new Bounds(minX, minY, maxX, maxY);
51 private static class VecRef {
56 /*private static void force(VecRef f, double x1, double y1, double x2, double y2) {
59 double l2 = dx*dx + dy*dy;
65 private static void forceNear(VecRef f, double x1, double y1, OctreeNode node, double[] posX, double[] posY) {
66 if(node instanceof OctreeLeaf) {
67 for(int id : ((OctreeLeaf)node).ids) {
68 force(f, x1, y1, posX[id], posY[id]);
72 OctreeInnerNode inner = (OctreeInnerNode)node;
73 forceNear(f, x1, y1, inner.n00, posX, posY);
74 forceNear(f, x1, y1, inner.n10, posX, posY);
75 forceNear(f, x1, y1, inner.n01, posX, posY);
76 forceNear(f, x1, y1, inner.n11, posX, posY);
80 private static void forceFar(VecRef f, double x1, double y1, OctreeNode node) {
81 double dx = node.massCenterX - x1;
82 double dy = node.massCenterY - y1;
83 double l2 = dx*dx + dy*dy;
84 double s = Q * node.mass / l2;
89 private static void computeForce(OctreeNode octree,
90 ArrayList<OctreeNode> farNodes,
91 ArrayList<OctreeNode> nearNodes,
92 double[] posX, double[] posY,
93 double[] forceX, double[] forceY) {
94 VecRef f = new VecRef();
95 if(octree instanceof OctreeLeaf) {
96 int[] ids = ((OctreeLeaf)octree).ids;
97 for(int i=0;i<ids.length;++i) {
105 for(int j=0;j<ids.length;++j)
108 force(f, x, y, posX[id2], posY[id2]);
110 for(OctreeNode node : nearNodes)
111 forceNear(f, x, y, node, posX, posY);
112 for(OctreeNode node : farNodes)
113 forceFar(f, x, y, node);
120 OctreeInnerNode inner = (OctreeInnerNode)octree;
121 computeForce(inner.n00, farNodes, nearNodes, posX, posY, forceX, forceY);
122 computeForce(inner.n10, farNodes, nearNodes, posX, posY, forceX, forceY);
123 computeForce(inner.n01, farNodes, nearNodes, posX, posY, forceX, forceY);
124 computeForce(inner.n11, farNodes, nearNodes, posX, posY, forceX, forceY);
128 public static void computeRepulsiveForces(double[] posX, double[] posY, double[] forceX, double[] forceY) {
129 Bounds bounds = computeOctreeBounds(posX, posY);
131 TIntArrayList ids = new TIntArrayList(posX.length);
132 for(int i=0;i<posX.length;++i)
134 OctreeNode octree = constructOctree(bounds.minX, bounds.minY, bounds.maxX, bounds.maxY, ids, posX, posY);
136 computeForce(octree, new ArrayList<OctreeNode>(), new ArrayList<OctreeNode>(), posX, posY, forceX, forceY);