# how to create RTree index on LineString geometry

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?

• Could you briefly explain what you are trying to achieve using the Index? Find the features within an envelope? Sep 12, 2012 at 9:54
• hi vinayan, I'm trying to create the spatialindex on a large amount of geometries. With spatial index, I can find some geometries within an envelope (eg, maybe the envelope maked by a buffer) instead of traverse them. Sep 15, 2012 at 2:49

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

The IntervalRTree is an index for 1-dimensional intervals. You can use it to store the projection of your line strings on an axis of the coordinate system. In that case you would compute the Envelope of your LineString and then get its minimum and maximum X or Y values. Of course there are other ways to project 2-dimensional geometries to 1-dimensional intervals (for example distance to the origin of your coordinate system). These will be trickier to compute.

You query the IntervalRTree with an interval. You will get all items which have intervals that intersect your query interval.

The Query Method uses the visitor pattern. You can either write your own class that implements the ItemVisitor interface and does whatever you need it to do in the VistitItem method or you can use ArrayListVisitor which simply collects all the Items in an ArrayList.

@vinayan's answer generates wrong results. According to the original JTS docs, an Envelope

"defines a rectangular region of the 2D coordinate plane. It is often used to represent the bounding box of a Geometry, e.g. the minimum and maximum x and y values of the Coordinates."

This means that NTS will consider your envelope as a rectangle and not a LINESTRING. LINESTRINGs are 1D intervals and you would need a data-structure that handles 1D Geometry.

EDIT:

The solution would be to use NTS's 1-D spatial-index called SIRTree. Here is how to create one:

``````ISpatialIndex spatialIndex = new SIRtree();
``````

Then provide double values for the coordinates to the insert method instead of an Envelope.

• Hi, Can you give an example to explain that more detail? Oct 8, 2012 at 5:58
• @Moe - It does not generate wrong results.. please read a little bit about spatial indexing(workshops.opengeo.org/postgis-intro/indexing.html) .. in short, its a quick way of retrieving objects from large set without going through a big loop..you just pass an envelope to the Index and get the list of features within that envelope.. Oct 8, 2012 at 11:06
• @vinayan please stop reading and actually run the code. Envelope is a rectangle. IList<object> intersectingObjects = spatialIndex.Query(envelope); will return anything that intersects with that rectangle, and not the LineString. Spatial indexes are useless if they only retrieve objects, they have to calculate geometric functions like intersections as well, and based on your example, it returns wrong results for LineStrings. In other words, Envelope is the wrong wrapper for a LineString.
– Joe
Oct 8, 2012 at 17:31
• @billycat JTS provides a 1-D spatialindex called SIRTree [1] which is exactly what you need as opposed to @vinayan's suggested STRTree. NTS also provides this index [2] so to create one you would change @vinayan's code to `ISpatialIndex spatialIndex = new SIRtree();` and then the insert method will take double coordinates instead of envelope. I edited the original answer to reflect those changes. [1] tsusiatsoftware.net/jts/javadoc/index.html [2] code.google.com/p/nettopologysuite/source/browse/trunk/…
– Joe
Oct 8, 2012 at 17:59
• AFAIK, spatial index is used for quick retrieval of objects..the spatial comparisons to be done are up-to the user..that is why my answer mentions "retrieve the items whos bounds intersect an envelope" Oct 9, 2012 at 7:01