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

   1 package org.simantics.debug.graphical.layout;
   2
   3 public class BarnesHut {
   4
   5     static class Bounds {
   6         final double minX;
   7         final double minY;
   8         final double maxX;
   9         final double maxY;
  10
  11         public Bounds(double minX, double minY, double maxX, double maxY) {
  12             this.minX = minX;
  13             this.minY = minY;
  14             this.maxX = maxX;
  15             this.maxY = maxY;
  16         }
  17     }
  18
  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];
  24
  25         for(int i=1;i<posX.length;++i) {
  26             double x = posX[i];
  27             double y = posY[i];
  28             if(x < minX)
  29                 minX = x;
  30             else if(x > maxX)
  31                 maxX = x;
  32             if(y < minY)
  33                 minY = y;
  34             else if(y > maxY)
  35                 maxY = y;
  36         }
  37
  38         double diff = (maxX - minX) - (maxY - minY);
  39         diff *= 0.5;
  40         if(diff > 0.0) {
  41             minY -= diff;
  42             maxY += diff;
  43         }
  44         else {
  45             minX += diff;
  46             maxX -= diff;
  47         }
  48         return new Bounds(minX, minY, maxX, maxY);
  49     }
  50
  51     private static class VecRef {
  52         double x;
  53         double y;
  54     }
  55
  56     /*private static void force(VecRef f, double x1, double y1, double x2, double y2) {
  57         double dx = x2 - x1;
  58         double dy = y2 - y1;
  59         double l2 = dx*dx + dy*dy;
  60         double s = Q / l2;
  61         f.x -= s * dx;
  62         f.y -= s * dy;
  63     }
  64
  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]);
  69             }
  70         }
  71         else {
  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);
  77         }
  78     }
  79
  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;
  85         f.x -= s * dx;
  86         f.y -= s * dy;
  87     }
  88
  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) {
  98                 int id = ids[i];
  99
 100                 double x = posX[id];
 101                 double y = posY[id];
 102                 f.x = 0.0;
 103                 f.y = 0.0;
 104
 105                 for(int j=0;j<ids.length;++j)
 106                     if(j != i) {
 107                         int id2 = ids[j];
 108                         force(f, x, y, posX[id2], posY[id2]);
 109                     }
 110                 for(OctreeNode node : nearNodes)
 111                     forceNear(f, x, y, node, posX, posY);
 112                 for(OctreeNode node : farNodes)
 113                     forceFar(f, x, y, node);
 114
 115                 forceX[id] += f.x;
 116                 forceY[id] += f.y;
 117             }
 118         }
 119         else {
 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);
 125         }
 126     }
 127
 128     public static void computeRepulsiveForces(double[] posX, double[] posY, double[] forceX, double[] forceY) {
 129         Bounds bounds = computeOctreeBounds(posX, posY);
 130
 131         TIntArrayList ids = new TIntArrayList(posX.length);
 132         for(int i=0;i<posX.length;++i)
 133             ids.add(i);
 134         OctreeNode octree = constructOctree(bounds.minX, bounds.minY, bounds.maxX, bounds.maxY, ids, posX, posY);
 135
 136         computeForce(octree, new ArrayList<OctreeNode>(), new ArrayList<OctreeNode>(), posX, posY, forceX, forceY);
 137     }*/
 138
 139 }