1 package org.simantics.debug.graphical.layout;
\r
3 import java.util.ArrayList;
\r
4 import java.util.Iterator;
\r
6 public class BarnesHut2 {
\r
8 static final double OPTIMAL_DISTANCE = 150.0;
\r
9 static final double C = 0.1;
\r
10 static final double K = C / OPTIMAL_DISTANCE;
\r
11 static final double G = K;
\r
12 static final double Q = C * OPTIMAL_DISTANCE * OPTIMAL_DISTANCE;
\r
14 public static final int OCTREE_LEAF_SIZE = 25;
\r
16 public static void applyDirectedForce(Particle a, Particle b) {
\r
17 double dx = a.x - b.x;
\r
18 double dy = a.y - b.y;
\r
19 double l2 = dx*dx + dy*dy;
\r
25 public static void applyDirectedForce(Particle a, OctreeNode b) {
\r
26 double dx = a.x - b.massCenterX;
\r
27 double dy = a.y - b.massCenterY;
\r
28 double l2 = dx*dx + dy*dy;
\r
29 double s = Q * b.mass / l2;
\r
34 private static abstract class OctreeNode {
\r
40 private static class OctreeInnerNode extends OctreeNode {
\r
41 final OctreeNode n00;
\r
42 final OctreeNode n10;
\r
43 final OctreeNode n01;
\r
44 final OctreeNode n11;
\r
46 public OctreeInnerNode(OctreeNode n00, OctreeNode n10, OctreeNode n01, OctreeNode n11) {
\r
52 double mass00 = n00.mass;
\r
53 double mass10 = n10.mass;
\r
54 double mass01 = n01.mass;
\r
55 double mass11 = n11.mass;
\r
56 double totalMass = mass00 + mass10 + mass01 + mass11;
\r
58 this.mass = totalMass;
\r
60 (n00.massCenterX*mass00 + n10.massCenterX*mass10 +
\r
61 n01.massCenterX*mass01 + n11.massCenterX*mass11)
\r
64 (n00.massCenterY*mass00 + n10.massCenterY*mass10 +
\r
65 n01.massCenterY*mass01 + n11.massCenterY*mass11)
\r
70 private static class OctreeLeaf extends OctreeNode {
\r
71 final Particle[] ps;
\r
73 public OctreeLeaf(Particle[] ps) {
\r
76 double massCenterX = 0.0;
\r
77 double massCenterY = 0.0;
\r
78 for(Particle p : ps) {
\r
83 this.mass = ps.length;
\r
84 this.massCenterX = massCenterX / ps.length;
\r
85 this.massCenterY = massCenterY / ps.length;
\r
89 private static OctreeNode constructOctree(double minX, double minY, double maxX, double maxY,
\r
90 ArrayList<Particle> ps) {
\r
91 if(ps.size() < OCTREE_LEAF_SIZE)
\r
92 return new OctreeLeaf(ps.toArray(new Particle[ps.size()]));
\r
94 double midX = 0.5 * (minX + maxX);
\r
95 double midY = 0.5 * (minY + maxY);
\r
97 ArrayList<Particle> ps00 = new ArrayList<Particle>();
\r
98 ArrayList<Particle> ps10 = new ArrayList<Particle>();
\r
99 ArrayList<Particle> ps01 = new ArrayList<Particle>();
\r
100 ArrayList<Particle> ps11 = new ArrayList<Particle>();
\r
102 for(Particle p : ps) {
\r
119 return new OctreeInnerNode(
\r
120 constructOctree(minX, minY, midX, midY, ps00),
\r
121 constructOctree(midX, minY, maxX, midY, ps10),
\r
122 constructOctree(minX, midY, midX, maxY, ps01),
\r
123 constructOctree(midX, midY, maxX, maxY, ps11)
\r
127 static class Bounds {
\r
133 public Bounds(double minX, double minY, double maxX, double maxY) {
\r
141 private static Bounds computeOctreeBounds(ArrayList<Particle> ps) {
\r
142 Iterator<Particle> it = ps.iterator();
\r
144 Particle pFirst = it.next();
\r
146 double minX = pFirst.x;
\r
147 double minY = pFirst.y;
\r
148 double maxX = pFirst.x;
\r
149 double maxY = pFirst.y;
\r
151 while(it.hasNext()) {
\r
152 Particle p = it.next();
\r
165 double diff = (maxX - minX) - (maxY - minY);
\r
175 return new Bounds(minX, minY, maxX, maxY);
\r
178 private static void computeForce(OctreeNode octree,
\r
179 ArrayList<OctreeNode> nearNodes, ArrayList<OctreeNode> farNodes) {
\r
180 // TODO Auto-generated method stub
\r
184 public static void computeRepulsiveForces(ArrayList<Particle> ps) {
\r
185 Bounds bounds = computeOctreeBounds(ps);
\r
186 OctreeNode octree = constructOctree(bounds.minX, bounds.minY, bounds.maxX, bounds.maxY, ps);
\r
187 computeForce(octree, new ArrayList<OctreeNode>(), new ArrayList<OctreeNode>());
\r