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

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