Saturday, April 11, 2009

RTree

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/


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.

9 comments:

  1. Hi,

    I 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);

    ReplyDelete
    Replies
    1. I think you're confusing spatial and geographical.

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


      Delete
  2. Hello.I have very stupid question.I don't understand what is object in tree.Add(rect, object);
    For example: tree.Add(new RTree.Rectangle(xmin, ymin, xmax, ymax, 0, 0), object);
    Best wishes.

    ReplyDelete
  3. And one more question.May be you can help me with this.
    I 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.

    ReplyDelete
    Replies
    1. Hi Denis,
      You 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 :-)

      Delete
  4. 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
  5. Hi, the Nearest function seems to have a bug when used in multi-threaded environment. It is because nearestIds is global, so simultaneous invocation of the same rtree object Nearest function will cause an exception because it is trying to modify the list while some other process is iterating through that same list.

    Thanks!

    ReplyDelete
    Replies
    1. Didn't know the library was still in use, its pretty old...
      I've migrated it to github: https://github.com/drorgl/cspatialindexrt
      I did a quick fix, feel free to test it or do a pull request.

      Delete