how to create RTree index on LineString geometry

Question

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?

Answer 1

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

Answer 2

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.

Answer 3

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