-package org.simantics.debug.graphical.layout;\r
-\r
-public class ExtensionLayoutAlgorithm {\r
- final double OPTIMAL_DISTANCE = 150.0; \r
- final double C = 0.1;\r
- final double K = C / OPTIMAL_DISTANCE;\r
- final double G = K;\r
- final double Q = C * OPTIMAL_DISTANCE * OPTIMAL_DISTANCE;\r
- final double TOLERANCE = 1e-3;\r
- final int MAX_ITERATIONS = 10000;\r
- final long TIMEOUT = 1000000000L; // 1 sec\r
- final double MAX_MOVE2 = 40000.0;\r
- \r
- int size;\r
- double[] posX;\r
- double[] posY;\r
- double[] forceX;\r
- double[] forceY;\r
- \r
- int repulsiveSize;\r
- double[] fixedRepulsiveX;\r
- double[] fixedRepulsiveY;\r
- double[][] neighbors;\r
- \r
- public ExtensionLayoutAlgorithm(double[][] neighbors, \r
- double[] fixedRepulsiveX, double[] fixedRepulsiveY) {\r
- this.size = neighbors.length;\r
- this.neighbors = neighbors;\r
- this.repulsiveSize = fixedRepulsiveX.length;\r
- this.fixedRepulsiveX = fixedRepulsiveX;\r
- this.fixedRepulsiveY = fixedRepulsiveY;\r
- this.posX = new double[size];\r
- this.posY = new double[size];\r
- this.forceX = new double[size];\r
- this.forceY = new double[size];\r
- }\r
- \r
- public double[] getPosX() {\r
- return posX;\r
- }\r
- \r
- public double[] getPosY() {\r
- return posY;\r
- }\r
- \r
- private void computeForces() {\r
- for(int i=0;i<size;++i) {\r
- double x = posX[i];\r
- double y = posY[i];\r
- double fx = -G * x;\r
- double fy = -G * y;\r
- \r
- for(int j=0;j<size;++j)\r
- if(j != i) {\r
- double dx = posX[j] - x;\r
- double dy = posY[j] - y;\r
- double l2 = dx*dx + dy*dy;\r
- fx -= Q * dx / l2;\r
- fy -= Q * dy / l2;\r
- }\r
- for(int j=0;j<repulsiveSize;++j)\r
- if(j != i) {\r
- double dx = fixedRepulsiveX[j] - x;\r
- double dy = fixedRepulsiveY[j] - y;\r
- double l2 = dx*dx + dy*dy;\r
- fx -= Q * dx / l2;\r
- fy -= Q * dy / l2;\r
- }\r
- \r
- double[] ns = neighbors[i];\r
- for(int j=0;j<ns.length;j+=2) {\r
- double dx = ns[j] - x;\r
- double dy = ns[j+1] - y; \r
- double l2 = dx*dx + dy*dy;\r
- double l = Math.sqrt(l2);\r
- fx += K * l * dx;\r
- fy += K * l * dy;\r
- }\r
- \r
- forceX[i] = fx;\r
- forceY[i] = fy;\r
- }\r
- }\r
- \r
- private boolean converged() {\r
- for(int i=0;i<size;++i) {\r
- double fx = forceX[i];\r
- double fy = forceY[i];\r
- double f2 = fx*fx + fy*fy;\r
- if(f2 > TOLERANCE)\r
- return false;\r
- }\r
- return true;\r
- }\r
- \r
- private void moveAll() {\r
- for(int i=0;i<size;++i) {\r
- double fx = forceX[i];\r
- double fy = forceY[i];\r
- double f2 = fx*fx + fy*fy;\r
- if(f2 > MAX_MOVE2) {\r
- double s = Math.sqrt(MAX_MOVE2 / f2);\r
- fx *= s;\r
- fy *= s;\r
- }\r
- posX[i] += fx;\r
- posY[i] += fy;\r
- }\r
- computeForces();\r
- }\r
- \r
- public void optimize() {\r
- computeForces();\r
-\r
- long beginTime = System.nanoTime();\r
- int iter;\r
- for(iter=0;iter<MAX_ITERATIONS;++iter) {\r
- if(converged() || ((iter&0xf)==0 && System.nanoTime()-beginTime > TIMEOUT))\r
- break; \r
- moveAll();\r
- }\r
- System.out.println("Elapsed: " + (System.nanoTime()-beginTime)*1e-6 + " ms");\r
- System.out.println("Iterations: " + iter);\r
- }\r
-}\r
+package org.simantics.debug.graphical.layout;
+
+public class ExtensionLayoutAlgorithm {
+ final double OPTIMAL_DISTANCE = 150.0;
+ final double C = 0.1;
+ final double K = C / OPTIMAL_DISTANCE;
+ final double G = K;
+ final double Q = C * OPTIMAL_DISTANCE * OPTIMAL_DISTANCE;
+ final double TOLERANCE = 1e-3;
+ final int MAX_ITERATIONS = 10000;
+ final long TIMEOUT = 1000000000L; // 1 sec
+ final double MAX_MOVE2 = 40000.0;
+
+ int size;
+ double[] posX;
+ double[] posY;
+ double[] forceX;
+ double[] forceY;
+
+ int repulsiveSize;
+ double[] fixedRepulsiveX;
+ double[] fixedRepulsiveY;
+ double[][] neighbors;
+
+ public ExtensionLayoutAlgorithm(double[][] neighbors,
+ double[] fixedRepulsiveX, double[] fixedRepulsiveY) {
+ this.size = neighbors.length;
+ this.neighbors = neighbors;
+ this.repulsiveSize = fixedRepulsiveX.length;
+ this.fixedRepulsiveX = fixedRepulsiveX;
+ this.fixedRepulsiveY = fixedRepulsiveY;
+ this.posX = new double[size];
+ this.posY = new double[size];
+ this.forceX = new double[size];
+ this.forceY = new double[size];
+ }
+
+ public double[] getPosX() {
+ return posX;
+ }
+
+ public double[] getPosY() {
+ return posY;
+ }
+
+ private void computeForces() {
+ for(int i=0;i<size;++i) {
+ double x = posX[i];
+ double y = posY[i];
+ double fx = -G * x;
+ double fy = -G * y;
+
+ for(int j=0;j<size;++j)
+ if(j != i) {
+ double dx = posX[j] - x;
+ double dy = posY[j] - y;
+ double l2 = dx*dx + dy*dy;
+ fx -= Q * dx / l2;
+ fy -= Q * dy / l2;
+ }
+ for(int j=0;j<repulsiveSize;++j)
+ if(j != i) {
+ double dx = fixedRepulsiveX[j] - x;
+ double dy = fixedRepulsiveY[j] - y;
+ double l2 = dx*dx + dy*dy;
+ fx -= Q * dx / l2;
+ fy -= Q * dy / l2;
+ }
+
+ double[] ns = neighbors[i];
+ for(int j=0;j<ns.length;j+=2) {
+ double dx = ns[j] - x;
+ double dy = ns[j+1] - y;
+ double l2 = dx*dx + dy*dy;
+ double l = Math.sqrt(l2);
+ fx += K * l * dx;
+ fy += K * l * dy;
+ }
+
+ forceX[i] = fx;
+ forceY[i] = fy;
+ }
+ }
+
+ private boolean converged() {
+ for(int i=0;i<size;++i) {
+ double fx = forceX[i];
+ double fy = forceY[i];
+ double f2 = fx*fx + fy*fy;
+ if(f2 > TOLERANCE)
+ return false;
+ }
+ return true;
+ }
+
+ private void moveAll() {
+ for(int i=0;i<size;++i) {
+ double fx = forceX[i];
+ double fy = forceY[i];
+ double f2 = fx*fx + fy*fy;
+ if(f2 > MAX_MOVE2) {
+ double s = Math.sqrt(MAX_MOVE2 / f2);
+ fx *= s;
+ fy *= s;
+ }
+ posX[i] += fx;
+ posY[i] += fy;
+ }
+ computeForces();
+ }
+
+ public void optimize() {
+ computeForces();
+
+ long beginTime = System.nanoTime();
+ int iter;
+ for(iter=0;iter<MAX_ITERATIONS;++iter) {
+ if(converged() || ((iter&0xf)==0 && System.nanoTime()-beginTime > TIMEOUT))
+ break;
+ moveAll();
+ }
+ System.out.println("Elapsed: " + (System.nanoTime()-beginTime)*1e-6 + " ms");
+ System.out.println("Iterations: " + iter);
+ }
+}