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

   1 package org.simantics.debug.graphical.layout;
   2
   3 import java.util.ArrayList;
   4 import java.util.Iterator;
   5
   6 public class BarnesHut2 {
   7
   8     static final double OPTIMAL_DISTANCE = 150.0;
   9     static final double C = 0.1;
  10     static final double K = C / OPTIMAL_DISTANCE;
  11     static final double G = K;
  12     static final double Q = C * OPTIMAL_DISTANCE * OPTIMAL_DISTANCE;
  13
  14     public static final int OCTREE_LEAF_SIZE = 25;
  15
  16     public static void applyDirectedForce(Particle a, Particle b) {
  17         double dx = a.x - b.x;
  18         double dy = a.y - b.y;
  19         double l2 = dx*dx + dy*dy;
  20         double s = Q / l2;
  21         a.fx += s * dx;
  22         a.fy += s * dy;
  23     }
  24
  25     public static void applyDirectedForce(Particle a, OctreeNode b) {
  26         double dx = a.x - b.massCenterX;
  27         double dy = a.y - b.massCenterY;
  28         double l2 = dx*dx + dy*dy;
  29         double s = Q * b.mass / l2;
  30         a.fx += s * dx;
  31         a.fy += s * dy;
  32     }
  33
  34     private static abstract class OctreeNode {
  35         double mass;
  36         double massCenterX;
  37         double massCenterY;
  38     }
  39
  40     private static class OctreeInnerNode extends OctreeNode {
  41         final OctreeNode n00;
  42         final OctreeNode n10;
  43         final OctreeNode n01;
  44         final OctreeNode n11;
  45
  46         public OctreeInnerNode(OctreeNode n00, OctreeNode n10, OctreeNode n01, OctreeNode n11) {
  47             this.n00 = n00;
  48             this.n10 = n10;
  49             this.n01 = n01;
  50             this.n11 = n11;
  51
  52             double mass00 = n00.mass;
  53             double mass10 = n10.mass;
  54             double mass01 = n01.mass;
  55             double mass11 = n11.mass;
  56             double totalMass = mass00 + mass10 + mass01 + mass11;
  57
  58             this.mass = totalMass;
  59             this.massCenterX =
  60                     (n00.massCenterX*mass00 + n10.massCenterX*mass10 +
  61                             n01.massCenterX*mass01 + n11.massCenterX*mass11)
  62                     / totalMass;
  63             this.massCenterY =
  64                     (n00.massCenterY*mass00 + n10.massCenterY*mass10 +
  65                             n01.massCenterY*mass01 + n11.massCenterY*mass11)
  66                     / totalMass;
  67         }
  68     }
  69
  70     private static class OctreeLeaf extends OctreeNode {
  71         final Particle[] ps;
  72
  73         public OctreeLeaf(Particle[] ps) {
  74             this.ps = ps;
  75
  76             double massCenterX = 0.0;
  77             double massCenterY = 0.0;
  78             for(Particle p : ps) {
  79                 massCenterX += p.x;
  80                 massCenterY += p.y;
  81             }
  82
  83             this.mass = ps.length;
  84             this.massCenterX = massCenterX / ps.length;
  85             this.massCenterY = massCenterY / ps.length;
  86         }
  87     }
  88
  89     private static OctreeNode constructOctree(double minX, double minY, double maxX, double maxY,
  90             ArrayList<Particle> ps) {
  91         if(ps.size() < OCTREE_LEAF_SIZE)
  92             return new OctreeLeaf(ps.toArray(new Particle[ps.size()]));
  93
  94         double midX = 0.5 * (minX + maxX);
  95         double midY = 0.5 * (minY + maxY);
  96
  97         ArrayList<Particle> ps00 = new ArrayList<Particle>();
  98         ArrayList<Particle> ps10 = new ArrayList<Particle>();
  99         ArrayList<Particle> ps01 = new ArrayList<Particle>();
 100         ArrayList<Particle> ps11 = new ArrayList<Particle>();
 101
 102         for(Particle p : ps) {
 103             double x = p.x;
 104             double y = p.y;
 105             if(x < midX) {
 106                 if(y < midY)
 107                     ps00.add(p);
 108                 else
 109                     ps01.add(p);
 110             }
 111             else {
 112                 if(y < midY)
 113                     ps10.add(p);
 114                 else
 115                     ps11.add(p);
 116             }
 117         }
 118
 119         return new OctreeInnerNode(
 120                 constructOctree(minX, minY, midX, midY, ps00),
 121                 constructOctree(midX, minY, maxX, midY, ps10),
 122                 constructOctree(minX, midY, midX, maxY, ps01),
 123                 constructOctree(midX, midY, maxX, maxY, ps11)
 124                 );
 125     }
 126
 127     static class Bounds {
 128         final double minX;
 129         final double minY;
 130         final double maxX;
 131         final double maxY;
 132
 133         public Bounds(double minX, double minY, double maxX, double maxY) {
 134             this.minX = minX;
 135             this.minY = minY;
 136             this.maxX = maxX;
 137             this.maxY = maxY;
 138         }
 139     }
 140
 141     private static Bounds computeOctreeBounds(ArrayList<Particle> ps) {
 142         Iterator<Particle> it = ps.iterator();
 143
 144         Particle pFirst = it.next();
 145
 146         double minX = pFirst.x;
 147         double minY = pFirst.y;
 148         double maxX = pFirst.x;
 149         double maxY = pFirst.y;
 150
 151         while(it.hasNext()) {
 152             Particle p = it.next();
 153             double x = p.x;
 154             double y = p.y;
 155             if(x < minX)
 156                 minX = x;
 157             else if(x > maxX)
 158                 maxX = x;
 159             if(y < minY)
 160                 minY = y;
 161             else if(y > maxY)
 162                 maxY = y;
 163         }
 164
 165         double diff = (maxX - minX) - (maxY - minY);
 166         diff *= 0.5;
 167         if(diff > 0.0) {
 168             minY -= diff;
 169             maxY += diff;
 170         }
 171         else {
 172             minX += diff;
 173             maxX -= diff;
 174         }
 175         return new Bounds(minX, minY, maxX, maxY);
 176     }
 177
 178     private static void computeForce(OctreeNode octree,
 179             ArrayList<OctreeNode> nearNodes, ArrayList<OctreeNode> farNodes) {
 180         // TODO Auto-generated method stub
 181
 182     }
 183
 184     public static void computeRepulsiveForces(ArrayList<Particle> ps) {
 185         Bounds bounds = computeOctreeBounds(ps);
 186         OctreeNode octree = constructOctree(bounds.minX, bounds.minY, bounds.maxX, bounds.maxY, ps);
 187         computeForce(octree, new ArrayList<OctreeNode>(), new ArrayList<OctreeNode>());
 188     }
 189 }