BarnesHutNode.java

package layout;

import java.awt.geom.Point2D;
import java.util.HashSet;
import java.util.Set;

import guiGraph.ConcurrentCoordinateNode;
import guiGraph.ConcurrentGraphWrapper;

/**
 * Barnes-Hut-Tree nodes
 * These nodes are used to generate a Barnes-Hut-Tree which allows effective and good approximation
 * of forces in n-body simulations
 * 
 * @author Robert Mader
 *
 */
class BarnesHutNode {
	
	private final Point2D.Double baseCord;	//minimal x/y value
	private final double size;		//size for square from baseCord
	
	private BarnesHutNode nw = null; //north-west child node
	private BarnesHutNode ne = null;
	private BarnesHutNode sw = null;
	private BarnesHutNode se = null;
	private ConcurrentCoordinateNode body = null;
	private final ConcurrentGraphWrapper graph;
	private Point2D.Double centerOfMass;
	private double mass = 0;
	
	//limit the recursion level so a stack overflow is avoided in bad cases
	private int maxRec = 1000;
	private final int recDepth;
	
	/**
	 * Constructor, takes the graph containing the nodes to be added, and a square in which to put the nodes
	 * @param graph
	 * @param baseCord	base coordinate
	 * @param size		how big the square is from the base coordinate (on the x and the y axis)
	 */
	BarnesHutNode(ConcurrentGraphWrapper graph, Point2D.Double baseCord, double size){
		this(graph, baseCord, size, 0);
	}
	
	BarnesHutNode(ConcurrentGraphWrapper graph, Point2D.Double baseCord, double size, int recDepth){
		this.graph = graph;
		this.baseCord = baseCord;
		this.size = size;
		this.recDepth = recDepth;
		centerOfMass = new Point2D.Double(baseCord.x + size/2, baseCord.y + size/2);
	}

	/**
	 * Is node external (a leaf) and does not contain a node?
	 * @return
	 */
	public boolean isEmpty(){
		return nw == null && body == null;
	}
	
	/**
	 * Is node a leaf?
	 * @return
	 */
	public boolean isExternal(){
		return nw == null;
	}
	
	/**
	 * Center of mass of the node (and of all child nodes)
	 * @return
	 */
	public Point2D.Double getCenterOfMass(){
		return centerOfMass;
	}
	
	/**
	 * Mass of node (and of all child nodes)
	 * @return
	 */
	public double getMass(){
		return mass;
	}
	
	/**
	 * If node contains a graph node (so it's a leaf) return it
	 * @return
	 */
	public ConcurrentCoordinateNode getBody(){
		return body;
	}
	
	/**
	 * How big is the square this node represents?
	 * @return
	 */
	public double getSize(){
		return size;
	}
	
	/**
	 * The center of the square represended by this node
	 * @return
	 */
	public Point2D.Double getCenter(){
		return new Point2D.Double(baseCord.x+size/2, baseCord.y+size/2);
	}
	
	/**
	 * Get all child nodes
	 * @return
	 */
	public Set<BarnesHutNode> getChilds(){
		Set<BarnesHutNode> set = new HashSet<BarnesHutNode>();
		if(nw != null){
			set.add(nw);
			set.add(ne);
			set.add(sw);
			set.add(se);
		}
		return set;
	}
	
	/**
	 * Initialize child nodes and readd already contained node
	 */
	private void initializeChilds(){
		mass = 0;
		centerOfMass = null;
		nw = new BarnesHutNode(graph, new Point2D.Double(baseCord.x,baseCord.y+size/2), size/2, recDepth+1);
		ne = new BarnesHutNode(graph, new Point2D.Double(baseCord.x+size/2,baseCord.y+size/2), size/2, recDepth+1);
		sw = new BarnesHutNode(graph, new Point2D.Double(baseCord.x,baseCord.y), size/2, recDepth+1);
		se = new BarnesHutNode(graph, new Point2D.Double(baseCord.x+size/2,baseCord.y), size/2, recDepth+1);
		
		
		ConcurrentCoordinateNode temp = body;
		body = null;
		addNode(temp);
	}
	
	/**
	 * Add node to tree. This function works recursively from the top of the tree.
	 * @param node
	 */
	public void addNode(ConcurrentCoordinateNode node){
		
		if(node == null) return;
		
		if(nw == null && body == null){
			body = node;
			centerOfMass = body.getCoordinates();
			
			mass = 1;
		}
		else if(nw == null){
			//if(body.getCoordinates().distance(node.getCoordinates()) > minDist){
			if(recDepth < maxRec){
				initializeChilds();
				this.addNode(node);
			}
		}
		else{
			if(centerOfMass == null){
				centerOfMass = node.getCoordinates();
			}
			else{
				centerOfMass = calcCenterOfMass(centerOfMass,mass,node.getCoordinates(),1);
			}
			
			mass += 1;
			
			if(node.getCoordinates().y > (baseCord.y + size/2)){
				if(node.getCoordinates().x <= (baseCord.x + size/2)){
					nw.addNode(node);
				}
				else{
					ne.addNode(node);
				}
			}
			else{
				if(node.getCoordinates().x <= (baseCord.x + size/2)){
					sw.addNode(node);
				}
				else{
					se.addNode(node);
				}
			}
		}
	}

	private Point2D.Double calcCenterOfMass(Point2D.Double point1, double mass1, Point2D.Double point2, double mass2) {
		
		/*
		 * center of two masses:
		 * m = m1 + m2
		 * x = (x1*m1 + x2*m2) / m
		 * y = (y1*m1 + y2*m2) / m
		 */
		
		return new Point2D.Double(	(point1.x*mass1 + point2.x*mass2)/(mass1+mass2),
							(point1.y*mass1 + point2.y*mass2)/(mass1+mass2));
	}
}