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

   1 package org.simantics.debug.graphical.layout;\r
   2 \r
   3 public class LayoutAlgorithm {\r
   4 \r
   5     final double OPTIMAL_DISTANCE = 150.0;   \r
   6     final double C = 0.1;\r
   7     final double K = C / OPTIMAL_DISTANCE;\r
   8     final double G = K;\r
   9     final double Q = C * OPTIMAL_DISTANCE * OPTIMAL_DISTANCE;\r
  10     final double TOLERANCE = 1e-3;\r
  11     final int MAX_ITERATIONS = 10000;\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[][] neighbors;\r
  21     \r
  22     public LayoutAlgorithm(int[][] neighbors) {\r
  23         this.size = neighbors.length;\r
  24         this.neighbors = neighbors;\r
  25         this.posX = new double[size];\r
  26         this.posY = new double[size];\r
  27         this.forceX = new double[size];\r
  28         this.forceY = new double[size];\r
  29     }\r
  30     \r
  31     public double[] getPosX() {\r
  32         return posX;\r
  33     }\r
  34     \r
  35     public double[] getPosY() {\r
  36         return posY;\r
  37     }\r
  38     \r
  39     private void computeForces() {\r
  40         for(int i=0;i<size;++i) {\r
  41             double x = posX[i];\r
  42             double y = posY[i];\r
  43             double fx = -G * x;\r
  44             double fy = -G * y;\r
  45             \r
  46             for(int j=0;j<size;++j)\r
  47                 if(j != i) {\r
  48                     double dx = posX[j] - x;\r
  49                     double dy = posY[j] - y;\r
  50                     double l2 = dx*dx + dy*dy;\r
  51                     /*double l = Math.sqrt(l2);\r
  52                     double l3 = l*l2;*/\r
  53                     fx -= Q * dx / l2;\r
  54                     fy -= Q * dy / l2;\r
  55                 }\r
  56             \r
  57             for(int j : neighbors[i]) {\r
  58                 double dx = posX[j] - x;\r
  59                 double dy = posY[j] - y;       \r
  60                 double l2 = dx*dx + dy*dy;\r
  61                 double l = Math.sqrt(l2);\r
  62                 fx += K * l * dx;\r
  63                 fy += K * l * dy;\r
  64             }\r
  65             \r
  66             forceX[i] = fx;\r
  67             forceY[i] = fy;\r
  68         }\r
  69     }\r
  70     \r
  71     private boolean converged() {\r
  72         for(int i=0;i<size;++i) {\r
  73             double fx = forceX[i];\r
  74             double fy = forceY[i];\r
  75             double f2 = fx*fx + fy*fy;\r
  76             if(f2 > TOLERANCE)\r
  77                 return false;\r
  78         }\r
  79         return true;\r
  80     }\r
  81     \r
  82     private void moveAll() {\r
  83         for(int i=0;i<size;++i) {\r
  84             double fx = forceX[i];\r
  85             double fy = forceY[i];\r
  86             double f2 = fx*fx + fy*fy;\r
  87             if(f2 > MAX_MOVE2) {\r
  88                 double s = Math.sqrt(MAX_MOVE2 / f2);\r
  89                 fx *= s;\r
  90                 fy *= s;\r
  91             }\r
  92             posX[i] += fx;\r
  93             posY[i] += fy;\r
  94         }\r
  95         computeForces();\r
  96     }\r
  97     \r
  98     public void optimize() {\r
  99         computeForces();\r
 100         \r
 101         for(int iter=0;iter<MAX_ITERATIONS;++iter) {\r
 102             if(converged())\r
 103                 break;\r
 104             moveAll();\r
 105         }\r
 106     }\r
 107 }\r