viceroypenguin / rbush Goto Github PK

R-Tree Implementation for C#

License: MIT License

C# 100.00%

spatial-index data-structures algorithm r-tree

rbush's Introduction

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.

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.

Search

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).

rbush's People

Contributors

Stargazers

Watchers

rbush's Issues

tree traversal

Hi, Is there currently a way to traverse the tree as with the original RBush

Signed assemblies

I would like to have signed assemblies in the nuget package. Is it something that would be considered?

I am fine with making a PR, probably using this guide (the maintainer would need to generate their own secret key though).

Is it possible to use structs?

Trying to implement this in an ecs system (DefaultEcs) and I can't find a way to implement ISpatialData in a struct.

A Question about Insert

Does the RBush.Insert() function detect if there is duplicates? If so, what does it do when it finds a duplicate?

Thanks!

Strong name the NuGet build

Hi - sorry if this is the wrong venue for this.

I'd like to use this package in an application I am developing. Installed the NuGet package via Visual Studio.

However, the assembly does not have a strong name. Since the rest of my application is strong named due to security requirements, I cannot load RBush without cloning the repo and compiling it myself.

This isn't a bug, but it is a request to strong name the NuGet package

Adding/removing single item fails

I added the following test to reproduce this issue:

The following test fails

		[Fact]
		public void VeriftyAddOneRemoveOne()
		{
			var tree = new RBush<Point>();
			var p1 = new Point(1, 1, 1, 1);
			tree.Insert(p1);
			tree.Delete(p1);
		}

The following test will pass

		[Fact]
		public void VeriftyAddTwoRemoveOne()
		{
			var tree = new RBush<Point>();
			var p1 = new Point(1, 1, 1, 1);
			var p2 = new Point(2, 2, 2, 2);
			tree.Insert(p1);
			tree.Insert(p2);
			tree.Delete(p1);
		}

Optimizing unique insert

I need an R-Tree that doesn't allow duplicates (I don't care if overwrite the last one, or just ignore the new one).

Right now I'm checking if the element exists, and then add it if it doesn't:

List<Point> points = new List<Point>();
...
if (!this.blockCache.Search(point.Envelope).Any()) points.Add(point);
...
this.blockCache.BulkLoad(points);

Is there any way to make it more optimal, besides reducing the rtreeEntries size?

Bug in Insert

Hi,

I found a very strange bug when using Insert. In the code below if I insert all the Points one by one, then search for those containing a specific area (there are 5 Point instances that contain the requested area), the number of found rectangles in 0

However if I do the same and do bulk load instead of insert, suddenly all 5 areas are found


[TestClass]
public class UnitTest1
{

    private class Point : ISpatialData, IComparable<Point>
    {
        private Envelope _envelope;

        public Point(double minX, double minY, double maxX, double maxY)
        {
            _envelope = new Envelope(
                minX: minX,
                minY: minY,
                maxX: maxX,
                maxY: maxY);
        }

        public ref readonly Envelope Envelope => ref _envelope;

        public int CompareTo(Point other)
        {
            if (this.Envelope.MinX != other.Envelope.MinX)
                return this.Envelope.MinX.CompareTo(other.Envelope.MinX);
            if (this.Envelope.MinY != other.Envelope.MinY)
                return this.Envelope.MinY.CompareTo(other.Envelope.MinY);
            if (this.Envelope.MaxX != other.Envelope.MaxX)
                return this.Envelope.MaxX.CompareTo(other.Envelope.MaxX);
            if (this.Envelope.MaxY != other.Envelope.MaxY)
                return this.Envelope.MaxY.CompareTo(other.Envelope.MaxY);
            return 0;
        }
    }


