R-Tree Library for Javascript

by Jon-Carlos Rivera

Released under an MIT license

This page contains examples of my R-Tree Library (rtree.js) for Javascript. The library is an open-source, high performance, and non-recursive implementation of the R-Tree data structure.

To contribute to, watch, or fork the R-Tree Library, see the project on GitHub at http://github.com/imbcmdth/RTree

Tests:

Simple Unit Tests

Preliminary unit testing examples.

Simple Playground

A simple interactive example of the R-Tree. Great for understanding R-Tree principles.

Area Effect

Generates a group of 6500 random small non-overlapping rectangles and shows the resultant tree-structure using a "heat-map".

Benchmark

Inserts 10k objects. Performs some searches. Inserts another 10k objects. Performs some searches. Deletes and reinserts some objects. Performs some final searches. Screenshot of various benchmark results
User Agent Initialize w/ 10k objects Perform 1k searches Add 10k more objects Another 1k searches
Firefox 3.7a4 pre 4471 ms 563 ms 5098 ms 908 ms
Safari (webkit r57055) 3874 ms 294 ms 4620 ms 450 ms
Opera 10.51 build 3315 1108 ms 78 ms 1260 ms 129 ms
Chrome 5.0.342.8 beta 805 ms 91 ms 904 ms 154 ms

Super-Harcore Example

ONLY run on Opera, Chrome, Safari, or Firefox 3.6 nightlies!
This test generates 20k dense non-overlapping rectangles of various size and color.