Skip to content

A Python implementation of the Barnes-Hut algorithm with a simulation of collision of two point clouds.

License

Notifications You must be signed in to change notification settings

alessialin/BarnesHut-py

Folders and files

NameName
Last commit message
Last commit date

Latest commit

 

History

70 Commits
 
 
 
 
 
 
 
 
 
 
 
 
 
 

Repository files navigation

Barnes-Hut Algorithm

The Barnes-Hut Algorithm1 is an approximation algorithm solving the N-Body Problem.

It is notable for having order O(N log N) compared to a direct sum - Brute Force - algorithm which would be O(N^2). The crucial idea is that it groups nearby bodies and approximates them as a single body. If the cluster is sufficiently far away, we can approximate its gravitational effect using its center of mass.

Quickstart

  • In order to run this in your local machine:
> git clone https://github.com/alessialin/BarnesHut-py.git
> cd BarnesHut-py
> pip install -r requirements.txt

NB. I'd suggest setting up a virtual environment beforehand to avoid polluting your machine's modules system.

  • To run the Barnes-Hut simulation:
> python3 ./src/BarnesHut-py.py

Files Structure

├── evaluation
│   └── BarnesHut_evaluation.py
|   └── BruteForce_evaluation.py
│   └── comparison.py
├── output
│   └── benchmark
|   │   └── BarnesHut_time.png
|   │   └── BruteForce_time.png
|   │   └── Comparison_time.png
│   └── BH_GalaxyCollision_800_v[x].mp4
│   └── BH_GalaxySimulation_800_v[x].mp4
│   └── BH_Quad.png
├── src
|   └── BarnesHut.py
|   └── body.py
│   └── node.py
│   └── quadtree_example.py
│   └── quadtree.py
│   └── utils.py
├── .gitignore
├── LICENSE
├── README.md
└── requirements.txt

Simulation

BH_GalaxyCollision_800_v0.mp4

Resources

Barnes, J., & Hut, P. (1986). A hierarchical O (N log N) force-calculation algorithm. Nature, 324(6096), 446-449.
Wikipedia
Galaxy Simulator
Princeton CS126
The Barnes-Hut Approximation

Footnotes

  1. The purpose of this repository is for the final submission of the course of 20602 COMPUTER SCIENCE (ALGORITHMS) at Bocconi University.

About

A Python implementation of the Barnes-Hut algorithm with a simulation of collision of two point clouds.

Topics

Resources

License

Stars

Watchers

Forks

Releases

No releases published

Packages

No packages published

Languages