--- /dev/null
+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
Code Review / simantics / platform.git / blobdiff