Implementing the Barnes-Hut Algorithm: A Quadrant Class

In the Introduction we talked about an object called a Barnes-Hut tree. This is one of two additional parts to the Barnes-Hut algorithm. The other is the concept of a quadrant (in 2D) or an octant (in 3D). For coding simplicity, we will create a quadrant-based Barnes-Hut tree. It is not difficult to add additional nodes if need be.

To create a quadrant object, the code goes as follows (again, comments preceded by //):

Quad.java

 //A quadrant object that can self-subdivide. Important for creating a Barnes-Hut tree, since it holds quadrants.

public class Quad {
  
  private double xmid, ymid, length;
  //Create a square quadrant with a given length and midpoints (xmid,ymid)
  public Quad(double xmid, double ymid, double length) {
    this.xmid=xmid;
    this.ymid=ymid; 
    this.length=length;
  }
  
  //How long is this quadrant?
  public double length() {
    return length;
  }
  
  //Check if the current quadrant contains a point
  public boolean contains(double xmid, double ymid) {
    if (xmid<=this.xmid+this.length/2.0 && xmid>=this.xmid-this.length/2.0 && ymid<=this.ymid+this.length/2.0 && ymid>=this.ymid-this.length/2.0) {
      return true;
    }
    else {
      return false;
    }
  }
  //Create subdivisions of the current quadrant
  
  // Subdivision: Northwest quadrant
  public Quad NW() {
    Quad newquad = new Quad(this.xmid-this.length/4.0, this.ymid+this.length/4.0,this.length/2.0);
    return newquad;
  }
  
  // Subdivision: Northeast quadrant
  public Quad NE() {
    Quad newquad = new Quad(this.xmid+this.length/4.0, this.ymid+this.length/4.0,this.length/2.0);
    return newquad;
  }
  
  // Subdivision: Southwest quadrant
  public Quad SW() {
    Quad newquad = new Quad(this.xmid-this.length/4.0, this.ymid-this.length/4.0,this.length/2.0);
    return newquad;
  }
  
  // Subdivision: Southeast quadrant
  public Quad SE() {
    Quad newquad = new Quad(this.xmid+this.length/4.0, this.ymid-this.length/4.0,this.length/2.0);
    return newquad;
  }
  
}
One more thing that is useful to update now is the Body class so we can check if the body is in a certain quadrant. To do this, all we have to do is add the following method, which takes advantage of the methods we just defined in the Quad class.

public boolean in(Quad q) {
    return q.contains(this.rx,this.ry);
  }
}

Now we have a data structure to hold Bodies, but what we really need is the Barnes-Hut tree that hold quadrants and contain information about the bodies they contain. The next section will do just that.