Creating RTree Index on LineString Geometry – Detailed Guide

spatial-index

I'm working with NTS(NetTopologySuite), then I get some geometries with type of LineString, and I want to create the IntervalRTree Index on them.

Here are some codes:

SortedPackedIntervalRTree<LineString> tree = new SortedPackedIntervalRTree<LineString>();

and the Insert Method looks like:

public void Insert(double min, double max, T item)

so, how can I get the "min" and "max" Value of LineString?

also, the Query Method of the tree looks like

public void Query(double min, double max, IItemVisitor<T> visitor)

and how to query the tree index?

Best Answer

You can create an STRtree, which is a query-only R-tree created using the Sort-Tile-Recursive (STR) algorithm for two-dimensional spatial data. More details are at the documentation page of JTS.

To create a STRtree index in NTS,

 ISpatialIndex spatialIndex = new STRtree();

You would insert geometries into the index using the geometry's envelope,

 IGeometry geometry = WktReader.Read(//linestring WKT);
 spatialIndex.Insert(geometry.EnvelopeInternal, geometry);

Now you can retrieve the items whos bounds intersect an envelope using,

 IGeometry boundaryGeom = WktReader.Read(//polygon Wkt);
 Envelope envelope = inProcessGeometry.EnvelopeInternal;
 IList<object> intersectingObjects = spatialIndex.Query(envelope);

Related Solutions

[GIS] Spatial index vs two coordinates indexes

A standard multicolumn b-tree index on the two columns is probably the most effective solution provided that:

both columns are used together in the where expression. A multicolumn index will not be used when only the second column is present

A multicolumn index is more efficient than two indexes on both columns because it will use less storage and will be less costly to update when the table changes (only one index to update vs two).

[GIS] How to work with the STRtree Index when object in the index change it’s position

There are a couple of reasons why what you're trying to do here won't work.

As dpp pointed out, you need to delete / reinsert changed coordinates on the index once something moves around. Otherwise, the index has no way of knowing that its cached metadata is dirty.
Items cannot be inserted into an STRTree once it has been built, so it's not suitable for things that are constantly shifting around.

Quadtree is similar to STRTree and does support on-the-fly insert / remove operations. It's slower, but still OK in practice.

However, all that aside, is there some reason why you need the actual Point instead of just Coordinates? If Coordinate is OK or if you're fine with creating Point objects later on, then Dictionary<Coordinate, int> just seems like a much simpler solution than a spatial index.

Dictionary<Coordinate, int> coordinateMapping = new Dictionary<Coordinate, int>();

// to insert a new coordinate:
int n;
if (!coordinateMapping.TryGetValue(coordinateToInsert, out n))
{
    n = 0;
}
coordinateMapping[coordinateToInsert] = n + 1;
// now future queries will tell you how many of that coordinate are present.

// to determine how many of a given coordinate are present:
int n;
coordinateMapping.TryGetValue(coordinateToQuery, out n);
// check "n" for how many copies of that coordinate are present.

// to remove one of the coordinates from the index:
int n = coordinateMapping[coordinateToRemove];
// the above throws KeyNotFoundException if the coordinate was not present.
if (n == 1)
{
    coordinateMapping.Remove(coordinateToRemove);
}
else
{
    coordinateMapping[coordinateToRemove] = n - 1;
}

Best Answer

Related Solutions

[GIS] Spatial index vs two coordinates indexes

[GIS] How to work with the STRtree Index when object in the index change it’s position

Related Question