C# port of the fast static 2d spatial index Flatbush (https://github.com/mourner/flatbush/)
MIT License
C# port of the fast static 2d spatial index Flatbush in javascript, check it out here.
Implementation is a packed Hilbert R-tree.
This structure is useful for computational geometry algorithms, e.g. finding all intersections between two arbitrary curves (mapping segments to bounding boxes), hit testing, 2d bounding box selections, etc.
Currently does not support k nearest neighbors query (which is implemented in the javascript version utilizing a priority queue). I added an additional method to use a visiting function which allows for stopping the query early and does not require having to return the index results.
Currently only supports signed int32 indexes and doubles for bounding box extents.
Ideas and contributions are welcome. Tests and benchmarks need to be added.
https://www.nuget.org/packages/Flatbush/
Install-Package Flatbush
See SpatialIndex class methods and example code below.
using Flatbush;
// Create a new spatial index to hold 5 boxes
var spatialIndex = new SpatialIndex(5);
spatialIndex.Add(-1.1, -1.1, 1.1, 1.1); // index 0
spatialIndex.Add(-5.2, -5.3, 5.4, 5.5); // index 1
spatialIndex.Add(-5.2, -5.3, 1.4, 1.5); // index 2
spatialIndex.Add(1.7, 1.6, 2.2, 5.0); // index 3
spatialIndex.Add(9.9, 10.1, 20.2, 20.9); // index 4
// Done adding items, build the index
spatialIndex.Finish();
// Query all boxes (results are integer indices) that overlap a point at 0,0
var results = spatialIndex.Query(0, 0, 0, 0);
// Prints the set [0, 1, 2] (order not defined)
foreach (var i in results)
{
Console.Write(i);
}
// Same as previous query (point at 0,0) but index 1 will not be included
results = spatialIndex.Query(0, 0, 0, 0, i => i != 1);
foreach (var i in results)
{
Console.Write(i);
}
// Visit all query results with a function rather than having a list of indices returned
// Querying results that intersect/overlap with the bounding box defined by
// (MinX = 12, MinY = 12, MaxX = 15, MaxY = 15)
spatialIndex.VisitQuery(12, 12, 15, 15, i =>
{
Console.Write(i);
// We return true to visit all the results (stops query early when return is false)
return true;
});
int visited = 0;
spatialIndex.VisitQuery(0, 0, 0, 0, i =>
{
Console.Write(i);
visited += 1;
// Visit only the first two results
return visited < 2;
});