    [TestMethod]
    public void TestInsert()
    {
        RBush<Point> tree = new RBush<Point>();
        tree.Insert(new Point(minX: 35.0457204123358, maxY: 31.7658263429689, maxX: 35.1736414417038, minY: 31.5946330633669));
        tree.Insert(new Point(minX: 35.0011136524732, maxY: 31.6763344627552, maxX: 35.0119650302309, minY: 31.6701999643473));
        tree.Insert(new Point(minX: 35.4519996266397, maxY: 33.2873426178667, maxX: 35.6225745715679, minY: 33.0521061332025));
        tree.Insert(new Point(minX: 35.3963660077949, maxY: 32.6939307443726, maxX: 35.609059834246, minY: 31.9833569998672));
        tree.Insert(new Point(minX: 34.8283506083251, maxY: 32.3931011267767, maxX: 35.074434567496, minY: 32.2548085664601));
        tree.Insert(new Point(minX: 34.8331658736056, maxY: 32.0096644072503, maxX: 35.0591449537042, minY: 31.7799489556277));
        tree.Insert(new Point(minX: 35.4232929081405, maxY: 33.0831804221654, maxX: 35.6402606700131, minY: 32.8928176841194));
        tree.Insert(new Point(minX: 35.1547685550823, maxY: 32.8357311630527, maxX: 35.3829851953318, minY: 32.6409460084027));
        tree.Insert(new Point(minX: 34.8921664127959, maxY: 31.7780322047787, maxX: 35.0343017543245, minY: 31.6053844677954));
        tree.Insert(new Point(minX: 34.9263969975396, maxY: 32.8432505478028, maxX: 35.1011727083577, minY: 32.65352493197));
        tree.Insert(new Point(minX: 35.2394825164923, maxY: 31.8621074757081, maxX: 35.2967869133878, minY: 31.8026823309661));
        tree.Insert(new Point(minX: 35.3717873599347, maxY: 33.1679615668549, maxX: 35.6478183130483, minY: 32.9175807550062));
        tree.Insert(new Point(minX: 35.196978533143, maxY: 32.3029676465732, maxX: 35.6432919646234, minY: 31.5634195882077));
        tree.Insert(new Point(minX: 35.0004845245009, maxY: 31.8400308568811, maxX: 35.1719739039302, minY: 31.7630003816153));
        tree.Insert(new Point(minX: 34.280847167853, maxY: 31.5639320874003, maxX: 34.8906355571353, minY: 31.0494793743498));
        tree.Insert(new Point(minX: 34.6095401534748, maxY: 31.9217629772612, maxX: 34.9053153865301, minY: 31.7162092103111));
        tree.Insert(new Point(minX: 34.836714064777, maxY: 32.2220684750668, maxX: 34.9971028731628, minY: 32.1214817541366));
        tree.Insert(new Point(minX: 34.8718260788802, maxY: 31.8420049154987, maxX: 35.0378162094246, minY: 31.599197115334));
        tree.Insert(new Point(minX: 35.1186400639205, maxY: 31.8937001264381, maxX: 35.1868012907541, minY: 31.8691974363715));
        tree.Insert(new Point(minX: 34.7893345961988, maxY: 32.2478719368633, maxX: 34.8912984464358, minY: 32.1180328589326));
        tree.Insert(new Point(minX: 35.0560255797127, maxY: 32.8736600563471, maxX: 35.2038027609729, minY: 32.6886762251772));
        tree.Insert(new Point(minX: 34.5118108403562, maxY: 31.7778320509551, maxX: 35.034306207294, minY: 31.482226934431));
        tree.Insert(new Point(minX: 34.7421834416939, maxY: 32.1466473164001, maxX: 34.8522596224097, minY: 32.0294016078206));
        tree.Insert(new Point(minX: 35.2850369921205, maxY: 31.8582696930051, maxX: 35.3671187142204, minY: 31.736701022482));
        tree.Insert(new Point(minX: 34.3920880329569, maxY: 30.9730153115276, maxX: 35.2259162784014, minY: 30.3321812616403));
        tree.Insert(new Point(minX: 34.3430710039186, maxY: 31.4431220155161, maxX: 35.3548545278468, minY: 30.9079503533306));
        tree.Insert(new Point(minX: 34.6081103075024, maxY: 32.1534717814552, maxX: 35.1015149543026, minY: 31.5923121167122));
        tree.Insert(new Point(minX: 34.7988787882969, maxY: 32.1086750906882, maxX: 34.9092712663857, minY: 32.0164071891458));
        tree.Insert(new Point(minX: 34.9359618915959, maxY: 32.283413702632, maxX: 35.0574178548968, minY: 32.172467059147));
        tree.Insert(new Point(minX: 34.8656317039855, maxY: 32.5522748453893, maxX: 35.0578412581373, minY: 32.3738879752974));
        tree.Insert(new Point(minX: 35.3422616609697, maxY: 33.2954674685247, maxX: 35.8977567880068, minY: 32.9728983905125));
        tree.Insert(new Point(minX: 34.6588626003523, maxY: 31.4067422387869, maxX: 34.9847215585919, minY: 31.0609203542086));
        tree.Insert(new Point(minX: 34.5795324959208, maxY: 30.3333639093901, maxX: 35.2158119200309, minY: 29.4630762907736));
        tree.Insert(new Point(minX: 35.3205147130136, maxY: 32.9039553396515, maxX: 35.646707739197, minY: 32.6967048307378));
        tree.Insert(new Point(minX: 35.1178267119206, maxY: 31.4709171748353, maxX: 35.490247102555, minY: 30.3384402926262));
        tree.Insert(new Point(minX: 34.8226151100133, maxY: 33.3817549409005, maxX: 36.0421996128722, minY: 32.2534003894817));
        tree.Insert(new Point(minX: 34.2676635415493, maxY: 31.0234624221816, maxX: 34.6920096335759, minY: 30.6224958789486));
        tree.Insert(new Point(minX: 35.1817645082021, maxY: 32.7613293133493, maxX: 35.5646264318558, minY: 32.4848680398321));
        tree.Insert(new Point(minX: 34.9166085325228, maxY: 31.8549410969553, maxX: 35.1725615321371, minY: 31.7671694138349));
        tree.Insert(new Point(minX: 34.9337083845948, maxY: 32.0150065654742, maxX: 35.0264053464613, minY: 31.876626985909));
        tree.Insert(new Point(minX: 34.835347572723, maxY: 32.3417009250043, maxX: 35.0109342273868, minY: 32.220362279336));
        tree.Insert(new Point(minX: 35.2948832076848, maxY: 31.5574185582711, maxX: 35.5915134856063, minY: 30.9104180607267));
        tree.Insert(new Point(minX: 34.7905250664059, maxY: 32.3417009250043, maxX: 35.0581623045431, minY: 32.1179577036489));
        tree.Insert(new Point(minX: 34.956024319859, maxY: 31.7745298632115, maxX: 35.0116424969789, minY: 31.7012421676793));
        tree.Insert(new Point(minX: 35.0202255429427, maxY: 30.9740219831866, maxX: 35.4679175364723, minY: 30.2435917751572));
        tree.Insert(new Point(minX: 34.8966295938088, maxY: 31.4930353034973, maxX: 35.4390784816745, minY: 30.9115962957363));
        tree.Insert(new Point(minX: 35.0662920752962, maxY: 33.107112234543, maxX: 35.4601689230693, minY: 32.7971835290283));
        tree.Insert(new Point(minX: 34.7340665896918, maxY: 32.0474591284795, maxX: 34.8204120930481, minY: 31.9989943342548));
        tree.Insert(new Point(minX: 34.6941456072459, maxY: 32.0383069680269, maxX: 34.8640822052443, minY: 31.8964808285729));
        tree.Insert(new Point(minX: 34.8811115785741, maxY: 31.7698965550383, maxX: 35.0267092460506, minY: 31.6065949131837));
        tree.Insert(new Point(minX: 34.8003277513142, maxY: 32.0806274386815, maxX: 34.8331150100439, minY: 32.052551536477));
        tree.Insert(new Point(minX: 34.8449718901336, maxY: 32.1384163064534, maxX: 35.0354837295605, minY: 32.003746842197));
        tree.Insert(new Point(minX: 34.6192253584107, maxY: 31.8527172183214, maxX: 34.7668538532351, minY: 31.7651896373863));
        tree.Insert(new Point(minX: 34.9038898727945, maxY: 32.7047870690854, maxX: 35.2017974842687, minY: 32.4160192641257));
        tree.Insert(new Point(minX: 34.5711602610893, maxY: 31.089343112111, maxX: 34.9186022069881, minY: 30.484129839607));
        tree.Insert(new Point(minX: 34.1949967186793, maxY: 31.7707872010952, maxX: 35.475053605904, minY: 30.3364832392137));
        tree.Insert(new Point(minX: 35.5779734622088, maxY: 33.2881090529044, maxX: 35.8581674148078, minY: 32.7292601351151));
        tree.Insert(new Point(minX: 35.2749705330965, maxY: 31.8401766909486, maxX: 35.3704140716109, minY: 31.7397911324406));
        tree.Insert(new Point(minX: 35.3673933021049, maxY: 33.3147865589053, maxX: 35.9062174225714, minY: 32.6843626605618));
        tree.Insert(new Point(minX: 34.9008058486684, maxY: 31.9598496573455, maxX: 35.5757203915414, minY: 31.3746779045228));
        tree.Insert(new Point(minX: 35.598379933386, maxY: 33.0086059628293, maxX: 35.9300290636195, minY: 32.6537719349482));
        tree.Insert(new Point(minX: 34.6095401534748, maxY: 31.9110715079679, maxX: 34.8405932932086, minY: 31.7162092103111));
        tree.Insert(new Point(minX: 34.8216158424473, maxY: 32.1086750906882, maxX: 34.8603966863607, minY: 32.0658349197875));
        tree.Insert(new Point(minX: 34.7332714270174, maxY: 32.046276160073, maxX: 34.8215417657172, minY: 31.9886947121707));
        tree.Insert(new Point(minX: 34.8149293733854, maxY: 32.0574043905775, maxX: 34.9091599462782, minY: 31.9417187138479));
        tree.Insert(new Point(minX: 34.8449718901336, maxY: 32.1394735385545, maxX: 35.0354837295605, minY: 32.0178299374316));
        tree.Insert(new Point(minX: 34.7988787882969, maxY: 32.1055722745323, maxX: 34.8569010984257, minY: 32.0178353029891));
        tree.Insert(new Point(minX: 34.8280655613399, maxY: 32.0377438786708, maxX: 35.0591449537042, minY: 31.7799489556277));
        tree.Insert(new Point(minX: 34.7408084826793, maxY: 31.9217629772612, maxX: 34.9053153865301, minY: 31.7662100576601));
        tree.Insert(new Point(minX: 34.6847053378812, maxY: 32.0105347066497, maxX: 34.8640822052443, minY: 31.8964808285729));
        tree.Insert(new Point(minX: 34.7701973085286, maxY: 32.1473290327111, maxX: 34.8524324985417, minY: 32.0901266819317));
        tree.Insert(new Point(minX: 34.741988219981, maxY: 32.1044330767071, maxX: 34.8140075719916, minY: 32.0294093609064));
        tree.Insert(new Point(minX: 34.835347572723, maxY: 32.3417009250043, maxX: 35.0109342273868, minY: 32.2091924053645));
        tree.Insert(new Point(minX: 34.836714064777, maxY: 32.2220684750668, maxX: 34.9971028731628, minY: 32.1215021618748));
        tree.Insert(new Point(minX: 34.7873539009184, maxY: 32.2478719368633, maxX: 34.8883177683104, minY: 32.1180328589326));
        tree.Insert(new Point(minX: 34.92831830183, maxY: 32.2903664069317, maxX: 35.0574178548968, minY: 32.1710611024405));
        tree.Insert(new Point(minX: 35.3205147130136, maxY: 32.9039553396515, maxX: 35.6457702965872, minY: 32.6967048307378));
        tree.Insert(new Point(minX: 34.8952563054852, maxY: 31.9625925083573, maxX: 35.5736607373982, minY: 31.3899298627969));
        tree.Insert(new Point(minX: 34.8449718901336, maxY: 32.1384163064534, maxX: 35.0354837295605, minY: 32.0178299374316));
        tree.Insert(new Point(minX: 34.8890894442614, maxY: 32.7047870690854, maxX: 35.2017974842687, minY: 32.3883416928594));
        tree.Insert(new Point(minX: 34.8656317039855, maxY: 32.4979457789334, maxX: 35.0423849643375, minY: 32.3738879752974));
        tree.Insert(new Point(minX: 34.7701973085286, maxY: 32.1473290327111, maxX: 34.8524324985417, minY: 32.090031514185));
        tree.Insert(new Point(minX: 34.993192032199, maxY: 32.3212391412162, maxX: 35.5996892102095, minY: 31.9080191148317));
        tree.Insert(new Point(minX: 35.3963660077949, maxY: 32.6939307443726, maxX: 35.609059834246, minY: 32.2180076624529));
        tree.Insert(new Point(minX: 34.9325067524752, maxY: 32.1386430270217, maxX: 35.0356750377975, minY: 32.0409113304089));
        tree.Insert(new Point(minX: 35.043472159742, maxY: 32.8736600563471, maxX: 35.2038027609729, minY: 32.6886762251772));
        tree.Insert(new Point(minX: 34.8449718901336, maxY: 32.1297427854206, maxX: 34.9490546869212, minY: 32.0178299374316));
        tree.Insert(new Point(minX: 34.9263969975396, maxY: 32.8384413743296, maxX: 35.1011727083577, minY: 32.65352493197));
        tree.Insert(new Point(minX: 35.1026228484405, maxY: 32.8356933279248, maxX: 35.3827736665259, minY: 32.6274637163331));
        tree.Insert(new Point(minX: 34.8883898699046, maxY: 32.6849848327049, maxX: 35.2011562856838, minY: 32.3888924841112));
        tree.Insert(new Point(minX: 34.4036190736879, maxY: 32.3567064968128, maxX: 35.0902632353055, minY: 31.4707834956166));
        tree.Insert(new Point(minX: 34.6095401534748, maxY: 32.0383069680269, maxX: 35.0591449537042, minY: 31.7162092103111));
        tree.Insert(new Point(minX: 34.7421834416939, maxY: 32.1466473164001, maxX: 35.0354837295605, minY: 32.003746842197));
        tree.Insert(new Point(minX: 34.7905250664059, maxY: 32.3417009250043, maxX: 35.0581623045431, minY: 32.1179577036489));

        Envelope envelope = new Envelope(34.73274678, 31.87729923, 34.73274678, 31.87729923);
        IEnumerable<Point> contained = tree.Search().Where(p=> p.Envelope.Intersects(envelope));
        int count = contained.Count();
        Assert.AreEqual(count, tree.Search(envelope).Count);
    }
    [TestMethod]
    public void TestBulk()
    {
        RBush<Point> tree = new RBush<Point>();
        List<Point> list = new List<Point>();
        list.Add(new Point(minX: 35.0457204123358, maxY: 31.7658263429689, maxX: 35.1736414417038, minY: 31.5946330633669));
        list.Add(new Point(minX: 35.0011136524732, maxY: 31.6763344627552, maxX: 35.0119650302309, minY: 31.6701999643473));
        list.Add(new Point(minX: 35.4519996266397, maxY: 33.2873426178667, maxX: 35.6225745715679, minY: 33.0521061332025));
        list.Add(new Point(minX: 35.3963660077949, maxY: 32.6939307443726, maxX: 35.609059834246, minY: 31.9833569998672));
        list.Add(new Point(minX: 34.8283506083251, maxY: 32.3931011267767, maxX: 35.074434567496, minY: 32.2548085664601));
        list.Add(new Point(minX: 34.8331658736056, maxY: 32.0096644072503, maxX: 35.0591449537042, minY: 31.7799489556277));
        list.Add(new Point(minX: 35.4232929081405, maxY: 33.0831804221654, maxX: 35.6402606700131, minY: 32.8928176841194));
        list.Add(new Point(minX: 35.1547685550823, maxY: 32.8357311630527, maxX: 35.3829851953318, minY: 32.6409460084027));
        list.Add(new Point(minX: 34.8921664127959, maxY: 31.7780322047787, maxX: 35.0343017543245, minY: 31.6053844677954));
        list.Add(new Point(minX: 34.9263969975396, maxY: 32.8432505478028, maxX: 35.1011727083577, minY: 32.65352493197));
        list.Add(new Point(minX: 35.2394825164923, maxY: 31.8621074757081, maxX: 35.2967869133878, minY: 31.8026823309661));
        list.Add(new Point(minX: 35.3717873599347, maxY: 33.1679615668549, maxX: 35.6478183130483, minY: 32.9175807550062));
        list.Add(new Point(minX: 35.196978533143, maxY: 32.3029676465732, maxX: 35.6432919646234, minY: 31.5634195882077));
        list.Add(new Point(minX: 35.0004845245009, maxY: 31.8400308568811, maxX: 35.1719739039302, minY: 31.7630003816153));
        list.Add(new Point(minX: 34.280847167853, maxY: 31.5639320874003, maxX: 34.8906355571353, minY: 31.0494793743498));
        list.Add(new Point(minX: 34.6095401534748, maxY: 31.9217629772612, maxX: 34.9053153865301, minY: 31.7162092103111));
        list.Add(new Point(minX: 34.836714064777, maxY: 32.2220684750668, maxX: 34.9971028731628, minY: 32.1214817541366));
        list.Add(new Point(minX: 34.8718260788802, maxY: 31.8420049154987, maxX: 35.0378162094246, minY: 31.599197115334));
        list.Add(new Point(minX: 35.1186400639205, maxY: 31.8937001264381, maxX: 35.1868012907541, minY: 31.8691974363715));
        list.Add(new Point(minX: 34.7893345961988, maxY: 32.2478719368633, maxX: 34.8912984464358, minY: 32.1180328589326));
        list.Add(new Point(minX: 35.0560255797127, maxY: 32.8736600563471, maxX: 35.2038027609729, minY: 32.6886762251772));
        list.Add(new Point(minX: 34.5118108403562, maxY: 31.7778320509551, maxX: 35.034306207294, minY: 31.482226934431));
        list.Add(new Point(minX: 34.7421834416939, maxY: 32.1466473164001, maxX: 34.8522596224097, minY: 32.0294016078206));
        list.Add(new Point(minX: 35.2850369921205, maxY: 31.8582696930051, maxX: 35.3671187142204, minY: 31.736701022482));
        list.Add(new Point(minX: 34.3920880329569, maxY: 30.9730153115276, maxX: 35.2259162784014, minY: 30.3321812616403));
        list.Add(new Point(minX: 34.3430710039186, maxY: 31.4431220155161, maxX: 35.3548545278468, minY: 30.9079503533306));
        list.Add(new Point(minX: 34.6081103075024, maxY: 32.1534717814552, maxX: 35.1015149543026, minY: 31.5923121167122));
        list.Add(new Point(minX: 34.7988787882969, maxY: 32.1086750906882, maxX: 34.9092712663857, minY: 32.0164071891458));
        list.Add(new Point(minX: 34.9359618915959, maxY: 32.283413702632, maxX: 35.0574178548968, minY: 32.172467059147));
        list.Add(new Point(minX: 34.8656317039855, maxY: 32.5522748453893, maxX: 35.0578412581373, minY: 32.3738879752974));
        list.Add(new Point(minX: 35.3422616609697, maxY: 33.2954674685247, maxX: 35.8977567880068, minY: 32.9728983905125));
        list.Add(new Point(minX: 34.6588626003523, maxY: 31.4067422387869, maxX: 34.9847215585919, minY: 31.0609203542086));
        list.Add(new Point(minX: 34.5795324959208, maxY: 30.3333639093901, maxX: 35.2158119200309, minY: 29.4630762907736));
        list.Add(new Point(minX: 35.3205147130136, maxY: 32.9039553396515, maxX: 35.646707739197, minY: 32.6967048307378));
        list.Add(new Point(minX: 35.1178267119206, maxY: 31.4709171748353, maxX: 35.490247102555, minY: 30.3384402926262));
        list.Add(new Point(minX: 34.8226151100133, maxY: 33.3817549409005, maxX: 36.0421996128722, minY: 32.2534003894817));
        list.Add(new Point(minX: 34.2676635415493, maxY: 31.0234624221816, maxX: 34.6920096335759, minY: 30.6224958789486));
        list.Add(new Point(minX: 35.1817645082021, maxY: 32.7613293133493, maxX: 35.5646264318558, minY: 32.4848680398321));
        list.Add(new Point(minX: 34.9166085325228, maxY: 31.8549410969553, maxX: 35.1725615321371, minY: 31.7671694138349));
        list.Add(new Point(minX: 34.9337083845948, maxY: 32.0150065654742, maxX: 35.0264053464613, minY: 31.876626985909));
        list.Add(new Point(minX: 34.835347572723, maxY: 32.3417009250043, maxX: 35.0109342273868, minY: 32.220362279336));
        list.Add(new Point(minX: 35.2948832076848, maxY: 31.5574185582711, maxX: 35.5915134856063, minY: 30.9104180607267));
        list.Add(new Point(minX: 34.7905250664059, maxY: 32.3417009250043, maxX: 35.0581623045431, minY: 32.1179577036489));
        list.Add(new Point(minX: 34.956024319859, maxY: 31.7745298632115, maxX: 35.0116424969789, minY: 31.7012421676793));
        list.Add(new Point(minX: 35.0202255429427, maxY: 30.9740219831866, maxX: 35.4679175364723, minY: 30.2435917751572));
        list.Add(new Point(minX: 34.8966295938088, maxY: 31.4930353034973, maxX: 35.4390784816745, minY: 30.9115962957363));
        list.Add(new Point(minX: 35.0662920752962, maxY: 33.107112234543, maxX: 35.4601689230693, minY: 32.7971835290283));
        list.Add(new Point(minX: 34.7340665896918, maxY: 32.0474591284795, maxX: 34.8204120930481, minY: 31.9989943342548));
        list.Add(new Point(minX: 34.6941456072459, maxY: 32.0383069680269, maxX: 34.8640822052443, minY: 31.8964808285729));
        list.Add(new Point(minX: 34.8811115785741, maxY: 31.7698965550383, maxX: 35.0267092460506, minY: 31.6065949131837));
        list.Add(new Point(minX: 34.8003277513142, maxY: 32.0806274386815, maxX: 34.8331150100439, minY: 32.052551536477));
        list.Add(new Point(minX: 34.8449718901336, maxY: 32.1384163064534, maxX: 35.0354837295605, minY: 32.003746842197));
        list.Add(new Point(minX: 34.6192253584107, maxY: 31.8527172183214, maxX: 34.7668538532351, minY: 31.7651896373863));
        list.Add(new Point(minX: 34.9038898727945, maxY: 32.7047870690854, maxX: 35.2017974842687, minY: 32.4160192641257));
        list.Add(new Point(minX: 34.5711602610893, maxY: 31.089343112111, maxX: 34.9186022069881, minY: 30.484129839607));
        list.Add(new Point(minX: 34.1949967186793, maxY: 31.7707872010952, maxX: 35.475053605904, minY: 30.3364832392137));
        list.Add(new Point(minX: 35.5779734622088, maxY: 33.2881090529044, maxX: 35.8581674148078, minY: 32.7292601351151));
        list.Add(new Point(minX: 35.2749705330965, maxY: 31.8401766909486, maxX: 35.3704140716109, minY: 31.7397911324406));
        list.Add(new Point(minX: 35.3673933021049, maxY: 33.3147865589053, maxX: 35.9062174225714, minY: 32.6843626605618));
        list.Add(new Point(minX: 34.9008058486684, maxY: 31.9598496573455, maxX: 35.5757203915414, minY: 31.3746779045228));
        list.Add(new Point(minX: 35.598379933386, maxY: 33.0086059628293, maxX: 35.9300290636195, minY: 32.6537719349482));
        list.Add(new Point(minX: 34.6095401534748, maxY: 31.9110715079679, maxX: 34.8405932932086, minY: 31.7162092103111));
        list.Add(new Point(minX: 34.8216158424473, maxY: 32.1086750906882, maxX: 34.8603966863607, minY: 32.0658349197875));
        list.Add(new Point(minX: 34.7332714270174, maxY: 32.046276160073, maxX: 34.8215417657172, minY: 31.9886947121707));
        list.Add(new Point(minX: 34.8149293733854, maxY: 32.0574043905775, maxX: 34.9091599462782, minY: 31.9417187138479));
        list.Add(new Point(minX: 34.8449718901336, maxY: 32.1394735385545, maxX: 35.0354837295605, minY: 32.0178299374316));
        list.Add(new Point(minX: 34.7988787882969, maxY: 32.1055722745323, maxX: 34.8569010984257, minY: 32.0178353029891));
        list.Add(new Point(minX: 34.8280655613399, maxY: 32.0377438786708, maxX: 35.0591449537042, minY: 31.7799489556277));
        list.Add(new Point(minX: 34.7408084826793, maxY: 31.9217629772612, maxX: 34.9053153865301, minY: 31.7662100576601));
        list.Add(new Point(minX: 34.6847053378812, maxY: 32.0105347066497, maxX: 34.8640822052443, minY: 31.8964808285729));
        list.Add(new Point(minX: 34.7701973085286, maxY: 32.1473290327111, maxX: 34.8524324985417, minY: 32.0901266819317));
        list.Add(new Point(minX: 34.741988219981, maxY: 32.1044330767071, maxX: 34.8140075719916, minY: 32.0294093609064));
        list.Add(new Point(minX: 34.835347572723, maxY: 32.3417009250043, maxX: 35.0109342273868, minY: 32.2091924053645));
        list.Add(new Point(minX: 34.836714064777, maxY: 32.2220684750668, maxX: 34.9971028731628, minY: 32.1215021618748));
        list.Add(new Point(minX: 34.7873539009184, maxY: 32.2478719368633, maxX: 34.8883177683104, minY: 32.1180328589326));
        list.Add(new Point(minX: 34.92831830183, maxY: 32.2903664069317, maxX: 35.0574178548968, minY: 32.1710611024405));
        list.Add(new Point(minX: 35.3205147130136, maxY: 32.9039553396515, maxX: 35.6457702965872, minY: 32.6967048307378));
        list.Add(new Point(minX: 34.8952563054852, maxY: 31.9625925083573, maxX: 35.5736607373982, minY: 31.3899298627969));
        list.Add(new Point(minX: 34.8449718901336, maxY: 32.1384163064534, maxX: 35.0354837295605, minY: 32.0178299374316));
        list.Add(new Point(minX: 34.8890894442614, maxY: 32.7047870690854, maxX: 35.2017974842687, minY: 32.3883416928594));
        list.Add(new Point(minX: 34.8656317039855, maxY: 32.4979457789334, maxX: 35.0423849643375, minY: 32.3738879752974));
        list.Add(new Point(minX: 34.7701973085286, maxY: 32.1473290327111, maxX: 34.8524324985417, minY: 32.090031514185));
        list.Add(new Point(minX: 34.993192032199, maxY: 32.3212391412162, maxX: 35.5996892102095, minY: 31.9080191148317));
        list.Add(new Point(minX: 35.3963660077949, maxY: 32.6939307443726, maxX: 35.609059834246, minY: 32.2180076624529));
        list.Add(new Point(minX: 34.9325067524752, maxY: 32.1386430270217, maxX: 35.0356750377975, minY: 32.0409113304089));
        list.Add(new Point(minX: 35.043472159742, maxY: 32.8736600563471, maxX: 35.2038027609729, minY: 32.6886762251772));
        list.Add(new Point(minX: 34.8449718901336, maxY: 32.1297427854206, maxX: 34.9490546869212, minY: 32.0178299374316));
        list.Add(new Point(minX: 34.9263969975396, maxY: 32.8384413743296, maxX: 35.1011727083577, minY: 32.65352493197));
        list.Add(new Point(minX: 35.1026228484405, maxY: 32.8356933279248, maxX: 35.3827736665259, minY: 32.6274637163331));
        list.Add(new Point(minX: 34.8883898699046, maxY: 32.6849848327049, maxX: 35.2011562856838, minY: 32.3888924841112));
        list.Add(new Point(minX: 34.4036190736879, maxY: 32.3567064968128, maxX: 35.0902632353055, minY: 31.4707834956166));
        list.Add(new Point(minX: 34.6095401534748, maxY: 32.0383069680269, maxX: 35.0591449537042, minY: 31.7162092103111));
        list.Add(new Point(minX: 34.7421834416939, maxY: 32.1466473164001, maxX: 35.0354837295605, minY: 32.003746842197));
        list.Add(new Point(minX: 34.7905250664059, maxY: 32.3417009250043, maxX: 35.0581623045431, minY: 32.1179577036489));

        tree.BulkLoad(list);
        Envelope envelope = new Envelope(34.73274678, 31.87729923, 34.73274678, 31.87729923);
        IEnumerable<Point> contained = tree.Search().Where(p => p.Envelope.Intersects(envelope));
        int count = contained.Count();
        Assert.AreEqual(count, tree.Search(envelope).Count);
    }
}

