|
|
|
|
How do I tell if a tree node is internal or external? Check if all four children are null. Consider writing a helper method isExternal() to check this.
How do I calculate center-of-mass of a body with an aggregate body? Just treat the aggregate body like any other body - the center of mass formula works even if one body is already the center of mass of several other bodies.
None of the particles appear on the screen. What could I be doing wrong? Make sure that your particles are not being drawn in the same color as your background. Don't forget to call Turtle.pause. Make sure that the x and y turtle coordinates that you plot are between 0 and SIZE. Make sure that your universe quadrant is initialized properly so that (-radius, -radius) is the lower left corner and (radius, radius) is the upper right corner. Make sure that your NW(), NE(), SW(), and SE() methods are setting up the proper subquadrants.
When computing the net force acting on body b, do I need a special case to prevent calculating the force between b and an aggregate body that happens to contain b? No. If an aggregate body representing a quad of size s contains b, then the distance d from b to the center of mass will be at most sqrt(2) × s. But in this case θ = s / d > 1/2, so the algorithm would need to expand the aggregate body anyway.
Who discovered the first subquadratic algorithm for N-Body simulation? Andrew Appel discovered his algorithm while at Princeton University working on his senior thesis in the Department of Physics.
When was the Barnes-Hut algorithm discovered? It was developed in 1986 by two astrophysicists at Princeton's Institute for Advanced Study.
Can the Barnes-Hut algorithm be extended to three dimensions? Yes. You can use an oct-tree instead of a quad-tree, although there are more wasted links. Another spatial partitioning data structure called a k-d tree is also useful for two and higher dimensional problems.
Is the Barnes-Hut algorithm less accurate than the direct sum approach taken in Assignment 3? Yes, although it is still the method of choice is many scientific applications. There are some applications (e.g., tracking the orbit of the solar system over billions of years) that require very accurate calculations where Barnes-Hut would not be appropriate.
Should I worry about collisions? No.
|
|
Input. Copy the files from the directory barnes-hut into your working directory. The file test2.txt is the 5 node example from the assignment. Please note that none of the testi.txt files are intended to be animated. They are simple data sets for the purpose of testing out your Quad and BHTree methods. The files, resultsi.txt, contain string representaions of the universe Quad and of the BHTree after one loop.
Compilation and execution. The main function must be in the file NBody.java. We will compile your program with:
and execute withjavac NBody.java
We will also be compiling your BHTree, Body, and Quad files with our own version of NBody that prints out the string representation of the universe Quad and the BHTree, so make sure you include the toString methods for both of these classes. This also means that the following methods MUST agree with the ones described in the assignment or existing in the template files. (If you want to modify one of these methods, remember that in java it is OK to have more than one method with the same name as long as they have different arguments.)java NBody < input.txt
For Body
public boolean in(Quad q)
public void resetForce()
public void update(double dt)
For BHTreepublic void draw(int size, double radius)
public void insert(Body b)
public void updateForce(Body b)
|
|
readme.txt. Use the following readme file template and answer any questions.
Submission. Submit NBody.java and all of the files needed to run your program. Don't forget to hit the "Run Script" button on the submission system to test that it compiles cleanly.
|
|
These are purely suggestions for how you might make progress. You do not have to follow these steps.
BHTree object whose
body field is set to null.
This way, you can recursively call the BHTree methods
on this external node without getting a null pointer exception.
This will also simplify the methods insert and updateForce.
BHTree.java. Mark internal nodes with an asterisk.
If you implement null branches as suggested above, this code would look
something like this:
public String toString() {
if(NE != null) return "*" + body + "\n" + NW + NE + SW + SE;
else return " " + body + "\n";
}
For testing, modify NBody.java to print
only the first iteration of the simulation, then stop.
|
|