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 it uses 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.5-cp38-cp38-win_amd64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 3c18eb04112de43a40cb6925da4c97a57b6e352b44a90e07d318b3b01e649495 |
|
MD5 | abcb1fa03552a58aeacc379ac6aab161 |
|
BLAKE2b-256 | 7d55d581f2aef2969d3001c1d87b716d1d6651fe11e4ac2db02296164feb46bb |
Hashes for python_prtree-0.3.5-cp38-cp38-manylinux2014_x86_64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | f098ad0b1dc1681ae5a09e120fa61864f898aee7b79106160e5d485f036f1dcd |
|
MD5 | 7996ef9f1e2fb1acc6454cd25e208e9b |
|
BLAKE2b-256 | 5028a9ba6e249bc9eaf6c23a3ef24a27e400c66434e7ea2a142192104ce078ff |
Hashes for python_prtree-0.3.5-cp38-cp38-macosx_10_9_x86_64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 2865d5304e2040cf402b05ea97b2508324533264d002e1d349809e95fbf5d474 |
|
MD5 | ab6b8bfad976fe8c87bf717623e083d5 |
|
BLAKE2b-256 | 6f717e5a265d06ea5ec5eb48670c62fa5e0e2b3acdcc98cba835d044795d532d |
Hashes for python_prtree-0.3.5-cp37-cp37m-win_amd64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 9af310fbf9825c1d9608900a0106a3db1450317a78ec0e20dab5ae5d9ea522b3 |
|
MD5 | 19bf86dc8b96088cb8144e3d6759e550 |
|
BLAKE2b-256 | 61a52d2bf6d1e3c59a4bcdd9b3af1090649df951d6d0a165ee46c6c5c9785ad9 |
Hashes for python_prtree-0.3.5-cp37-cp37m-manylinux2014_x86_64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 7e8d871113f161d9bca957a600c2c33218f9e8f1304967fcf667aa0cb8936934 |
|
MD5 | 8e72c9d47a88ab432e24ec8ef908a8ec |
|
BLAKE2b-256 | a49ddbffe553faf59bae46c203b8196583e94e44b13002abe3ab89039b0bc8ae |
Hashes for python_prtree-0.3.5-cp37-cp37m-macosx_10_9_x86_64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 15bb0e25c23ae6ed3165cc22f873d9fe9906b293265d4b435fd559672a53daa0 |
|
MD5 | ca71ebc03863db81a176cd906f059ecb |
|
BLAKE2b-256 | d3301c5ad7e72bd3aba1d84849763230a8ef6154591e23e2fbdae4ebc2d2679d |
Hashes for python_prtree-0.3.5-cp36-cp36m-win_amd64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 3aef8072a033e6b8b735510433fd9d34068e874234a27e887d88b9bf5f9ea264 |
|
MD5 | b9c5e607f2c4f85d4293ec0f0f4666f7 |
|
BLAKE2b-256 | 7e5a2cf01598a88f1178df77098839bfba1b2a3c53acb352f5e6fa465822115c |
Hashes for python_prtree-0.3.5-cp36-cp36m-manylinux2014_x86_64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 7f146680e401a925010d4d00de10721576e4966ffe6c836850ff0d66b9c1589b |
|
MD5 | f4759e00362b7ebc528204b1c16af3bb |
|
BLAKE2b-256 | 7e9bda4e3d69b5df2766250b7bdd2e6b3575934248484172d826d7317637781d |
Hashes for python_prtree-0.3.5-cp36-cp36m-macosx_10_9_x86_64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 516790069690b8695df430985e697933eefd994fb1a55a42553c86de94d35e74 |
|
MD5 | bbf39f0a64c150bfa2c5cb0e131014fd |
|
BLAKE2b-256 | e39c18a228406eafd6067a646de58a4359b1430e14b154ee0ad60d4252e935ac |
Hashes for python_prtree-0.3.5-cp35-cp35m-win_amd64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | dc33634d98d03389881809a8c902182186645dc978c7008022bb21043f233d72 |
|
MD5 | 153a13f2b5059481fb2c7311b558801f |
|
BLAKE2b-256 | 40b2ce14f4167119cc654d87d3a7502eb41093a1f0e3d9c3832cacda40c1723c |
Hashes for python_prtree-0.3.5-cp35-cp35m-manylinux2014_x86_64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 3450434a242a081a0a4930d86b841ea8b1dcad5d8b604f3ff9a326675edd2967 |
|
MD5 | 84ca19cb8ff0a71dea0021d0169c20d9 |
|
BLAKE2b-256 | b4c04a65ea7557c33e8ace29aed8cc35e9add39793413df92b046d5721157bb8 |
Hashes for python_prtree-0.3.5-cp35-cp35m-macosx_10_9_x86_64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 719bb8f5c8a23174a0ba32ad6a484583d0585d568be3fd4b400a93413d20ad65 |
|
MD5 | d40105cc7525b4cce6800a04734f4e1b |
|
BLAKE2b-256 | e864fca080501659779463358b1c3c94d18b4884e467022185f155301ba6d9b6 |