I had an idea for a geographic application not so long ago and I was looking for an algorithm to find all elements in a specific region (e.g. spatial index), finally I came upon an algorithm called RTree but I still couldn't find a C# code.

So I decided to port Java Spatial Index Library

You can find it here:

https://sourceforge.net/projects/cspatialindexrt/

Create a new instance:

RTree.RTree<T> tree = new RTree.RTree<T>();

Create a rectangle:

RTree.Rectangle rect = new RTree.Rectangle(1, 2, 3, 4, 5, 6);

Add a new rectangle to the RTree:

tree.Add(rect, object);

Check which objects are inside the rectangle:

var objects = tree.Contains(rect);

Count how many items in the RTree:

var i = tree.Count;

Check which objects intersect with the rectangle:

var objects = tree.Intersects(rect);

Create a point:

RTree.Point point = new RTree.Point(1, 2, 3);

Get a list of rectangles close to the point with maximum distance:

var objects = tree.Nearest(point, 10);

The library's code can be improved, but I needed something quick for a POC.

So I decided to port Java Spatial Index Library

You can find it here:

https://sourceforge.net/projects/cspatialindexrt/

__Basic usage__Create a new instance:

RTree.RTree<T> tree = new RTree.RTree<T>();

Create a rectangle:

RTree.Rectangle rect = new RTree.Rectangle(1, 2, 3, 4, 5, 6);

Add a new rectangle to the RTree:

tree.Add(rect, object);

Check which objects are inside the rectangle:

var objects = tree.Contains(rect);

Count how many items in the RTree:

var i = tree.Count;

Check which objects intersect with the rectangle:

var objects = tree.Intersects(rect);

Create a point:

RTree.Point point = new RTree.Point(1, 2, 3);

Get a list of rectangles close to the point with maximum distance:

var objects = tree.Nearest(point, 10);

The library's code can be improved, but I needed something quick for a POC.

Hi,

ReplyDeleteI do a test. I have 2 geo points. I use the Microsoft.SqlServer.Types.dll to calc the distance between 2 points.

the result is 934.888984856364 meters.

I use your RTree nearest method. it returns the 123 values. I set the furthestDistance parameter to 0.03F.

So I think the returned result is wrong.

Do you have any idea?

var lat=31.240426F, long=121.482235F;

var Bund1 = SqlGeography.Point(lat, long, 4326); //Bund Riverside

var Bund2 = SqlGeography.Point(31.232014, 121.481559, 4326); //Bund (Superior)

Console.WriteLine(Bund1.STDistance(Bund2)); // distance is 934.888984856364 meters

var tre = new RTree.RTree();

tre.Add(new RTree.Rectangle(31.232014F, 121.481559F, 31.232014F, 121.481559F, 0.0F, 0.0F), 123);

var li = tre.Nearest(new RTree.Point(lat, long, 0.0F), 0.03F);

I think you're confusing spatial and geographical.

DeleteRTree is a spatial index while SqlGeography is geographical.

Calculating distance between two points in 2D space:

http://www.mathwarehouse.com/algebra/distance_formula/index.php

Calculating distance between two geographical points is a bit more complicated:

http://www.movable-type.co.uk/scripts/latlong.html

The numbers you provided are lon/lat, which means they are the angles from the equator/Greenwich on Earth, the distance uses the earth radius to calculate distances.

Oh....,, Thank you SO MUCH!!!!

DeleteHello.I have very stupid question.I don't understand what is object in tree.Add(rect, object);

ReplyDeleteFor example: tree.Add(new RTree.Rectangle(xmin, ymin, xmax, ymax, 0, 0), object);

Best wishes.

And one more question.May be you can help me with this.

ReplyDeleteI add an element to list of elements.Also I get list of point for creating Rectangle in Rtree and add rectangle to a tree-instance.

After this I find Rectangle nearest to my point.Can I get the index of this rectangle in tree-instance to get index of my element?

Best Wishes,Denis.

Hi Denis,

DeleteYou should instantiate RTree with your container type instead of object, create a class and store all the properties you'd like to associate with a particular point/rectangle.

I'll need a specific example to be more specific :-)

Hi, just a quick one really, can the RTree.RTree and all of its added instances be serialized, written out into a binary stream and retrieve it from them later on?

ReplyDelete