-package org.simantics.debug.graphical.layout;\r
-\r
-public class BarnesHut {\r
- \r
- static class Bounds {\r
- final double minX;\r
- final double minY;\r
- final double maxX;\r
- final double maxY;\r
- \r
- public Bounds(double minX, double minY, double maxX, double maxY) {\r
- this.minX = minX;\r
- this.minY = minY;\r
- this.maxX = maxX;\r
- this.maxY = maxY;\r
- }\r
- }\r
- \r
- private static Bounds computeOctreeBounds(double[] posX, double[] posY) {\r
- double minX = posX[0];\r
- double minY = posY[0];\r
- double maxX = posX[0];\r
- double maxY = posY[0];\r
- \r
- for(int i=1;i<posX.length;++i) {\r
- double x = posX[i];\r
- double y = posY[i];\r
- if(x < minX)\r
- minX = x;\r
- else if(x > maxX)\r
- maxX = x;\r
- if(y < minY)\r
- minY = y;\r
- else if(y > maxY)\r
- maxY = y;\r
- }\r
- \r
- double diff = (maxX - minX) - (maxY - minY);\r
- diff *= 0.5;\r
- if(diff > 0.0) {\r
- minY -= diff;\r
- maxY += diff;\r
- }\r
- else {\r
- minX += diff;\r
- maxX -= diff; \r
- }\r
- return new Bounds(minX, minY, maxX, maxY);\r
- }\r
-\r
- private static class VecRef {\r
- double x;\r
- double y;\r
- }\r
- \r
- /*private static void force(VecRef f, double x1, double y1, double x2, double y2) {\r
- double dx = x2 - x1;\r
- double dy = y2 - y1;\r
- double l2 = dx*dx + dy*dy;\r
- double s = Q / l2;\r
- f.x -= s * dx;\r
- f.y -= s * dy;\r
- }\r
- \r
- private static void forceNear(VecRef f, double x1, double y1, OctreeNode node, double[] posX, double[] posY) {\r
- if(node instanceof OctreeLeaf) {\r
- for(int id : ((OctreeLeaf)node).ids) {\r
- force(f, x1, y1, posX[id], posY[id]);\r
- }\r
- }\r
- else {\r
- OctreeInnerNode inner = (OctreeInnerNode)node;\r
- forceNear(f, x1, y1, inner.n00, posX, posY);\r
- forceNear(f, x1, y1, inner.n10, posX, posY);\r
- forceNear(f, x1, y1, inner.n01, posX, posY);\r
- forceNear(f, x1, y1, inner.n11, posX, posY);\r
- }\r
- }\r
- \r
- private static void forceFar(VecRef f, double x1, double y1, OctreeNode node) {\r
- double dx = node.massCenterX - x1;\r
- double dy = node.massCenterY - y1;\r
- double l2 = dx*dx + dy*dy;\r
- double s = Q * node.mass / l2;\r
- f.x -= s * dx;\r
- f.y -= s * dy;\r
- }\r
- \r
- private static void computeForce(OctreeNode octree, \r
- ArrayList<OctreeNode> farNodes,\r
- ArrayList<OctreeNode> nearNodes,\r
- double[] posX, double[] posY, \r
- double[] forceX, double[] forceY) {\r
- VecRef f = new VecRef();\r
- if(octree instanceof OctreeLeaf) {\r
- int[] ids = ((OctreeLeaf)octree).ids;\r
- for(int i=0;i<ids.length;++i) {\r
- int id = ids[i];\r
- \r
- double x = posX[id];\r
- double y = posY[id];\r
- f.x = 0.0;\r
- f.y = 0.0;\r
- \r
- for(int j=0;j<ids.length;++j)\r
- if(j != i) {\r
- int id2 = ids[j];\r
- force(f, x, y, posX[id2], posY[id2]);\r
- }\r
- for(OctreeNode node : nearNodes)\r
- forceNear(f, x, y, node, posX, posY);\r
- for(OctreeNode node : farNodes)\r
- forceFar(f, x, y, node);\r
- \r
- forceX[id] += f.x;\r
- forceY[id] += f.y;\r
- }\r
- }\r
- else {\r
- OctreeInnerNode inner = (OctreeInnerNode)octree;\r
- computeForce(inner.n00, farNodes, nearNodes, posX, posY, forceX, forceY);\r
- computeForce(inner.n10, farNodes, nearNodes, posX, posY, forceX, forceY);\r
- computeForce(inner.n01, farNodes, nearNodes, posX, posY, forceX, forceY);\r
- computeForce(inner.n11, farNodes, nearNodes, posX, posY, forceX, forceY);\r
- }\r
- }\r
- \r
- public static void computeRepulsiveForces(double[] posX, double[] posY, double[] forceX, double[] forceY) {\r
- Bounds bounds = computeOctreeBounds(posX, posY);\r
- \r
- TIntArrayList ids = new TIntArrayList(posX.length);\r
- for(int i=0;i<posX.length;++i)\r
- ids.add(i);\r
- OctreeNode octree = constructOctree(bounds.minX, bounds.minY, bounds.maxX, bounds.maxY, ids, posX, posY);\r
- \r
- computeForce(octree, new ArrayList<OctreeNode>(), new ArrayList<OctreeNode>(), posX, posY, forceX, forceY);\r
- }*/\r
- \r
-}\r
+package org.simantics.debug.graphical.layout;
+
+public class BarnesHut {
+
+ static class Bounds {
+ final double minX;
+ final double minY;
+ final double maxX;
+ final double maxY;
+
+ public Bounds(double minX, double minY, double maxX, double maxY) {
+ this.minX = minX;
+ this.minY = minY;
+ this.maxX = maxX;
+ this.maxY = maxY;
+ }
+ }
+
+ private static Bounds computeOctreeBounds(double[] posX, double[] posY) {
+ double minX = posX[0];
+ double minY = posY[0];
+ double maxX = posX[0];
+ double maxY = posY[0];
+
+ for(int i=1;i<posX.length;++i) {
+ double x = posX[i];
+ double y = posY[i];
+ if(x < minX)
+ minX = x;
+ else if(x > maxX)
+ maxX = x;
+ if(y < minY)
+ minY = y;
+ else if(y > maxY)
+ maxY = y;
+ }
+
+ double diff = (maxX - minX) - (maxY - minY);
+ diff *= 0.5;
+ if(diff > 0.0) {
+ minY -= diff;
+ maxY += diff;
+ }
+ else {
+ minX += diff;
+ maxX -= diff;
+ }
+ return new Bounds(minX, minY, maxX, maxY);
+ }
+
+ private static class VecRef {
+ double x;
+ double y;
+ }
+
+ /*private static void force(VecRef f, double x1, double y1, double x2, double y2) {
+ double dx = x2 - x1;
+ double dy = y2 - y1;
+ double l2 = dx*dx + dy*dy;
+ double s = Q / l2;
+ f.x -= s * dx;
+ f.y -= s * dy;
+ }
+
+ private static void forceNear(VecRef f, double x1, double y1, OctreeNode node, double[] posX, double[] posY) {
+ if(node instanceof OctreeLeaf) {
+ for(int id : ((OctreeLeaf)node).ids) {
+ force(f, x1, y1, posX[id], posY[id]);
+ }
+ }
+ else {
+ OctreeInnerNode inner = (OctreeInnerNode)node;
+ forceNear(f, x1, y1, inner.n00, posX, posY);
+ forceNear(f, x1, y1, inner.n10, posX, posY);
+ forceNear(f, x1, y1, inner.n01, posX, posY);
+ forceNear(f, x1, y1, inner.n11, posX, posY);
+ }
+ }
+
+ private static void forceFar(VecRef f, double x1, double y1, OctreeNode node) {
+ double dx = node.massCenterX - x1;
+ double dy = node.massCenterY - y1;
+ double l2 = dx*dx + dy*dy;
+ double s = Q * node.mass / l2;
+ f.x -= s * dx;
+ f.y -= s * dy;
+ }
+
+ private static void computeForce(OctreeNode octree,
+ ArrayList<OctreeNode> farNodes,
+ ArrayList<OctreeNode> nearNodes,
+ double[] posX, double[] posY,
+ double[] forceX, double[] forceY) {
+ VecRef f = new VecRef();
+ if(octree instanceof OctreeLeaf) {
+ int[] ids = ((OctreeLeaf)octree).ids;
+ for(int i=0;i<ids.length;++i) {
+ int id = ids[i];
+
+ double x = posX[id];
+ double y = posY[id];
+ f.x = 0.0;
+ f.y = 0.0;
+
+ for(int j=0;j<ids.length;++j)
+ if(j != i) {
+ int id2 = ids[j];
+ force(f, x, y, posX[id2], posY[id2]);
+ }
+ for(OctreeNode node : nearNodes)
+ forceNear(f, x, y, node, posX, posY);
+ for(OctreeNode node : farNodes)
+ forceFar(f, x, y, node);
+
+ forceX[id] += f.x;
+ forceY[id] += f.y;
+ }
+ }
+ else {
+ OctreeInnerNode inner = (OctreeInnerNode)octree;
+ computeForce(inner.n00, farNodes, nearNodes, posX, posY, forceX, forceY);
+ computeForce(inner.n10, farNodes, nearNodes, posX, posY, forceX, forceY);
+ computeForce(inner.n01, farNodes, nearNodes, posX, posY, forceX, forceY);
+ computeForce(inner.n11, farNodes, nearNodes, posX, posY, forceX, forceY);
+ }
+ }
+
+ public static void computeRepulsiveForces(double[] posX, double[] posY, double[] forceX, double[] forceY) {
+ Bounds bounds = computeOctreeBounds(posX, posY);
+
+ TIntArrayList ids = new TIntArrayList(posX.length);
+ for(int i=0;i<posX.length;++i)
+ ids.add(i);
+ OctreeNode octree = constructOctree(bounds.minX, bounds.minY, bounds.maxX, bounds.maxY, ids, posX, posY);
+
+ computeForce(octree, new ArrayList<OctreeNode>(), new ArrayList<OctreeNode>(), posX, posY, forceX, forceY);
+ }*/
+
+}