fastquadtree.pyqtree.Index¶
The interface of the class below is taken from the pyqtree package, but the implementation has been modified to use the fastquadtree package as a backend instead of the original pure-python implementation. Based on the benchmarks, this gives a overall performance boost of 6.514x. See the benchmark section of the docs for more details and the latest numbers.
Index is the top-level class for creating and using a quadtree spatial index with the original pyqtree interface. If you are not migrating from pyqtree, consider using the RectQuadTree class for detailed control and better performance.
This class wraps a RectQuadTree instance and provides methods to insert items with bounding boxes, remove items, and query for items intersecting a given bounding box.
Example usage:
from fastquadtree.pyqtree import Index
spindex = Index(bbox=(0, 0, 100, 100))
spindex.insert('duck', (50, 30, 53, 60))
spindex.insert('cookie', (10, 20, 15, 25))
spindex.insert('python', (40, 50, 95, 90))
results = spindex.intersect((51, 51, 86, 86))
sorted(results) # ['duck', 'python']
Initiate by specifying either 1) a bbox to keep track of, or 2) with an xy centerpoint and a width and height.
Parameters:
| Name | Type | Description | Default |
|---|---|---|---|
bbox | Iterable[SupportsFloat] | None | The coordinate system bounding box of the area that the quadtree should keep track of, as a 4-length sequence (xmin,ymin,xmax,ymax) | None |
x | float | int | None | The x center coordinate of the area that the quadtree should keep track of. | None |
y | float | int | None | The y center coordinate of the area that the quadtree should keep track of. | None |
width | float | int | None | How far from the xcenter that the quadtree should look when keeping track. | None |
height | float | int | None | How far from the ycenter that the quadtree should look when keeping track | None |
max_items | optional | The maximum number of items allowed per quad before splitting up into four new subquads. Default is 10. | MAX_ITEMS |
max_depth | optional | The maximum levels of nested subquads, after which no more splitting occurs and the bottommost quad nodes may grow indefinately. Default is 20. | MAX_DEPTH |
Note
Either the bbox argument must be set, or the x, y, width, and height arguments must be set.
insert(item, bbox) ¶
Inserts an item into the quadtree along with its bounding box.
Parameters:
| Name | Type | Description | Default |
|---|---|---|---|
item | Any | The item to insert into the index, which will be returned by the intersection method | required |
bbox | Iterable[SupportsFloat] | The spatial bounding box tuple of the item, with four members (xmin,ymin,xmax,ymax) | required |
remove(item, bbox) ¶
Removes an item from the quadtree.
Parameters:
| Name | Type | Description | Default |
|---|---|---|---|
item | Any | The item to remove from the index | required |
bbox | Iterable[SupportsFloat] | The spatial bounding box tuple of the item, with four members (xmin,ymin,xmax,ymax) | required |
Note
Both parameters need to exactly match the parameters provided to the insert method.
intersect(bbox) ¶
Intersects an input bounding box rectangle with all of the items contained in the quadtree.
Parameters:
| Name | Type | Description | Default |
|---|---|---|---|
bbox | Iterable[SupportsFloat] | A spatial bounding box tuple with four members (xmin,ymin,xmax,ymax) | required |
Returns:
| Type | Description |
|---|---|
list | A list of inserted items whose bounding boxes intersect with the input bbox. |