RBush 3.1.0

.NET 6.0 .NET Core 3.1 .NET Standard 1.2
dotnet add package RBush --version 3.1.0
NuGet\Install-Package RBush -Version 3.1.0
This command is intended to be used within the Package Manager Console in Visual Studio, as it uses the NuGet module's version of Install-Package.
<PackageReference Include="RBush" Version="3.1.0" />
For projects that support PackageReference, copy this XML node into the project file to reference the package.
paket add RBush --version 3.1.0
#r "nuget: RBush, 3.1.0"
#r directive can be used in F# Interactive, C# scripting and .NET Interactive. Copy this into the interactive tool or source code of the script to reference the package.
// Install RBush as a Cake Addin
#addin nuget:?package=RBush&version=3.1.0

// Install RBush as a Cake Tool
#tool nuget:?package=RBush&version=3.1.0

RBush

RBush is a high-performance .NET library for 2D spatial indexing of points and rectangles. It's based on an optimized R-tree data structure with bulk insertion support.

Spatial index is a special data structure for points and rectangles that allows you to perform queries like "all items within this bounding box" very efficiently (e.g. hundreds of times faster than looping over all items). It's most commonly used in maps and data visualizations.

This code has been copied over from the Javascript RBush library.

Build status License

Install

Install with Nuget (Install-Package RBush).

Usage

Creating a Tree

First, define the data item class to implement ISpatialData. Then the class can be used as such:

class Point : ISpatialData
{
  public Point(Envelope envelope) =>
    _envelope = envelope;
  private readonly Envelope _envelope;
  public public ref readonly Envelope Envelope => _envelope;
}

var tree = new RBush<Point>()

An optional argument (maxEntries) to the constructor defines the maximum number of entries in a tree node. 9 (used by default) is a reasonable choice for most applications. Higher value means faster insertion and slower search, and vice versa.

var tree = new RBush<Point>(maxEntries: 16)

Adding Data

Insert an item:

var item = new Point(
  new Envelope(
    MinX: 0,
    MinY: 0,
    MaxX: 0,
    MaxY: 0));
tree.Insert(item);

Bulk-Inserting Data

Bulk-insert the given data into the tree:

var points = new List<Point>();
tree.BulkLoad(points);

Bulk insertion is usually ~2-3 times faster than inserting items one by one. After bulk loading (bulk insertion into an empty tree), subsequent query performance is also ~20-30% better.

Note that when you do bulk insertion into an existing tree, it bulk-loads the given data into a separate tree and inserts the smaller tree into the larger tree. This means that bulk insertion works very well for clustered data (where items in one update are close to each other), but makes query performance worse if the data is scattered.

var result = tree.Search(
    new Envelope
    (
        minX: 40,
        minY: 20,
        maxX: 80,
        maxY: 70
    );

Returns an IEnumerable<T> of data items (points or rectangles) that the given bounding box intersects.

var allItems = tree.Search();

Returns all items of the tree.

Removing Data

Remove a previously inserted item:
tree.Delete(item);

Unless provided an IComparer<T>, RBush uses EqualityComparer<T>.Default to select the item. If the item being passed in is not the same reference value, ensure that the class supports EqualityComparer<T>.Default equality testing.

Remove all items:
tree.Clear();

Credit

This code was adapted from a Javascript library called RBush. The only changes made were to adapt coding styles and preferences.

Algorithms Used

  • single insertion: non-recursive R-tree insertion with overlap minimizing split routine from R*-tree (split is very effective in JS, while other R*-tree modifications like reinsertion on overflow and overlap minimizing subtree search are too slow and not worth it)
  • single deletion: non-recursive R-tree deletion using depth-first tree traversal with free-at-empty strategy (entries in underflowed nodes are not reinserted, instead underflowed nodes are kept in the tree and deleted only when empty, which is a good compromise of query vs removal performance)
  • bulk loading: OMT algorithm (Overlap Minimizing Top-down Bulk Loading) combined with Floyd�Rivest selection algorithm
  • bulk insertion: STLT algorithm (Small-Tree-Large-Tree)
  • search: standard non-recursive R-tree search

Papers

Development

Clone the repository and open RBush.sln in Visual Studio.

Compatibility

RBush should run on any .NET system that supports .NET Standard 1.2 (.NET Framework 4.5.1 or later; .NET Core 1.0 or later).

Product Versions
.NET net5.0 net5.0-windows net6.0 net6.0-android net6.0-ios net6.0-maccatalyst net6.0-macos net6.0-tvos net6.0-windows net7.0 net7.0-android net7.0-ios net7.0-maccatalyst net7.0-macos net7.0-tvos net7.0-windows
.NET Core netcoreapp1.0 netcoreapp1.1 netcoreapp2.0 netcoreapp2.1 netcoreapp2.2 netcoreapp3.0 netcoreapp3.1
.NET Standard netstandard1.2 netstandard1.3 netstandard1.4 netstandard1.5 netstandard1.6 netstandard2.0 netstandard2.1
.NET Framework net451 net452 net46 net461 net462 net463 net47 net471 net472 net48
MonoAndroid monoandroid
MonoMac monomac
MonoTouch monotouch
Tizen tizen30 tizen40 tizen60
Universal Windows Platform uap uap10.0
Windows Phone wpa81
Windows Store netcore451
Xamarin.iOS xamarinios
Xamarin.Mac xamarinmac
Xamarin.TVOS xamarintvos
Xamarin.WatchOS xamarinwatchos
Compatible target framework(s)
Additional computed target framework(s)
Learn more about Target Frameworks and .NET Standard.
  • .NETCoreApp 3.1

    • No dependencies.
  • .NETStandard 1.2

  • net6.0

    • No dependencies.

NuGet packages (3)

Showing the top 3 NuGet packages that depend on RBush:

Package Downloads
SlipeServer.Server

C# Server for MTA San Andreas

Boerman.FlightAnalysis

The Boerman.FlightAnalysis package contains algorithms to analyze flight movements and extract information like departure time and airfield, arrival time and airfield, total air time and more.

Dbscan.RBush

Boilerplate code to connect RBush with Dbscan.

GitHub repositories (1)

Showing the top 1 popular GitHub repositories that depend on RBush:

Repository Stars
Esri/arcgis-pro-sdk-community-samples
ArcGIS Pro SDK for Microsoft .NET Framework Community Samples
Version Downloads Last updated
3.1.0 5,075 7/13/2022
3.0.0 343 7/11/2022
2.0.53 1,330 5/25/2022
2.0.46 20,477 11/6/2020
2.0.41 70,286 4/18/2019
2.0.31 5,766 6/6/2018
2.0.28 4,018 3/12/2018
1.0.24 848 3/12/2018
1.0.20 863 1/15/2018
1.0.18 1,445 7/13/2017