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:
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 ✓Figures courtesy of plot.ly! Click on the images to get interactive plots
Small uniform (1500) vs Large uniform (50000) Circle (20000) vs uniform (20000) High aspect ratio (20000) vs uniform (20000) Skewed (5000) vs circle (20000)First, you will need to have npm installed and git. Clone this repo, go into the directory where it is located and then type:
To pull in all the files locally. If you have node.js installed, you can then do,
Or if you are using iojs,
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!
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"
}
Improvements to these benchmarks are always welcome.
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
To add a new algorithm to the suite, there are 3 things you need to do:
algorithms/ folder. At minimum, your adapter must implement two methods: exports.prepare and exports.run.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 rectanglescompleteAlgs 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.You can run your test cases using the run.js command.
(c) 2015 Mikola Lysenko. MIT License
RetroSearch is an open source project built by @garambo | Open a GitHub Issue
Search and Browse the WWW like it's 1997 | Search results from DuckDuckGo
HTML:
3.2
| Encoding:
UTF-8
| Version:
0.7.4