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:

• Collision detection (part 1)
• Collision detection (part 2)
• Collision detection (part 3)

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

Tiny (500 boxes)

Small (1500 boxes)

Medium (10000 boxes)

Large (250000 boxes)

Circle

Small (10000 boxes)

Large (50000 boxes)

High aspect ratio

Small (10000 boxes)

Large (100000 boxes)

2D - Bipartite

Small uniform (1500) vs Large uniform (50000)

Circle (20000) vs uniform (20000)

High aspect ratio (20000) vs uniform (20000)

Skewed (5000) vs circle (20000)

3D - Complete

Uniform

Sphere

Skewed

Bunny

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:

1. Create an adapter for the algorithm in the algorithms/ folder. At minimum, your adapter must implement two methods: exports.prepare and exports.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
2. Add an entry in the completeAlgs or bipartiteAlgs sets in bench.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.
3. 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