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) / (xmin, xmax, ymin, ymax, zmin, zmax)
- Now supports 3D PRTree with python_prtree>=0.4.0
- 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 PRTree2D
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 = PRTree2D(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.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, 1.0, 0.0, 0.5, 0.0, 0.5],
[1.0, 1.2, 2.5, 3.0, 2.5, 3.0]]) # (xmin, xmax, ymin, ymax, zmin, zmax)
prtree = PRTree3D(idxes, rects) # initial construction
q = np.array([[0.5, 0.6, 0.2, 0.3, 0.2, 0.3],
[0.8, 1.5, 0.5, 3.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')
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
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
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 Distributions
Built Distributions
Hashes for python_prtree-0.4.0-cp39-cp39-win_amd64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 2df2d8cb499fa4a032b05d18910dfbd4c904f687998830cb6cd6b8367dc170f4 |
|
MD5 | 32422b8ebc92d096194ca5647f0422ed |
|
BLAKE2b-256 | d62d262dcbebb26e409a2ab0698a4b0b49924d3d783fa8ca0d8d4e4aa93c7738 |
Hashes for python_prtree-0.4.0-cp39-cp39-manylinux2014_x86_64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 6073219c063210cb26d805e2a4329c7af822e482ddd465be4c5c3a5b34150812 |
|
MD5 | a87a2dc5121bfa97a6c09d67a03897e2 |
|
BLAKE2b-256 | 0f4871677a92559e3a2ee01fe6d5a5a373a4430cccf43f1dafa6c0e512b4da09 |
Hashes for python_prtree-0.4.0-cp39-cp39-macosx_10_9_x86_64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 25b5673c70745fe1d53dec2941bc22b60976223e63fed629e7dd8c3b4b7568a5 |
|
MD5 | 487ef6f906013e2b14105d9768c137bd |
|
BLAKE2b-256 | e8c8bb926df839a6175a1c2996e8c85fa88e34bbc5556a345e3ac183b86fce73 |
Hashes for python_prtree-0.4.0-cp38-cp38-win_amd64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | edc5e907c5f064f20260058205f56e037d36e24158abae8d5428890293b7bad7 |
|
MD5 | dad70bb70dca80f5e2cecafa90ba31a7 |
|
BLAKE2b-256 | f14b0fadd235fdb3e01f93f4d32a958de1eeffe62ea53d705a9a360218726b4f |
Hashes for python_prtree-0.4.0-cp38-cp38-manylinux2014_x86_64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 032c5a80eb78277d3ffbd95f8aee76ff8b2e2cbdd880158900669942ef8bf25a |
|
MD5 | c0d23087e94bc7b6b262d4c63463973e |
|
BLAKE2b-256 | 081d6a0cb9033cb35f1c4399fc1f40c7d6d5622c27a2c34434f61d65072aeef9 |
Hashes for python_prtree-0.4.0-cp38-cp38-macosx_10_9_x86_64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 53add641be87ddf1fce144df132fb072b2c325dbe4728484f141ed1fbcf46e0b |
|
MD5 | 82fef7f10d0db70414910c18a8e4caad |
|
BLAKE2b-256 | 45e93818d9aa300d6556df57660b04f112aa375fff4dfc7cfd196afd1fa25c5a |
Hashes for python_prtree-0.4.0-cp37-cp37m-win_amd64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 293e9431b46e809b4a4c911e07a51a07ab79bedf997182a3a8f24c0a23f18fb6 |
|
MD5 | c71620b0748021af164dbaff031d7b6c |
|
BLAKE2b-256 | 659862c6c3dbf55b9452012aecd1b67134292a71e56feb6542c48b95231d9f02 |
Hashes for python_prtree-0.4.0-cp37-cp37m-manylinux2014_x86_64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | eb5a168454c6e0b901272770ea88c91a8afa19db88920baad09591e893569ec9 |
|
MD5 | 4b2424b9cdf995cc0a8b3b1ebc15c62c |
|
BLAKE2b-256 | cf2dcf691658d6dafa63fa2adf4369424bf9be28a0d76ef67096408afd58a2e0 |
Hashes for python_prtree-0.4.0-cp37-cp37m-macosx_10_9_x86_64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | ccb3b8cd0c8f0ec686882f9a37b827bdac08063c8cc49ee6dfa92c61f0bea72f |
|
MD5 | e5332dd5f5d463b9cfe44104c932caa4 |
|
BLAKE2b-256 | 8fdf2e6f989f16341dceaa7a2347f62167f55bc563a3be981666572693138d5a |
Hashes for python_prtree-0.4.0-cp36-cp36m-win_amd64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 1fe429fb3141dc8b26f23c609ef3d4fcb9a33603f4e602de18015e1100d75664 |
|
MD5 | 2be88d903cf4e916e611e332f5680db3 |
|
BLAKE2b-256 | f7decc1662bd3d30de154a22afd4503b3ba074d4444f09a9b7f01e71c90d1be9 |
Hashes for python_prtree-0.4.0-cp36-cp36m-manylinux2014_x86_64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | b929064606b0d91e9b1722a476e4f16ec113b13a3a2428c42fcb4dac6d74cb8e |
|
MD5 | 637309aaef9ff483df50391be97560dd |
|
BLAKE2b-256 | 333c13df85e4dc60988d5e13f0389264713d8c4ec78d48ec391cad3a6e55b5d3 |
Hashes for python_prtree-0.4.0-cp36-cp36m-macosx_10_9_x86_64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | e68be08c37086c1d5c8ed4293f54deb92609aece9d61bb29e145ad236fb602e2 |
|
MD5 | 3bf096bc961b44814b1f7b03ee351388 |
|
BLAKE2b-256 | f145787b54cb221365619879a797bc73c18138c9cf060e9ac4f837a3f43f0bf7 |
Hashes for python_prtree-0.4.0-cp35-cp35m-win_amd64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | b0aa1ecede2b01855d8d97442194ab569fbf09d786e085b120e0d1a523b41a5a |
|
MD5 | 4f3f616667471bc8a41068ff6d24bc98 |
|
BLAKE2b-256 | c9cfef209042d74510e099f688e7b3ae17af941163ff261f85a992e0e2966c78 |
Hashes for python_prtree-0.4.0-cp35-cp35m-manylinux2014_x86_64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | e0a3bd6311b51d1cee26828c899886d325b999ea7b5b4cb18786951c971b7286 |
|
MD5 | 57322565b91bfbe9a36e0cd180475580 |
|
BLAKE2b-256 | 685d1ce617c179f87322154b1612823ff4a9ddec0204ddfd3ada518ffbeac485 |