Migrated source code from Simantics SVN

[simantics/platform.git] / bundles / org.simantics.debug.graphical / src / org / simantics / debug / graphical / layout / BarnesHut.java

diff --git a/bundles/org.simantics.debug.graphical/src/org/simantics/debug/graphical/layout/BarnesHut.java b/bundles/org.simantics.debug.graphical/src/org/simantics/debug/graphical/layout/BarnesHut.java
new file mode 100644 (file)
index 0000000..caf097c
--- /dev/null
+++ b/bundles/org.simantics.debug.graphical/src/org/simantics/debug/graphical/layout/BarnesHut.java
@@ -0,0 +1,139 @@
+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