Python implementation of Priority R-Tree
Project description
python_prtree
python_prtree is a python/c++ implementation of the Priority R-Tree (see references below). The supported futures are as follows:
- Construct a Priority R-Tree (PRTree) from an array of rectangles
- The array shape is (xmin, ymin, xmax, ymax) in 2D and (xmin, ymin, zmin, xmax, ymax, zmax) in 3D.
- 3D PRTree is supported since
>=0.4.0
. - Changed the ordering of the array shape since
>=0.5.0
.
query
andbatch_query
with rectangle(s)- Supports Point query with (x, y) in 2D and (x, y, z) in 3D since
>=0.5.1
- Supports Point query with (x, y) in 2D and (x, y, z) in 3D since
insert
anderase
(but not yet optimized)- Fixed a bug that one cannot insert to an empty PRTree at
0.5.0
.
- Fixed a bug that one cannot insert to an empty PRTree at
rebuild
with already given data since>=0.5.0
.- For better performance when too many insert/erase operations are called since.
- The
insert
andquery
methods can now be passed pickable Python objects instead of int64 indexes since>=0.5.2
.- See the example below for more details.
This package is mainly for mostly static situations where insertion and deletion events rarely occur (e.g. map matching).
Installation
You can install python_prtree with the pip command:
pip install python-prtree
If the pip installation does not work (e.g. on an M1 Mac), please git clone clone and install as follows:
pip install -U cmake pybind11
git clone --recursive https://github.com/atksh/python_prtree
cd python_prtree
python setup.py install
A Simple Example
import numpy as np
from python_prtree import PRTree2D
idxes = np.array([1, 2]) # must be unique because it uses idx as key for hash map
rects = np.array([[0.0, 0.0, 1.0, 0.5],
[1.0, 1.5, 1.2, 3.0]]) # (xmin, ymin, xmax, ymax)
prtree = PRTree2D(idxes, rects) # initial construction
q = np.array([[0.5, 0.2, 0.6, 0.3],
[0.8, 0.5, 1.5, 3.5]])
result = prtree.batch_query(q)
print(result)
# [[1], [1, 2]]
# You can insert an additional rectangle,
prtree.insert(3, np.array([1.0, 1.0, 2.0, 2.0]))
q = np.array([[0.5, 0.2, 0.6, 0.3],
[0.8, 0.5, 1.5, 3.5]])
result = prtree.batch_query(q)
print(result)
# [[1], [1, 2, 3]]
# And erase by index.
prtree.erase(2)
result = prtree.batch_query(q)
print(result)
# [[1], [1, 3]]
# Point query
print(prtree.query(0.5, 0.5))
# [1]
print(prtree.query((0.5, 0.5)))
# [1]
New Features and Changes
python-prtree>=0.5.3
- Add gzip compression for pickled objects.
python-prtree>=0.5.2
You can use pickable Python objects instead of int64 indexes for insert
and query
methods:
import numpy as np
from python_prtree import PRTree2D
objs = [{"name": "foo"}, (1, 2, 3)] # must NOT be unique but pickable
rects = np.array([[0.0, 0.0, 1.0, 0.5],
[1.0, 1.5, 1.2, 3.0]]) # (xmin, ymin, xmax, ymax)
prtree = PRTree2D()
for obj, rect in zip(objs, rects):
# keyword argments: bb(bounding box) and obj(object)
prtree.insert(bb=rect, obj=obj)
# returns indexes genereted by incremental rule.
result = prtree.query((0, 0, 1, 1))
print(result)
# [1]
# returns objects when you specify the keyword argment return_obj=True
result = prtree.query((0, 0, 1, 1), return_obj=True)
print(result)
# [{'name': 'foo'}]
python-prtree>=0.5.0
- [CRUTIAL] Changed the input order from (xmin, xmax, ymin, ymax, ...) to (xmin, ymin, xmax, ymax, ...).
- [FEATURE] Added rebuild method to build the PRTree from scratch using the already given data.
- [BUGFIX] Fixed a bug that prevented insertion into an empty PRTree.
- [REMIND] Cross-version saving and loading compatibility is not guaranteed.
python-prtree>=0.4.0
You can use PRTree3D:
import numpy as np
from python_prtree import PRTree3D
idxes = np.array([1, 2]) # must be unique because it uses idx as key for hash map
rects = np.array([[0.0, 0.5, 0.0, 0.5, 1.0, 0.5],
[1.0, 1.5, 2.0, 1.2, 2.5, 3.0]]) # (xmin, ymin, zmin, xmax, ymax, zmax)
prtree = PRTree3D(idxes, rects) # initial construction
q = np.array([[0.5, 0.2, 0.2, 0.6, 0.3, 0.3],
[0.8, 0.5, 0.5, 1.5, 3.5, 3.5]])
result = prtree.batch_query(q)
print(result)
# [[], [2]]
python-prtree>=0.3.0
You can save and load a binary file as follows:
# save
prtree.save('tree.bin')
# load with binary file
prtree = PRTree('tree.bin')
# or defered load
prtree = PRTree()
prtree.load('tree.bin')
Cross-version compatibility is NOT guaranteed, so please reconstruct your tree when you update this package.
Note
The 1d-array batch query will be implicitly treated as a batch with size = 1.
If you want 1d result, please use query
method.
result = prtree.query(q[0])
print(result)
# [1]
result = prtree.batch_query(q[0])
print(result)
# [[1]]
You can also erase(delete) by index and insert a new one.
prtree.erase(1) # delete the rectangle with idx=1 from the PRTree
prtree.insert(3, np.array([0.3, 0.5, 0.1, 0.2])) # add a new rectangle to the PRTree
Performance
Construction
2d
3d
Query and batch query
2d
3d
Delete and insert
2d
3d
Requirement
- numpy
NOTE
- C++ implements this PRTree with Pybind11 and much faster than the numba implementation of PRTree.
- If you can use C++, you should use boost::geometry (I did not know it and sadly made this package).
- Please note that insert / erase operations are not optimized compared to ordinary r-tree. Plus, this implementation does not exactly follow that of the paper due to my technical skills.
Reference
The Priority R-Tree: A Practically Efficient and Worst-Case Optimal R-Tree Lars Arge, Mark de Berg, Herman Haverkort, and Ke Yi Proceedings of the 2004 ACM SIGMOD International Conference on Management of Data (SIGMOD '04), Paris, France, June 2004, 347-358. Journal version in ACM Transactions on Algorithms. author's page
Project details
Release history Release notifications | RSS feed
Download files
Download the file for your platform. If you're not sure which to choose, learn more about installing packages.
Source Distribution
Built Distributions
Hashes for python_prtree-0.5.3-cp39-cp39-win_amd64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | bdd2ec6d9a26a9953cd695eed4489863ba82375eff441f73c32e368411071cb8 |
|
MD5 | 66ad1933228347e43d57d0b5c413989e |
|
BLAKE2b-256 | fbfe98161d5ea1c2b014aa52330d00a529ade207b80679b783919ea3feab4b7c |
Hashes for python_prtree-0.5.3-cp39-cp39-manylinux_2_17_x86_64.manylinux2014_x86_64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 698121c1940ee91407c77911b4b13a6bdca7d393275a19df6a20a34906d2265d |
|
MD5 | f3961580d87bf7e247fca56dba19edea |
|
BLAKE2b-256 | 9f8465f34726f6ce4d76a410fe420b82c3db27365c47a43428a27aa1a343dfe0 |
Hashes for python_prtree-0.5.3-cp39-cp39-manylinux_2_17_aarch64.manylinux2014_aarch64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 6a948e5002abece8ce098045df705b8881381a388711ab3b30f009154dc47b05 |
|
MD5 | 99b33a91bc885aa0558816fb8c2f26e7 |
|
BLAKE2b-256 | 8fe4ffd13aba1b65bd30434a5b7b8c1140a03149f3b5cc42869076200c9f3627 |
Hashes for python_prtree-0.5.3-cp39-cp39-macosx_10_15_x86_64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 8a0c1a159af1a95c24242adbacb5f01921d09ec7800d5e82820a40c57e37079f |
|
MD5 | 0a28008633b46cf3c3f1830efc8e1bed |
|
BLAKE2b-256 | 7b4fb0c124d43d9d565445db4e322a067fb47778a6aa1e7d3655b64009611d4c |
Hashes for python_prtree-0.5.3-cp38-cp38-win_amd64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | efee2f5424228cc1cee5cf454e49d03dfe2fd4802734d44f45284db69072f41d |
|
MD5 | 3264af7ac10e2a5df434fcfcbac7e382 |
|
BLAKE2b-256 | abb789a98893469b32e6874faaa16c008eb216de9e2d37b015717f3aa376d97b |
Hashes for python_prtree-0.5.3-cp38-cp38-manylinux_2_17_x86_64.manylinux2014_x86_64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 31e1fdae216de9d953fc5e210c97ae69c3a388b3031f73979f8de976e2fb79e6 |
|
MD5 | 6df3ced767e93fdbb3dceb358934ef6b |
|
BLAKE2b-256 | 87b87dfe2ec4788230f464d71642ccddac02b33a315412bd80cd7971bf4304d2 |
Hashes for python_prtree-0.5.3-cp38-cp38-manylinux_2_17_aarch64.manylinux2014_aarch64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | c9e86fd932638ac441f0c74e300acd4cffa4747f8de6abb920d08dc5e56985a5 |
|
MD5 | 01b7c44d6a71b043bdd31b3a325a8efc |
|
BLAKE2b-256 | df5f8d43a425bc967ec2ee9b8bde59416fa9bf52dbdd4d026d51a8226fd00753 |
Hashes for python_prtree-0.5.3-cp38-cp38-macosx_10_15_x86_64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | a4bec8af21ec2313a5100e0dbfbfde4f66dd725ac24d7774e763cc456a3a1d76 |
|
MD5 | cb8fc3fd7a1379247e50b1cf665cb64d |
|
BLAKE2b-256 | 58a9a307ed6d58ea4584c059b2d335c9e7d99c21c4458498f85a9e0a0720203e |
Hashes for python_prtree-0.5.3-cp37-cp37m-win_amd64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | a21ff3c029123e3455a77d1a5624eeca89f18d063ebf97598be3a201921a9253 |
|
MD5 | f97315f469990ef67798066b49018d2f |
|
BLAKE2b-256 | 505c85f320205a09140980135ac7173175f6fa906a947d288ee8595c69a305f4 |
Hashes for python_prtree-0.5.3-cp37-cp37m-manylinux_2_17_x86_64.manylinux2014_x86_64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | ae155d45a08a2a19c73d2df4df2164693be682504dc908d9a4764bcf039a2204 |
|
MD5 | 287345f76ab8fbcc037fa1cfeef70867 |
|
BLAKE2b-256 | b80a06a849b2a579156fa8eca7b0a9aa90741d10ab5f028fbf8a2d60c77f2a5b |
Hashes for python_prtree-0.5.3-cp37-cp37m-manylinux_2_17_aarch64.manylinux2014_aarch64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | d6c636b23a19e6fe4f6a89f0e5f3416f3e2912d797ab0c72d133404ce9c0df29 |
|
MD5 | 09b399f61e1b1fad6a7a883ec7e82dd2 |
|
BLAKE2b-256 | 65246d30cd5efb8df8a4f7f88b659fb17a6404650db221d3d3354ae0fe2f60f2 |
Hashes for python_prtree-0.5.3-cp37-cp37m-macosx_10_15_x86_64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 4a4e1c2576662a9e0e1fb25ff8b690f32a8c8e50efa3c2f4c618705d8aa418bb |
|
MD5 | d3d72159ac7eed8c529dacac090c7866 |
|
BLAKE2b-256 | 9366b520f19c49fce5714598627525a7742271947a7457da8059b1d7efe15b2c |
Hashes for python_prtree-0.5.3-cp36-cp36m-win_amd64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 0b1ca4d33e140c03b6075c4e3c5c896fec960e95c01757a57566a88cf6206772 |
|
MD5 | c6f9eb3d09f884931be13a8aa48675e7 |
|
BLAKE2b-256 | e160b391ade3cedf47298451e1edb3d5a48dbd8e7a43047166d7f0adc5db18c7 |
Hashes for python_prtree-0.5.3-cp36-cp36m-manylinux_2_17_x86_64.manylinux2014_x86_64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | f3861f09d076dca6080c3b431ca1ae018857942150f3fc9124af7c67688ab723 |
|
MD5 | 006bbe71d4233a3180f07465abd7fe97 |
|
BLAKE2b-256 | fefb237c3508cf4cbf54c4f734ca41840635dba3c3cf39546e8ec68e172e180d |
Hashes for python_prtree-0.5.3-cp36-cp36m-manylinux_2_17_aarch64.manylinux2014_aarch64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | e4d6f102ee4b689dda0a5baa30484a5445d49e23dae867a6b69e3d71bd15c2c9 |
|
MD5 | 35b478d45d5969825ed2eec06e2a933f |
|
BLAKE2b-256 | f2186f99f723398ae0f4564bcb6a19a06d16c5d84b5f9be69436bdf8a0ff1884 |
Hashes for python_prtree-0.5.3-cp36-cp36m-macosx_10_15_x86_64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 346ce0ba9ed2226234804ee3a6234622690b47db53c57a62ad0f8b7e1ce25281 |
|
MD5 | 0b63f3a363c60f18e2a1e18d5306bd90 |
|
BLAKE2b-256 | d46ec119db86205f0a7374d80dc1666cd980ed15f470f34c7456a1d9dccad434 |