STRTree¶

class STRtree(geometries, leafsize=10)¶

A query-only R-tree created using the Sort-Tile-Recursive (STR) algorithm.

For two-dimensional spatial data. The tree is constructed directly at initialization.

Parameters

geometriesarray_like
leafsizeint, default 10: the maximum number of child nodes that a node can have

Examples

>>> import pygeos
>>> tree = pygeos.STRtree(pygeos.points(np.arange(10), np.arange(10)))
>>> # Query geometries that overlap envelope of input geometries:
>>> tree.query(pygeos.box(2, 2, 4, 4)).tolist()
[2, 3, 4]
>>> # Query geometries that are contained by input geometry:
>>> tree.query(pygeos.box(2, 2, 4, 4), predicate='contains').tolist()
[3]
>>> # Query geometries that overlap envelopes of ``geoms``
>>> tree.query_bulk([pygeos.box(2, 2, 4, 4), pygeos.box(5, 5, 6, 6)]).tolist()
[[0, 0, 0, 1, 1], [2, 3, 4, 5, 6]]
>>> tree.nearest([pygeos.points(1,1), pygeos.points(3,5)]).tolist()  
[[0, 1], [1, 4]]

nearest(geometry)¶

Returns the index of the nearest item in the tree for each input geometry.

Note

‘nearest’ requires at least GEOS 3.6.0.

If there are multiple equidistant or intersected geometries in the tree, only a single result is returned for each input geometry, based on the order that tree geometries are visited; this order may be nondeterministic.

Any geometry that is None or empty in the input geometries is omitted from the output.

Parameters

geometryGeometry or array_like: Input geometries to query the tree.

Returns

ndarray with shape (2, n): The first subarray contains input geometry indexes. The second subarray contains tree geometry indexes.

See also

nearest_all: returns all equidistant geometries and optional distances

Examples

>>> import pygeos
>>> tree = pygeos.STRtree(pygeos.points(np.arange(10), np.arange(10)))
>>> tree.nearest(pygeos.points(1,1)).tolist()  
[[0], [1]]
>>> tree.nearest([pygeos.box(1,1,3,3)]).tolist()  
[[0], [1]]
>>> points = pygeos.points(0.5,0.5)
>>> tree.nearest([None, pygeos.points(10,10)]).tolist()  
[[1], [9]]

nearest_all(geometry, max_distance=None, return_distance=False)¶

Returns the index of the nearest item(s) in the tree for each input geometry.

Note

‘nearest_all’ requires at least GEOS 3.6.0.

If there are multiple equidistant or intersected geometries in tree, all are returned. Tree indexes are returned in the order they are visited for each input geometry and may not be in ascending index order; no meaningful order is implied.

The max_distance used to search for nearest items in the tree may have a significant impact on performance by reducing the number of input geometries that are evaluated for nearest items in the tree. Only those input geometries with at least one tree item within +/- max_distance beyond their envelope will be evaluated.

The distance, if returned, will be 0 for any intersected geometries in the tree.

Any geometry that is None or empty in the input geometries is omitted from the output.

Parameters

geometryGeometry or array_like: Input geometries to query the tree.
max_distancefloat, optional: Maximum distance within which to query for nearest items in tree. Must be greater than 0.
return_distancebool, default False: If True, will return distances in addition to indexes.

Returns

indices or tuple of (indices, distances): indices is an ndarray of shape (2,n) and distances (if present) an ndarray of shape (n). The first subarray of indices contains input geometry indices. The second subarray of indices contains tree geometry indices.

See also

nearest: returns singular nearest geometry for each input

Examples

>>> import pygeos
>>> tree = pygeos.STRtree(pygeos.points(np.arange(10), np.arange(10)))
>>> tree.nearest_all(pygeos.points(1,1)).tolist()  
[[0], [1]]
>>> tree.nearest_all([pygeos.box(1,1,3,3)]).tolist()  
[[0, 0, 0], [1, 2, 3]]
>>> points = pygeos.points(0.5,0.5)
>>> index, distance = tree.nearest_all(points, return_distance=True)  
>>> index.tolist()  
[[0, 0], [0, 1]]
>>> distance.round(4).tolist()  
[0.7071, 0.7071]
>>> tree.nearest_all(None).tolist()  
[[], []]

query(geometry, predicate=None)¶

Return the index of all geometries in the tree with extents that intersect the envelope of the input geometry.

If predicate is provided, a prepared version of the input geometry is tested using the predicate function against each item whose extent intersects the envelope of the input geometry: predicate(geometry, tree_geometry).

If geometry is None, an empty array is returned.

Parameters

geometryGeometry: The envelope of the geometry is taken automatically for querying the tree.
predicate{None, ‘intersects’, ‘within’, ‘contains’, ‘overlaps’, ‘crosses’,’touches’, ‘covers’, ‘covered_by’, ‘contains_properly’}, optional: The predicate to use for testing geometries from the tree that are within the input geometry’s envelope.

Returns

ndarray: Indexes of geometries in tree

Examples

>>> import pygeos
>>> tree = pygeos.STRtree(pygeos.points(np.arange(10), np.arange(10)))
>>> tree.query(pygeos.box(1,1, 3,3)).tolist()
[1, 2, 3]
>>> # Query geometries that are contained by input geometry
>>> tree.query(pygeos.box(2, 2, 4, 4), predicate='contains').tolist()
[3]

query_bulk(geometry, predicate=None)¶

Returns all combinations of each input geometry and geometries in the tree where the envelope of each input geometry intersects with the envelope of a tree geometry.

If predicate is provided, a prepared version of each input geometry is tested using the predicate function against each item whose extent intersects the envelope of the input geometry: predicate(geometry, tree_geometry).

This returns an array with shape (2,n) where the subarrays correspond to the indexes of the input geometries and indexes of the tree geometries associated with each. To generate an array of pairs of input geometry index and tree geometry index, simply transpose the results.

In the context of a spatial join, input geometries are the “left” geometries that determine the order of the results, and tree geometries are “right” geometries that are joined against the left geometries. This effectively performs an inner join, where only those combinations of geometries that can be joined based on envelope overlap or optional predicate are returned.

Any geometry that is None or empty in the input geometries is omitted from the output.

Parameters

geometryGeometry or array_like: Input geometries to query the tree. The envelope of each geometry is automatically calculated for querying the tree.
predicate{None, ‘intersects’, ‘within’, ‘contains’, ‘overlaps’, ‘crosses’,’touches’, ‘covers’, ‘covered_by’, ‘contains_properly’}, optional: The predicate to use for testing geometries from the tree that are within the input geometry’s envelope.

Returns

ndarray with shape (2, n): The first subarray contains input geometry indexes. The second subarray contains tree geometry indexes.

Examples

>>> import pygeos
>>> tree = pygeos.STRtree(pygeos.points(np.arange(10), np.arange(10)))
>>> tree.query_bulk([pygeos.box(2, 2, 4, 4), pygeos.box(5, 5, 6, 6)]).tolist()
[[0, 0, 0, 1, 1], [2, 3, 4, 5, 6]]
>>> # Query for geometries that contain tree geometries
>>> tree.query_bulk([pygeos.box(2, 2, 4, 4), pygeos.box(5, 5, 6, 6)], predicate='contains').tolist()
[[0], [3]]
>>> # To get an array of pairs of index of input geometry, index of tree geometry,
>>> # transpose the output:
>>> tree.query_bulk([pygeos.box(2, 2, 4, 4), pygeos.box(5, 5, 6, 6)]).T.tolist()
[[0, 2], [0, 3], [0, 4], [1, 5], [1, 6]]