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; array of (xmin, xmax, ymin, ymax)
- query and batch query with 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., mapmatching).
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]]
1d-array batch query will be implicitly treated as 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 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 git+https://github.com/atksh/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
For APPLE USERS
Please, make sure that cmake and openmp are installed, or copy and paste this command
brew install cmake libomp
then, you can install by pip.
Performance
Construction
Query and batch query
Delete and insert
Requirement
- numpy
- openmp
- cmake
NOTE
- This PRTree is implemented by C++ with Pybind11, and much faster than numba implementation of PRTree.
- mimalloc could allow us to get better performance (1.5x ~ 2.0x).
- If you can use C++, you should use boost::geometry (I didn't 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.1.1-cp38-cp38-win_amd64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 754722e7a6ccb7538e9f922a2f38a14d1fb0bc619b2997db89ebd34153ee58ac |
|
MD5 | 3a47990fb6ece4e350ba75432d26e0fe |
|
BLAKE2b-256 | f0bb64c033bf9a8d2ebed8d8a529d6d6dcf13eb0b7131d80143b2e4d84db8696 |
Hashes for python_prtree-0.1.1-cp38-cp38-win32.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 02166c648acac66c9c44721b502ce191b281129009464aa9fddfced44242d204 |
|
MD5 | 469067b422db598f23a07cd19f8dcfbc |
|
BLAKE2b-256 | fbe09ae0fae34f94839af8934564da4e33197841575e45af50b65a47f6bdc257 |
Hashes for python_prtree-0.1.1-cp38-cp38-manylinux2010_x86_64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 26984923b2683a42c42b1e49dbfad274c80713b960f77bdedf75575b5c2142b1 |
|
MD5 | 531d2122641be57786116f4903507ac3 |
|
BLAKE2b-256 | a6680de714d83610150bbfadda790811e93e771750f07fb2646ea77cc63e8e1a |
Hashes for python_prtree-0.1.1-cp38-cp38-macosx_10_9_x86_64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 773d92caf7d225a9d8c63b092897dfef4cf7b5ea148ab47723ce533c504b2f79 |
|
MD5 | 4a5d17387747e8c0460ea8d364290567 |
|
BLAKE2b-256 | 68c36e90d3f1e1bd9e80e4a288cf89e3cf2cb560676232ed58a35862b1fe1609 |
Hashes for python_prtree-0.1.1-cp37-cp37m-win_amd64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 6399c6cf0e639123cd8cf5a97c47738d0e46b41f36122c210cc5caa4be6d7cc7 |
|
MD5 | f1d5d2b3a2cf6569344e40c97553a3e9 |
|
BLAKE2b-256 | 7626970755a1f70ba300f4c050cca2a317e40408297af04fb38e32e3643b8c43 |
Hashes for python_prtree-0.1.1-cp37-cp37m-win32.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | b29c6b50e7bc2041a89d592dde5f9d8a86359b94e215a45e4e68f9055355d9a3 |
|
MD5 | a09bd774df2e40a92acf22bfbdd6cc0e |
|
BLAKE2b-256 | c295b3f10f912c0758c2568db6920142dd1daa7ad6af9b62eb88d44adc24e157 |
Hashes for python_prtree-0.1.1-cp37-cp37m-manylinux2010_x86_64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 4fc55992c59c6ed53499a67d6afcc27c6c3625e4b86a2d6d4f4b5d3d813fce50 |
|
MD5 | c235fe91f88acebbc7851b8fbd21971a |
|
BLAKE2b-256 | 55b98f6bc71130cc85aeea06646bdb8a674b0adcd8995135c599c6e26e0b6f99 |
Hashes for python_prtree-0.1.1-cp37-cp37m-macosx_10_9_x86_64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | e9322c96b5e2fc24aaa69112840ea267b38a62a40534bdb73bfadcd7474659dd |
|
MD5 | f0a2b95decd39d61e2157f7761824a87 |
|
BLAKE2b-256 | 232428724e47aa9aae041dcf220f9e5da23727f4382ef3967c01eaf6d9671b0c |
Hashes for python_prtree-0.1.1-cp36-cp36m-win_amd64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 7dcd9238b69470eb7beaf3eef50c0fa999baa0cc4e7fdf018b103586cb2c609c |
|
MD5 | f57d31dca2c587051394b4ba52bee7e1 |
|
BLAKE2b-256 | b41ed83cc3218453a1955903e35262346eb9a309068964e2e98b415dc9f99638 |
Hashes for python_prtree-0.1.1-cp36-cp36m-win32.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 3e957f92906e5536f13e77c12b98b6537b7448f7cf4fe2a04d9d25e940a466c1 |
|
MD5 | 4a309df5e9a4afa6eff1e6fcd2f5070e |
|
BLAKE2b-256 | 10dfbcfa2c8775d6cc907d95242cbaaefa4aa79ad96c80362660b83b03ca034c |
Hashes for python_prtree-0.1.1-cp36-cp36m-manylinux2010_x86_64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 02aaa9b686db5dfa92fa2a709f84fe24d15ac82d544c9d0fabc6acf0d9133eb4 |
|
MD5 | 92aa99cfbc9d95f685c70783e2763dba |
|
BLAKE2b-256 | 6bcb1b20cc6157dad38400e9c254a7e71a4410e03ee09d9a022d026ce33356b0 |
Hashes for python_prtree-0.1.1-cp36-cp36m-macosx_10_9_x86_64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | c492973c29f54aeb1d38e70bd17f660047ad80e349e3ecf44a1a17d993e5d004 |
|
MD5 | 26dc189ef0c4422e41d582498eb586e7 |
|
BLAKE2b-256 | 5fccc414443827a39999d3d5661eb0aae7777a419ae9f36903614a62e964411d |
Hashes for python_prtree-0.1.1-cp35-cp35m-win_amd64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 6acdd32ee34c57aeb9d463c1b843362b9314fecb54204ac305cd57063340937f |
|
MD5 | 9b8f4af2ed14e93db7a4c99d04e32b5a |
|
BLAKE2b-256 | f4deb28b892dba73decf340bd3845a6c31d07a1a1e8df1e0dc42c0375b2a4a03 |
Hashes for python_prtree-0.1.1-cp35-cp35m-win32.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 97fc80384d37a26e874d8ef740febab1ac904ac85ae2dd47bebdf0877632c2a9 |
|
MD5 | 6541222639758c1c7f6495155fb427d3 |
|
BLAKE2b-256 | 06114d0aa9a0ef51b015f66c3fc1c4811baa6542133a0b929ae2e761a9b6a841 |
Hashes for python_prtree-0.1.1-cp35-cp35m-manylinux2010_x86_64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | afb1aff94f9c1628acb0df998fbf46c1433813bc65fb5b66236036c52305c6db |
|
MD5 | 69b182a9e964dc3649a7d0fc01b7e436 |
|
BLAKE2b-256 | c50e1be7f8bd891083e787c7f99816a2199b2f8b90b2b53e563cf71f93a13fa6 |
Hashes for python_prtree-0.1.1-cp35-cp35m-macosx_10_9_x86_64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 7f3d03b07c8d502f7ac383ee73b737533d9521ec36d7953acafb2fa4a1f2607c |
|
MD5 | bea57b8bc68fab8c3cb1445c267a3234 |
|
BLAKE2b-256 | d62f1ff10c388a99bf8d6801a1c4e5f5e593ba914422cafb739f0c205ff33bbc |