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

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