Question about Inserting Node

Thank you very much for converting the JavaScript code and and sharing it on GitHub, it is not easy to find a C# version for R-tree implementation and I appreciate it.
The code runs through and seems to provide same results compared to my original one without using R-tree, but I have a question.
Below is the code to find the location to insert a new node, but the highlight code seems odd to me. I don't quite follow why it only compares to node.Item[1] every time in the for loop. In this case, newArea will never change when iterate through all items. Shouldn't it compare to node.Item[i]?
I looked at the similar code in JavaScript version, and it seems it compares to node.Item[i], not node.Item[1].

Thanks,

Xiaoxing

JavaScript:

error MinimumMinEntries

I edit the MinimumMaxEntries parameter to 3 instead of 4 as default, I set up the RTree tree with var tree = new RBush(maxEntries: 3);. When creating the RTree tree, I show that the RTree tree has a Node with 1 Entrie. Meanwhile, the default setting parameter is MinimumMinEntries = 2. How to fix this error.

Delete and Count

Count is not update during Delete().

BasicRemoveTest() should be updated with Assert.Equal(shouldFindPoints.Count, tree.Count);
This test fails today.

RBush and rotated rectangles

Hello,

first, I would say thank you for your work.

Is it possible to change RBush, so that it works with rotated rectangles? Any idea? Perhaps first check for the outer rect and if they overlap to check, if it also overlaps with the inner rotated rect? Where to start?

