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.

6 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