Python implementation of Priority R-Tree
Project description
python_prtree
"python_prtree" is a python implementation of Priority R-Tree (see reference below). Supported futures are as follows:
- Construct Priority R-Tree(PRTree) from rectangles; an array of (xmin, xmax, ymin, ymax)
- query and batch query with a rectangle(s)
- insert and erase(delete) (but not optimized yet)
This package is mainly for nearly static situations, which mean few insert/delete events happen (e.g., map-matching).
Usage
import numpy as np
from python_prtree import PRTree
idxes = np.array([1, 2]) # must be unique because using idx as key for hash map
rects = np.array([[0.0, 1.0, 0.0, 0.5],
[1.0, 1.2, 2.5, 3.0]]) # (xmin, xmax, ymin, ymax)
prtree = PRTree(idxes, rects) # initial construction
q = np.array([[0.5, 0.6, 0.2, 0.3],
[0.8, 1.5, 0.5, 3.5]])
result = prtree.batch_query(q)
print(result)
# [[1], [1, 2]]
New features(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')
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
Installation
To install python_prtree with pip command
pip install python-prtree
Or, you can clone and install just like
git clone --recursive https://github.com/atksh/python_prtree
cd python_prtree
python setup.py install
This installation needs cmake.
Performance
Construction
Query and batch query
Delete and insert
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 Distributions
Built Distributions
Hashes for python_prtree-0.3.1-cp38-cp38-win_amd64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 3edbf55a3f8da88139b5b94f283d3150a880b5733558e901c30dadae157c92a9 |
|
MD5 | 650bb170fbb5c7cb3683bc6dcdc5aeb2 |
|
BLAKE2b-256 | 9b5c397eaf8c342d6b6cbada9155d394709cf1c3938e923d93880e6f121461bf |
Hashes for python_prtree-0.3.1-cp38-cp38-manylinux2014_x86_64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | b57b720958406d3120bbaad899dc8f12e605ab9ea0813fd21a016dd7f4188b51 |
|
MD5 | 72fc6bb17bb7c6a0c88569f31b5eb206 |
|
BLAKE2b-256 | b819a35395d4aa327ea52809ce905cd3d3a2d2153517fd3d97aab3beb5c69ec2 |
Hashes for python_prtree-0.3.1-cp38-cp38-macosx_10_9_x86_64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 7d822aa3d96d7730eb83052aeb1ff8cce5747fb9765791dc8d41d03adee7e6dc |
|
MD5 | 8e20ed1e12528413c3ddc78b3a339be5 |
|
BLAKE2b-256 | d440563fdc930de1774a62ac17df2823851eb8aefaaabaaff9be86243bb92957 |
Hashes for python_prtree-0.3.1-cp37-cp37m-win_amd64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | b970f08127ebad97a26bc7e3a1a027f573fb5e91ea1878fe72dd9754f307f054 |
|
MD5 | 32db62f26eb6c5b07fabf9a6a491b3fa |
|
BLAKE2b-256 | f44ba3d6087895f36031bec6598058210f3483f73e623ef31a29141f0f4a87ce |
Hashes for python_prtree-0.3.1-cp37-cp37m-manylinux2014_x86_64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | c8ee119d54fc3db4637c7a5c2270e1e355c30aeca6d251602a633223d98763ba |
|
MD5 | e2c82a751b6e168abe22d97ff0fcdb18 |
|
BLAKE2b-256 | 6eee66e8faf6a5d787158ba88ed955a18a51a676132818fd03002c46b84e3edd |
Hashes for python_prtree-0.3.1-cp37-cp37m-macosx_10_9_x86_64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 8257219e2fb894a40b7649a09d3a6c77270948e6cb7d80346c1eecdcead52402 |
|
MD5 | 49b50bedb696961ab7277b86979c2560 |
|
BLAKE2b-256 | 7b3db237b0e3b7ea94a42b3b3a59763dff388c53ad779acb4e7a8192221e4154 |
Hashes for python_prtree-0.3.1-cp36-cp36m-win_amd64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | c2315691057c66e05217b86f07382c217ce9022ead91ee91733f7f2ccd7be6e9 |
|
MD5 | 67da449198e1509d77a20dfc4eba52c5 |
|
BLAKE2b-256 | bb82399eadf828214936fa8ff00e2c70674e37993e3207aefa9cd208cd1efe93 |
Hashes for python_prtree-0.3.1-cp36-cp36m-manylinux2014_x86_64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | ff789ccc5720f423d13248cefcbeda5109c32b52d996542cfc5ae4027c4af2f7 |
|
MD5 | 3730b4a0ded866ba18160ef742f4f978 |
|
BLAKE2b-256 | 31a51251c06628dfea56918d69c533ec14cb38b12c34a0f084b7ae03c632cdfc |
Hashes for python_prtree-0.3.1-cp36-cp36m-macosx_10_9_x86_64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 69dd1d221caaf088bfd1e2e4bd64b4321b2b266a447e5557ff2ee943b15cab97 |
|
MD5 | 8e35c128614b50a5f6d262e64fb57f98 |
|
BLAKE2b-256 | 71f4a66de306c73aed57d6d438a90278dfdf1c1393b7e4456b7e8a3990cb8d04 |
Hashes for python_prtree-0.3.1-cp35-cp35m-win_amd64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 49571eac51e3fb3e377c2310fd3f81cc133391214b0a1de1208194408e92854c |
|
MD5 | 86e45880069618fbe187bd1d6efac515 |
|
BLAKE2b-256 | bb081ff365b5bf4f65eee1777dd6f78ea05db2368c8252943df91ce78f5b6a2f |
Hashes for python_prtree-0.3.1-cp35-cp35m-manylinux2014_x86_64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | ddcf27c66affbf5df6d393b1b3ef02645f4f9838cccf0173b9200359681beae2 |
|
MD5 | d917544920e5ffd6dbb3602daef0d251 |
|
BLAKE2b-256 | 1d51f609ae67ca43675f898aa0658658509b874b0e49a53064e66ac11309c5fa |
Hashes for python_prtree-0.3.1-cp35-cp35m-macosx_10_9_x86_64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 5e317d06a180eeb7b4d3fb03655d3528c190ea388c7d7c4ae9284efc11659e4a |
|
MD5 | 9d1c883f72b161a03bf68002dc6c396d |
|
BLAKE2b-256 | 751caca826b2bac328ae3d50aa046af3b6bc3bee4abd6653ac4eb84f0cc46be2 |