Any help is appreciated.

performance improvment

RBush.BuildNodes() replace data.Skip(left).Take(num).ToList() by data.GetRange(left, num) double BulkLoad() performance during my benchmark.

			if (height == 1)
			{
				//return new Node(data.Skip(left).Take(num).ToList(), height);
				return new Node(data.GetRange(left, num), height);
			}

Note that, if you forget to set maxEntries during RBush construction, BulkLoad() will be very, very, very slow. I suggest to verify the capacity of the RTree in the first lines of Bulkload(). Unfortunatly it is a bit more code than just updating min & maxEntries as in the constructor.

What we need to change C# 7.2 to C# 6

Hi, I don't know you still supporting this project. But I need to use this in VS 2015 with some 3rd party libs. Which they don't support using VS 2017 and C# 7.2. Any idea of how to use in VS 2015 this lib.
By the way, thanks to implementing this project and the performance is crazy comparison to the other Rtree solutions out there.

Recommend Projects

React

A declarative, efficient, and flexible JavaScript library for building user interfaces.
Vue.js

🖖 Vue.js is a progressive, incrementally-adoptable JavaScript framework for building UI on the web.
Typescript

TypeScript is a superset of JavaScript that compiles to clean JavaScript output.
TensorFlow

An Open Source Machine Learning Framework for Everyone
Django

The Web framework for perfectionists with deadlines.
Laravel

A PHP framework for web artisans
D3

Bring data to life with SVG, Canvas and HTML. 📊📈🎉

Recommend Topics

javascript

JavaScript (JS) is a lightweight interpreted programming language with first-class functions.
web

Some thing interesting about web. New door for the world.
server

A server is a program made to process requests and deliver data to clients.
Machine learning

Machine learning is a way of modeling and interpreting data that allows a piece of software to respond intelligently.
Visualization

Some thing interesting about visualization, use data art
Game

Some thing interesting about game, make everyone happy.

Recommend Org

Facebook

We are working to build community through open source technology. NB: members must have two-factor auth.
Microsoft

Open source projects and samples from Microsoft.
Google

Google ❤️ Open Source for everyone.
Alibaba

Alibaba Open Source for everyone
D3

Data-Driven Documents codes.
Tencent

China tencent open source team.