bundles/org.simantics.debug.graphical/src/org/simantics/debug/graphical/layout/BarnesHut.java

   1 package org.simantics.debug.graphical.layout;\r
   2 \r
   3 public class BarnesHut {\r
   4     \r
   5     static class Bounds {\r
   6         final double minX;\r
   7         final double minY;\r
   8         final double maxX;\r
   9         final double maxY;\r
  10         \r
  11         public Bounds(double minX, double minY, double maxX, double maxY) {\r
  12             this.minX = minX;\r
  13             this.minY = minY;\r
  14             this.maxX = maxX;\r
  15             this.maxY = maxY;\r
  16         }\r
  17     }\r
  18     \r
  19     private static Bounds computeOctreeBounds(double[] posX, double[] posY) {\r
  20         double minX = posX[0];\r
  21         double minY = posY[0];\r
  22         double maxX = posX[0];\r
  23         double maxY = posY[0];\r
  24         \r
  25         for(int i=1;i<posX.length;++i) {\r
  26             double x = posX[i];\r
  27             double y = posY[i];\r
  28             if(x < minX)\r
  29                 minX = x;\r
  30             else if(x > maxX)\r
  31                 maxX = x;\r
  32             if(y < minY)\r
  33                 minY = y;\r
  34             else if(y > maxY)\r
  35                 maxY = y;\r
  36         }\r
  37         \r
  38         double diff = (maxX - minX) - (maxY - minY);\r
  39         diff *= 0.5;\r
  40         if(diff > 0.0) {\r
  41             minY -= diff;\r
  42             maxY += diff;\r
  43         }\r
  44         else {\r
  45             minX += diff;\r
  46             maxX -= diff;   \r
  47         }\r
  48         return new Bounds(minX, minY, maxX, maxY);\r
  49     }\r
  50 \r
  51     private static class VecRef {\r
  52         double x;\r
  53         double y;\r
  54     }\r
  55     \r
  56     /*private static void force(VecRef f, double x1, double y1, double x2, double y2) {\r
  57         double dx = x2 - x1;\r
  58         double dy = y2 - y1;\r
  59         double l2 = dx*dx + dy*dy;\r
  60         double s = Q / l2;\r
  61         f.x -= s * dx;\r
  62         f.y -= s * dy;\r
  63     }\r
  64     \r
  65     private static void forceNear(VecRef f, double x1, double y1, OctreeNode node, double[] posX, double[] posY) {\r
  66         if(node instanceof OctreeLeaf) {\r
  67             for(int id : ((OctreeLeaf)node).ids) {\r
  68                 force(f, x1, y1, posX[id], posY[id]);\r
  69             }\r
  70         }\r
  71         else {\r
  72             OctreeInnerNode inner = (OctreeInnerNode)node;\r
  73             forceNear(f, x1, y1, inner.n00, posX, posY);\r
  74             forceNear(f, x1, y1, inner.n10, posX, posY);\r
  75             forceNear(f, x1, y1, inner.n01, posX, posY);\r
  76             forceNear(f, x1, y1, inner.n11, posX, posY);\r
  77         }\r
  78     }\r
  79     \r
  80     private static void forceFar(VecRef f, double x1, double y1, OctreeNode node) {\r
  81         double dx = node.massCenterX - x1;\r
  82         double dy = node.massCenterY - y1;\r
  83         double l2 = dx*dx + dy*dy;\r
  84         double s = Q * node.mass / l2;\r
  85         f.x -= s * dx;\r
  86         f.y -= s * dy;\r
  87     }\r
  88     \r
  89     private static void computeForce(OctreeNode octree, \r
  90             ArrayList<OctreeNode> farNodes,\r
  91             ArrayList<OctreeNode> nearNodes,\r
  92             double[] posX, double[] posY, \r
  93             double[] forceX, double[] forceY) {\r
  94         VecRef f = new VecRef();\r
  95         if(octree instanceof OctreeLeaf) {\r
  96             int[] ids = ((OctreeLeaf)octree).ids;\r
  97             for(int i=0;i<ids.length;++i) {\r
  98                 int id = ids[i];\r
  99                 \r
 100                 double x = posX[id];\r
 101                 double y = posY[id];\r
 102                 f.x = 0.0;\r
 103                 f.y = 0.0;\r
 104                 \r
 105                 for(int j=0;j<ids.length;++j)\r
 106                     if(j != i) {\r
 107                         int id2 = ids[j];\r
 108                         force(f, x, y, posX[id2], posY[id2]);\r
 109                     }\r
 110                 for(OctreeNode node : nearNodes)\r
 111                     forceNear(f, x, y, node, posX, posY);\r
 112                 for(OctreeNode node : farNodes)\r
 113                     forceFar(f, x, y, node);\r
 114                                 \r
 115                 forceX[id] += f.x;\r
 116                 forceY[id] += f.y;\r
 117             }\r
 118         }\r
 119         else {\r
 120             OctreeInnerNode inner = (OctreeInnerNode)octree;\r
 121             computeForce(inner.n00, farNodes, nearNodes, posX, posY, forceX, forceY);\r
 122             computeForce(inner.n10, farNodes, nearNodes, posX, posY, forceX, forceY);\r
 123             computeForce(inner.n01, farNodes, nearNodes, posX, posY, forceX, forceY);\r
 124             computeForce(inner.n11, farNodes, nearNodes, posX, posY, forceX, forceY);\r
 125         }\r
 126     }\r
 127     \r
 128     public static void computeRepulsiveForces(double[] posX, double[] posY, double[] forceX, double[] forceY) {\r
 129         Bounds bounds = computeOctreeBounds(posX, posY);\r
 130         \r
 131         TIntArrayList ids = new TIntArrayList(posX.length);\r
 132         for(int i=0;i<posX.length;++i)\r
 133             ids.add(i);\r
 134         OctreeNode octree = constructOctree(bounds.minX, bounds.minY, bounds.maxX, bounds.maxY, ids, posX, posY);\r
 135         \r
 136         computeForce(octree, new ArrayList<OctreeNode>(), new ArrayList<OctreeNode>(), posX, posY, forceX, forceY);\r
 137     }*/\r
 138     \r
 139 }\r