RBush 3.2.0

dotnet add package RBush --version 3.2.0
NuGet\Install-Package RBush -Version 3.2.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.2.0" />
For projects that support PackageReference, copy this XML node into the project file to reference the package.
paket add RBush --version 3.2.0
#r "nuget: RBush, 3.2.0"
#r directive can be used in F# Interactive and Polyglot Notebooks. 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.2.0

// Install RBush as a Cake Tool
#tool nuget:?package=RBush&version=3.2.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 Compatible and additional computed target framework versions.
.NET net5.0 was computed.  net5.0-windows was computed.  net6.0 is compatible.  net6.0-android was computed.  net6.0-ios was computed.  net6.0-maccatalyst was computed.  net6.0-macos was computed.  net6.0-tvos was computed.  net6.0-windows was computed.  net7.0 was computed.  net7.0-android was computed.  net7.0-ios was computed.  net7.0-maccatalyst was computed.  net7.0-macos was computed.  net7.0-tvos was computed.  net7.0-windows was computed.  net8.0 was computed.  net8.0-android was computed.  net8.0-browser was computed.  net8.0-ios was computed.  net8.0-maccatalyst was computed.  net8.0-macos was computed.  net8.0-tvos was computed.  net8.0-windows was computed. 
.NET Core netcoreapp1.0 was computed.  netcoreapp1.1 was computed.  netcoreapp2.0 was computed.  netcoreapp2.1 was computed.  netcoreapp2.2 was computed.  netcoreapp3.0 was computed.  netcoreapp3.1 is compatible. 
.NET Standard netstandard1.2 is compatible.  netstandard1.3 was computed.  netstandard1.4 was computed.  netstandard1.5 was computed.  netstandard1.6 was computed.  netstandard2.0 was computed.  netstandard2.1 was computed. 
.NET Framework net451 was computed.  net452 was computed.  net46 was computed.  net461 was computed.  net462 was computed.  net463 was computed.  net47 was computed.  net471 was computed.  net472 was computed.  net48 was computed.  net481 was computed. 
MonoAndroid monoandroid was computed. 
MonoMac monomac was computed. 
MonoTouch monotouch was computed. 
Tizen tizen30 was computed.  tizen40 was computed.  tizen60 was computed. 
Universal Windows Platform uap was computed.  uap10.0 was computed. 
Windows Phone wpa81 was computed. 
Windows Store netcore451 was computed. 
Xamarin.iOS xamarinios was computed. 
Xamarin.Mac xamarinmac was computed. 
Xamarin.TVOS xamarintvos was computed. 
Xamarin.WatchOS xamarinwatchos was computed. 
Compatible target framework(s)
Included target framework(s) (in package)
Learn more about Target Frameworks and .NET Standard.
  • .NETCoreApp 3.1

    • No dependencies.
  • .NETStandard 1.2

  • net6.0

    • No dependencies.

NuGet packages (4)

Showing the top 4 NuGet packages that depend on RBush:

Package Downloads
ClosedXML The ID prefix of this package has been reserved for one of the owners of this package by NuGet.org.

See release notes https://github.com/ClosedXML/ClosedXML/releases/tag/0.104.0-preview2 ClosedXML is a .NET library for reading, manipulating and writing Excel 2007+ (.xlsx, .xlsm) files. It aims to provide an intuitive and user-friendly interface to dealing with the underlying OpenXML API.

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 (4)

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

Repository Stars
ClosedXML/ClosedXML
ClosedXML is a .NET library for reading, manipulating and writing Excel 2007+ (.xlsx, .xlsm) files. It aims to provide an intuitive and user-friendly interface to dealing with the underlying OpenXML API.
ihm-tswow/Links-Awakening-DX-HD
Unaffiliated fork off https://linksawakeningdxhd.itch.io/links-awakening-dx-hd
Esri/arcgis-pro-sdk-community-samples
ArcGIS Pro SDK for Microsoft .NET Framework Community Samples
Kaioru/Edelstein
A v.95.1 Mushroom game server emulator written in C# .NET
Version Downloads Last updated
3.2.0 180,981 12/29/2022
3.1.0 69,685 7/13/2022
3.0.0 2,916 7/11/2022
2.0.53 3,044 5/25/2022
2.0.46 50,569 11/6/2020
2.0.41 113,751 4/18/2019
2.0.31 11,330 6/6/2018
2.0.28 4,520 3/12/2018
1.0.24 1,038 3/12/2018
1.0.20 1,018 1/15/2018
1.0.18 2,068 7/13/2017