-package org.simantics.debug.graphical.layout;\r
-\r
-import java.util.ArrayList;\r
-import java.util.Iterator;\r
-\r
-public class BarnesHut2 {\r
- \r
- static final double OPTIMAL_DISTANCE = 150.0; \r
- static final double C = 0.1;\r
- static final double K = C / OPTIMAL_DISTANCE;\r
- static final double G = K;\r
- static final double Q = C * OPTIMAL_DISTANCE * OPTIMAL_DISTANCE;\r
-\r
- public static final int OCTREE_LEAF_SIZE = 25;\r
- \r
- public static void applyDirectedForce(Particle a, Particle b) {\r
- double dx = a.x - b.x;\r
- double dy = a.y - b.y;\r
- double l2 = dx*dx + dy*dy;\r
- double s = Q / l2;\r
- a.fx += s * dx;\r
- a.fy += s * dy;\r
- }\r
- \r
- public static void applyDirectedForce(Particle a, OctreeNode b) {\r
- double dx = a.x - b.massCenterX;\r
- double dy = a.y - b.massCenterY;\r
- double l2 = dx*dx + dy*dy;\r
- double s = Q * b.mass / l2;\r
- a.fx += s * dx;\r
- a.fy += s * dy;\r
- }\r
- \r
- private static abstract class OctreeNode {\r
- double mass;\r
- double massCenterX;\r
- double massCenterY;\r
- }\r
- \r
- private static class OctreeInnerNode extends OctreeNode {\r
- final OctreeNode n00;\r
- final OctreeNode n10;\r
- final OctreeNode n01;\r
- final OctreeNode n11;\r
- \r
- public OctreeInnerNode(OctreeNode n00, OctreeNode n10, OctreeNode n01, OctreeNode n11) {\r
- this.n00 = n00;\r
- this.n10 = n10;\r
- this.n01 = n01;\r
- this.n11 = n11;\r
- \r
- double mass00 = n00.mass;\r
- double mass10 = n10.mass;\r
- double mass01 = n01.mass;\r
- double mass11 = n11.mass;\r
- double totalMass = mass00 + mass10 + mass01 + mass11;\r
- \r
- this.mass = totalMass;\r
- this.massCenterX = \r
- (n00.massCenterX*mass00 + n10.massCenterX*mass10 + \r
- n01.massCenterX*mass01 + n11.massCenterX*mass11)\r
- / totalMass;\r
- this.massCenterY = \r
- (n00.massCenterY*mass00 + n10.massCenterY*mass10 + \r
- n01.massCenterY*mass01 + n11.massCenterY*mass11)\r
- / totalMass;\r
- }\r
- }\r
- \r
- private static class OctreeLeaf extends OctreeNode {\r
- final Particle[] ps;\r
-\r
- public OctreeLeaf(Particle[] ps) {\r
- this.ps = ps;\r
- \r
- double massCenterX = 0.0;\r
- double massCenterY = 0.0;\r
- for(Particle p : ps) {\r
- massCenterX += p.x;\r
- massCenterY += p.y;\r
- } \r
- \r
- this.mass = ps.length;\r
- this.massCenterX = massCenterX / ps.length;\r
- this.massCenterY = massCenterY / ps.length;\r
- }\r
- }\r
- \r
- private static OctreeNode constructOctree(double minX, double minY, double maxX, double maxY,\r
- ArrayList<Particle> ps) {\r
- if(ps.size() < OCTREE_LEAF_SIZE)\r
- return new OctreeLeaf(ps.toArray(new Particle[ps.size()]));\r
- \r
- double midX = 0.5 * (minX + maxX);\r
- double midY = 0.5 * (minY + maxY);\r
- \r
- ArrayList<Particle> ps00 = new ArrayList<Particle>();\r
- ArrayList<Particle> ps10 = new ArrayList<Particle>();\r
- ArrayList<Particle> ps01 = new ArrayList<Particle>();\r
- ArrayList<Particle> ps11 = new ArrayList<Particle>();\r
- \r
- for(Particle p : ps) {\r
- double x = p.x;\r
- double y = p.y;\r
- if(x < midX) {\r
- if(y < midY)\r
- ps00.add(p);\r
- else\r
- ps01.add(p);\r
- }\r
- else {\r
- if(y < midY)\r
- ps10.add(p);\r
- else\r
- ps11.add(p);\r
- }\r
- }\r
- \r
- return new OctreeInnerNode(\r
- constructOctree(minX, minY, midX, midY, ps00),\r
- constructOctree(midX, minY, maxX, midY, ps10),\r
- constructOctree(minX, midY, midX, maxY, ps01),\r
- constructOctree(midX, midY, maxX, maxY, ps11)\r
- ); \r
- }\r
- \r
- static class Bounds {\r
- final double minX;\r
- final double minY;\r
- final double maxX;\r
- final double maxY;\r
- \r
- public Bounds(double minX, double minY, double maxX, double maxY) {\r
- this.minX = minX;\r
- this.minY = minY;\r
- this.maxX = maxX;\r
- this.maxY = maxY;\r
- }\r
- }\r
- \r
- private static Bounds computeOctreeBounds(ArrayList<Particle> ps) {\r
- Iterator<Particle> it = ps.iterator();\r
- \r
- Particle pFirst = it.next(); \r
- \r
- double minX = pFirst.x;\r
- double minY = pFirst.y;\r
- double maxX = pFirst.x;\r
- double maxY = pFirst.y;\r
- \r
- while(it.hasNext()) {\r
- Particle p = it.next();\r
- double x = p.x;\r
- double y = p.y;\r
- if(x < minX)\r
- minX = x;\r
- else if(x > maxX)\r
- maxX = x;\r
- if(y < minY)\r
- minY = y;\r
- else if(y > maxY)\r
- maxY = y;\r
- }\r
- \r
- double diff = (maxX - minX) - (maxY - minY);\r
- diff *= 0.5;\r
- if(diff > 0.0) {\r
- minY -= diff;\r
- maxY += diff;\r
- }\r
- else {\r
- minX += diff;\r
- maxX -= diff; \r
- }\r
- return new Bounds(minX, minY, maxX, maxY);\r
- }\r
-\r
- private static void computeForce(OctreeNode octree,\r
- ArrayList<OctreeNode> nearNodes, ArrayList<OctreeNode> farNodes) {\r
- // TODO Auto-generated method stub\r
- \r
- }\r
- \r
- public static void computeRepulsiveForces(ArrayList<Particle> ps) {\r
- Bounds bounds = computeOctreeBounds(ps); \r
- OctreeNode octree = constructOctree(bounds.minX, bounds.minY, bounds.maxX, bounds.maxY, ps); \r
- computeForce(octree, new ArrayList<OctreeNode>(), new ArrayList<OctreeNode>());\r
- }\r
-}\r
+package org.simantics.debug.graphical.layout;
+
+import java.util.ArrayList;
+import java.util.Iterator;
+
+public class BarnesHut2 {
+
+ static final double OPTIMAL_DISTANCE = 150.0;
+ static final double C = 0.1;
+ static final double K = C / OPTIMAL_DISTANCE;
+ static final double G = K;
+ static final double Q = C * OPTIMAL_DISTANCE * OPTIMAL_DISTANCE;
+
+ public static final int OCTREE_LEAF_SIZE = 25;
+
+ public static void applyDirectedForce(Particle a, Particle b) {
+ double dx = a.x - b.x;
+ double dy = a.y - b.y;
+ double l2 = dx*dx + dy*dy;
+ double s = Q / l2;
+ a.fx += s * dx;
+ a.fy += s * dy;
+ }
+
+ public static void applyDirectedForce(Particle a, OctreeNode b) {
+ double dx = a.x - b.massCenterX;
+ double dy = a.y - b.massCenterY;
+ double l2 = dx*dx + dy*dy;
+ double s = Q * b.mass / l2;
+ a.fx += s * dx;
+ a.fy += s * dy;
+ }
+
+ private static abstract class OctreeNode {
+ double mass;
+ double massCenterX;
+ double massCenterY;
+ }
+
+ private static class OctreeInnerNode extends OctreeNode {
+ final OctreeNode n00;
+ final OctreeNode n10;
+ final OctreeNode n01;
+ final OctreeNode n11;
+
+ public OctreeInnerNode(OctreeNode n00, OctreeNode n10, OctreeNode n01, OctreeNode n11) {
+ this.n00 = n00;
+ this.n10 = n10;
+ this.n01 = n01;
+ this.n11 = n11;
+
+ double mass00 = n00.mass;
+ double mass10 = n10.mass;
+ double mass01 = n01.mass;
+ double mass11 = n11.mass;
+ double totalMass = mass00 + mass10 + mass01 + mass11;
+
+ this.mass = totalMass;
+ this.massCenterX =
+ (n00.massCenterX*mass00 + n10.massCenterX*mass10 +
+ n01.massCenterX*mass01 + n11.massCenterX*mass11)
+ / totalMass;
+ this.massCenterY =
+ (n00.massCenterY*mass00 + n10.massCenterY*mass10 +
+ n01.massCenterY*mass01 + n11.massCenterY*mass11)
+ / totalMass;
+ }
+ }
+
+ private static class OctreeLeaf extends OctreeNode {
+ final Particle[] ps;
+
+ public OctreeLeaf(Particle[] ps) {
+ this.ps = ps;
+
+ double massCenterX = 0.0;
+ double massCenterY = 0.0;
+ for(Particle p : ps) {
+ massCenterX += p.x;
+ massCenterY += p.y;
+ }
+
+ this.mass = ps.length;
+ this.massCenterX = massCenterX / ps.length;
+ this.massCenterY = massCenterY / ps.length;
+ }
+ }
+
+ private static OctreeNode constructOctree(double minX, double minY, double maxX, double maxY,
+ ArrayList<Particle> ps) {
+ if(ps.size() < OCTREE_LEAF_SIZE)
+ return new OctreeLeaf(ps.toArray(new Particle[ps.size()]));
+
+ double midX = 0.5 * (minX + maxX);
+ double midY = 0.5 * (minY + maxY);
+
+ ArrayList<Particle> ps00 = new ArrayList<Particle>();
+ ArrayList<Particle> ps10 = new ArrayList<Particle>();
+ ArrayList<Particle> ps01 = new ArrayList<Particle>();
+ ArrayList<Particle> ps11 = new ArrayList<Particle>();
+
+ for(Particle p : ps) {
+ double x = p.x;
+ double y = p.y;
+ if(x < midX) {
+ if(y < midY)
+ ps00.add(p);
+ else
+ ps01.add(p);
+ }
+ else {
+ if(y < midY)
+ ps10.add(p);
+ else
+ ps11.add(p);
+ }
+ }
+
+ return new OctreeInnerNode(
+ constructOctree(minX, minY, midX, midY, ps00),
+ constructOctree(midX, minY, maxX, midY, ps10),
+ constructOctree(minX, midY, midX, maxY, ps01),
+ constructOctree(midX, midY, maxX, maxY, ps11)
+ );
+ }
+
+ static class Bounds {
+ final double minX;
+ final double minY;
+ final double maxX;
+ final double maxY;
+
+ public Bounds(double minX, double minY, double maxX, double maxY) {
+ this.minX = minX;
+ this.minY = minY;
+ this.maxX = maxX;
+ this.maxY = maxY;
+ }
+ }
+
+ private static Bounds computeOctreeBounds(ArrayList<Particle> ps) {
+ Iterator<Particle> it = ps.iterator();
+
+ Particle pFirst = it.next();
+
+ double minX = pFirst.x;
+ double minY = pFirst.y;
+ double maxX = pFirst.x;
+ double maxY = pFirst.y;
+
+ while(it.hasNext()) {
+ Particle p = it.next();
+ double x = p.x;
+ double y = p.y;
+ if(x < minX)
+ minX = x;
+ else if(x > maxX)
+ maxX = x;
+ if(y < minY)
+ minY = y;
+ else if(y > maxY)
+ maxY = y;
+ }
+
+ double diff = (maxX - minX) - (maxY - minY);
+ diff *= 0.5;
+ if(diff > 0.0) {
+ minY -= diff;
+ maxY += diff;
+ }
+ else {
+ minX += diff;
+ maxX -= diff;
+ }
+ return new Bounds(minX, minY, maxX, maxY);
+ }
+
+ private static void computeForce(OctreeNode octree,
+ ArrayList<OctreeNode> nearNodes, ArrayList<OctreeNode> farNodes) {
+ // TODO Auto-generated method stub
+
+ }
+
+ public static void computeRepulsiveForces(ArrayList<Particle> ps) {
+ Bounds bounds = computeOctreeBounds(ps);
+ OctreeNode octree = constructOctree(bounds.minX, bounds.minY, bounds.maxX, bounds.maxY, ps);
+ computeForce(octree, new ArrayList<OctreeNode>(), new ArrayList<OctreeNode>());
+ }
+}
Code Review / simantics / platform.git / blobdiff