Awesome
THE GREAT JAVASCRIPT BOX INTERSECTION BENCHMARK
The goal of this benchmark is to compare different solutions for finding all intersections amongst a set of boxes. An overview of this problem and this procedure can be found in the following blog posts:
Libraries surveyed
Library | Algorithms implemented | Dimensions | Bipartite |
---|---|---|---|
None | Brute force | Any | ✓ |
box-intersect | Streaming segment trees | Any | ✓ |
rbush | BVH | 2 | ✓ |
p2.js | Brute force, sweep and prune, grid | 2 | |
jsts | BVH, hierarchical grid | 2 | ✓ |
rtree | BVH | 2 | ✓ |
simple-quadtree | Hierarchical grid | 2 | ✓ |
oimo | Brute force, BVH, sweep and prune | 3 | |
box2d | Sweep and prune | 2 | |
lazykdtree | BVH | Any | ✓ |
Results
Figures courtesy of plot.ly! Click on the images to get interactive plots
2D - Complete
Uniform
<img src="https://mikolalysenko.github.io/box-intersect-benchmark/images/uniform.png">Tiny (500 boxes)
<img src="https://plot.ly/~MikolaLysenko/124/image.svg">
Small (1500 boxes)
<img src="https://plot.ly/~MikolaLysenko/125/image.svg">
Medium (10000 boxes)
<img src="https://plot.ly/~MikolaLysenko/127/image.svg">
Large (250000 boxes)
<img src="https://plot.ly/~MikolaLysenko/129/image.svg">
Circle
<img src="https://mikolalysenko.github.io/box-intersect-benchmark/images/sphere.png">Small (10000 boxes)
<img src="https://plot.ly/~MikolaLysenko/130/image.svg">
Large (50000 boxes)
<img src="https://plot.ly/~MikolaLysenko/131/image.svg">
High aspect ratio
<img src="https://mikolalysenko.github.io/box-intersect-benchmark/images/skewed.png">Small (10000 boxes)
<img src="https://plot.ly/~MikolaLysenko/132/image.svg">
Large (100000 boxes)
<img src="https://plot.ly/~MikolaLysenko/139/image.svg">
2D - Bipartite
Small uniform (1500) vs Large uniform (50000)
<img src="https://plot.ly/~MikolaLysenko/147/image.svg">
Circle (20000) vs uniform (20000)
<img src="https://plot.ly/~MikolaLysenko/148/image.svg">
High aspect ratio (20000) vs uniform (20000)
<img src="https://plot.ly/~MikolaLysenko/150/image.svg">
Skewed (5000) vs circle (20000)
<img src="https://plot.ly/~MikolaLysenko/151/image.svg">
3D - Complete
Uniform
<img src="https://plot.ly/~MikolaLysenko/152/image.svg">
Sphere
<img src="https://plot.ly/~MikolaLysenko/153/image.svg">
Skewed
<img src="https://plot.ly/~MikolaLysenko/154/image.svg">
Bunny
<img src="https://plot.ly/~MikolaLysenko/155/image.svg">
Running the benchmark
In node.js/iojs
First, you will need to have npm installed and git. Clone this repo, go into the directory where it is located and then type:
npm install
To pull in all the files locally. If you have node.js installed, you can then do,
node run
Or if you are using iojs,
iojs run
You can run specific cases by specifying them on the command line. For example, to run the tiny benchmark do:
node run cases/uniform2d-tiny-complete.json
If you want to run the whole suite at once, you can run one of the following npm scripts:
npm run complete2
npm run bipartite2
npm run complete3
npm run bipartite3
These take some time to run so be patient!
Setting up plot.ly (optional)
If you want to make charts to go along with your data, you will need to create an account and get an API key with plot.ly. Once you've done this, save your credentials to the file plotly.json
in the root directory of the folder (note this is not tracked in git). The contents of the JSON file should look something like:
{
"username": "Node.js-Demo-Account",
"key": "dvlqkmw0zm"
}
Contributing
Improvements to these benchmarks are always welcome.
Adding more test data
To create a new generator, you can create a module in the generators/
folder and add a reference to it in the distributions object in the bench.js
file. You can also create new test cases by modifying the JSON configuration files in the cases/
folder. The cases which are run
Adding an algorithm
To add a new algorithm to the suite, there are 3 things you need to do:
- Create an adapter for the algorithm in the
algorithms/
folder. At minimum, your adapter must implement two methods:exports.prepare
andexports.run
.
a.prepare
should translate the input boxes into whatever data format your algorithm requires (ie if you have some custom AABB type, then do these conversions here so you aren't penalized by them) a.run
should execute your algorithm and return the total number of overlapping rectangles - Add an entry in the
completeAlgs
orbipartiteAlgs
sets inbench.js
. If your algorithm only supports one of these modes of entry (for example only complete intersections), then you don't have to add it to both tables. - Add your algorithm to the relevant test cases.
You can run your test cases using the run.js
command.
License
(c) 2015 Mikola Lysenko. MIT License