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)insert
anderase
(but not yet optimized)rebuild
with already given data since>=0.5.0
.- For better performance when too many insert/erase operations are called since.
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
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, 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]]
New features and Changes
python-prtree>=0.5.0
- [CRUTIAL] Changed the input order from (xmin, xmax, ymin, ymax, ...) to (xmin, ymin, xmax, 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.0-cp39-cp39-win_amd64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | cc397718ffb734f31ef21ba4f7b17c1b4263c5c0430782b126eed1f919148c6b |
|
MD5 | cf84b720b580ec829259a6e296101c61 |
|
BLAKE2b-256 | 66f1bef883d974ecbaa7ae784e8dfdc9a15e31217c744201c0f6e495a5d96dd7 |
Hashes for python_prtree-0.5.0-cp39-cp39-manylinux_2_17_x86_64.manylinux2014_x86_64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 862767835906c50592962d4ea37bd221191c7a9c707345bec19529b5fbbdfa17 |
|
MD5 | ff1d961a294b08fb1d243b1e8110400b |
|
BLAKE2b-256 | 312ebec093f2a7446a535c3c32ec74829796caa040b3986826e2b99793bb6f35 |
Hashes for python_prtree-0.5.0-cp39-cp39-manylinux_2_17_aarch64.manylinux2014_aarch64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | a992ef6fc6031d02749e3d58b0d3a813dac3f7453a141ce2fae28b6a4b0b7986 |
|
MD5 | 5b407b10dd9328f1c968707b8f135a39 |
|
BLAKE2b-256 | 0b6ba7ccafe69c9529fea8273f373da3f0d0687341cba265dce57d0e25c9783d |
Hashes for python_prtree-0.5.0-cp39-cp39-macosx_10_9_x86_64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | c3589d055f06efb8c4e11cd419a5354ff919884d362d378506358c5e00b9399b |
|
MD5 | 219820932d527d12501a1606f85608ea |
|
BLAKE2b-256 | 7967b8a40e4437d0f535245762b6abfd26dc355daef4d532aae294b86282ec7d |
Hashes for python_prtree-0.5.0-cp38-cp38-win_amd64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 694fd23dd5a161b842d06888a270c8b112a4d320d4a62059d0e7e8258225e494 |
|
MD5 | 7a241a1d8bcd78bbb7c21039d1da2df4 |
|
BLAKE2b-256 | 5ee757d03f155c13fa9bbc673d20f1a5ec1cfb1f89045f36b8aad36661e0523d |
Hashes for python_prtree-0.5.0-cp38-cp38-manylinux_2_17_x86_64.manylinux2014_x86_64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 103b2446915c6abac52c48ab1b0a1ae92bd5c6e7ca547b17b64383b7e1994f1f |
|
MD5 | b1fea4c9bc26516ee74e5ce773c20619 |
|
BLAKE2b-256 | 692ddb55be3c0dad2699fc10cadd4c4bb1f7625b1b79ee7c92330a1b71006f26 |
Hashes for python_prtree-0.5.0-cp38-cp38-manylinux_2_17_aarch64.manylinux2014_aarch64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | b46f881a204fbaf102dec47b07da30b15c47e058652f773c9fa02c90ef1e8c27 |
|
MD5 | a0abe5ae63df1704c74c29b76319d7ac |
|
BLAKE2b-256 | 5777db6044d14834192285172a065b8c53026426bb9f1691dd312e2016180176 |
Hashes for python_prtree-0.5.0-cp38-cp38-macosx_10_9_x86_64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 289c1da891c107c70d7e522c111fa9d25b7f316302082d1da7fb1ff282d6c6a1 |
|
MD5 | 44cd5ba5a7ae1fe410b6074147db0a00 |
|
BLAKE2b-256 | 9abe2009a5ef9fe98ef3919dca4e5570bab126f7bf5bae107ca6c2988d7e816c |
Hashes for python_prtree-0.5.0-cp37-cp37m-win_amd64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 7277bcfac58982951d51b856cd18da8055ee1d022125a82085065f84dc2aa495 |
|
MD5 | ac35a50061c6a9d8699fad05a167dcb1 |
|
BLAKE2b-256 | 6ae2b080b6b5c98df95703c237a0e41a57333fdbbbb8f105201e1753f12a8c76 |
Hashes for python_prtree-0.5.0-cp37-cp37m-manylinux_2_17_x86_64.manylinux2014_x86_64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 2c0f0fef318f936800d9baccb4951a15abc75366a0f09e04f6ca28da768a231a |
|
MD5 | 5341d63bae10bc55fb2ae3b058666cc2 |
|
BLAKE2b-256 | 94ad12ff8fc7ad24c421d6498df2e7d0704dd760edd6d61ed90ddab4ab3f57a6 |
Hashes for python_prtree-0.5.0-cp37-cp37m-manylinux_2_17_aarch64.manylinux2014_aarch64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | d736d9bd7e2e93bdaa0ade6e7ff6bf859cf9e73258a04308e1ee08a198de0b4b |
|
MD5 | ecc1f7251d50ac38245f6706c6ec4073 |
|
BLAKE2b-256 | 7907620a1485e2b099e2b6268aa927738a8f1556c8a47bb2c993f4b14e317d4c |
Hashes for python_prtree-0.5.0-cp37-cp37m-macosx_10_9_x86_64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | ebcd6935367801cd9fc5f9cc9cd6c7f739b6df5aa0c1ba9d90e3f7568a4026e2 |
|
MD5 | 3d60e133a1cf70dcc7ef222d18186c6e |
|
BLAKE2b-256 | 22247fde18978ac839858183aeea37e46201f17269bd837ccc5d1dd3329becd7 |
Hashes for python_prtree-0.5.0-cp36-cp36m-win_amd64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 50ffce70d1ef183efb5f03c6626561806d4cde6a568d058319180d0d6d6671cf |
|
MD5 | abfc4890ab7dd8ddc9e28fc8314ddb43 |
|
BLAKE2b-256 | 6443f4eee696c26b56fb5bf0cc8faba7d7addddf82861c0ce6009eb3374b385d |
Hashes for python_prtree-0.5.0-cp36-cp36m-manylinux_2_17_x86_64.manylinux2014_x86_64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | bbafc77eb4ada3d18315db428b71a85fc2a7d652ee0053e0525992413d9e2af6 |
|
MD5 | 626ddc47fa6732a0809f4efeac5598f5 |
|
BLAKE2b-256 | fba92f30cc85c67fc5bf733a9e85cbc7a15d55cb2405e62fac05b575530c45cc |
Hashes for python_prtree-0.5.0-cp36-cp36m-manylinux_2_17_aarch64.manylinux2014_aarch64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | b2ecf88a8b3e746d477becfffc853ee1389706fd6f1dc6f1d53dd40e490894f7 |
|
MD5 | 794364176241eabbb9ef2d73958d4734 |
|
BLAKE2b-256 | 601dc453dad17e16101c7eabf5c9d8afcbeeed01ddfe223afa2e84bdadbaf646 |
Hashes for python_prtree-0.5.0-cp36-cp36m-macosx_10_9_x86_64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | d4b074b512a129f95b4fbbae3c30e079fa28059406438c04e33ce6d03f24863d |
|
MD5 | 929b3b5bb7ed873b3a94300c4d308823 |
|
BLAKE2b-256 | 47f11580c3d38d96021a509a9081f607a0b85886e97aa6c6b9c4e37f941f2f1a |