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

   1 package org.simantics.debug.graphical.layout;
   2
   3 public class ExtensionLayoutAlgorithm {
   4     final double OPTIMAL_DISTANCE = 150.0;
   5     final double C = 0.1;
   6     final double K = C / OPTIMAL_DISTANCE;
   7     final double G = K;
   8     final double Q = C * OPTIMAL_DISTANCE * OPTIMAL_DISTANCE;
   9     final double TOLERANCE = 1e-3;
  10     final int MAX_ITERATIONS = 10000;
  11     final long TIMEOUT = 1000000000L; // 1 sec
  12     final double MAX_MOVE2 = 40000.0;
  13
  14     int size;
  15     double[] posX;
  16     double[] posY;
  17     double[] forceX;
  18     double[] forceY;
  19
  20     int repulsiveSize;
  21     double[] fixedRepulsiveX;
  22     double[] fixedRepulsiveY;
  23     double[][] neighbors;
  24
  25     public ExtensionLayoutAlgorithm(double[][] neighbors,
  26             double[] fixedRepulsiveX, double[] fixedRepulsiveY) {
  27         this.size = neighbors.length;
  28         this.neighbors = neighbors;
  29         this.repulsiveSize = fixedRepulsiveX.length;
  30         this.fixedRepulsiveX = fixedRepulsiveX;
  31         this.fixedRepulsiveY = fixedRepulsiveY;
  32         this.posX = new double[size];
  33         this.posY = new double[size];
  34         this.forceX = new double[size];
  35         this.forceY = new double[size];
  36     }
  37
  38     public double[] getPosX() {
  39         return posX;
  40     }
  41
  42     public double[] getPosY() {
  43         return posY;
  44     }
  45
  46     private void computeForces() {
  47         for(int i=0;i<size;++i) {
  48             double x = posX[i];
  49             double y = posY[i];
  50             double fx = -G * x;
  51             double fy = -G * y;
  52
  53             for(int j=0;j<size;++j)
  54                 if(j != i) {
  55                     double dx = posX[j] - x;
  56                     double dy = posY[j] - y;
  57                     double l2 = dx*dx + dy*dy;
  58                     fx -= Q * dx / l2;
  59                     fy -= Q * dy / l2;
  60                 }
  61             for(int j=0;j<repulsiveSize;++j)
  62                 if(j != i) {
  63                     double dx = fixedRepulsiveX[j] - x;
  64                     double dy = fixedRepulsiveY[j] - y;
  65                     double l2 = dx*dx + dy*dy;
  66                     fx -= Q * dx / l2;
  67                     fy -= Q * dy / l2;
  68                 }
  69
  70             double[] ns = neighbors[i];
  71             for(int j=0;j<ns.length;j+=2) {
  72                 double dx = ns[j] - x;
  73                 double dy = ns[j+1] - y;
  74                 double l2 = dx*dx + dy*dy;
  75                 double l = Math.sqrt(l2);
  76                 fx += K * l * dx;
  77                 fy += K * l * dy;
  78             }
  79
  80             forceX[i] = fx;
  81             forceY[i] = fy;
  82         }
  83     }
  84
  85     private boolean converged() {
  86         for(int i=0;i<size;++i) {
  87             double fx = forceX[i];
  88             double fy = forceY[i];
  89             double f2 = fx*fx + fy*fy;
  90             if(f2 > TOLERANCE)
  91                 return false;
  92         }
  93         return true;
  94     }
  95
  96     private void moveAll() {
  97         for(int i=0;i<size;++i) {
  98             double fx = forceX[i];
  99             double fy = forceY[i];
 100             double f2 = fx*fx + fy*fy;
 101             if(f2 > MAX_MOVE2) {
 102                 double s = Math.sqrt(MAX_MOVE2 / f2);
 103                 fx *= s;
 104                 fy *= s;
 105             }
 106             posX[i] += fx;
 107             posY[i] += fy;
 108         }
 109         computeForces();
 110     }
 111
 112     public void optimize() {
 113         computeForces();
 114
 115         long beginTime = System.nanoTime();
 116         int iter;
 117         for(iter=0;iter<MAX_ITERATIONS;++iter) {
 118             if(converged() || ((iter&0xf)==0 && System.nanoTime()-beginTime > TIMEOUT))
 119                 break;
 120             moveAll();
 121         }
 122         System.out.println("Elapsed: " + (System.nanoTime()-beginTime)*1e-6 + " ms");
 123         System.out.println("Iterations: " + iter);
 124     }
 125 }