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), an alternative to R-Tree. 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)- Supports Point query with (x, y) in 2D and (x, y, z) in 3D since
>=0.5.1
- Supports Point query with (x, y) in 2D and (x, y, z) in 3D since
insert
anderase
(but not yet optimized)- Fixed a bug that one cannot insert to an empty PRTree at
0.5.0
.
- Fixed a bug that one cannot insert to an empty PRTree at
rebuild
with already given data since>=0.5.0
.- For better performance when too many insert/erase operations are called since.
- The
insert
andquery
methods can now be passed pickable Python objects instead of int64 indexes since>=0.5.2
.- See the example below for more details.
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
A Simple Example
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]]
# Point query
print(prtree.query(0.5, 0.5))
# [1]
print(prtree.query((0.5, 0.5)))
# [1]
New Features and Changes
python-prtree>=0.5.7
You can use PRTree4D.
python-prtree>=0.5.3
- Add compression for pickled objects.
python-prtree>=0.5.2
You can use pickable Python objects instead of int64 indexes for insert
and query
methods:
import numpy as np
from python_prtree import PRTree2D
objs = [{"name": "foo"}, (1, 2, 3)] # must NOT be unique but pickable
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()
for obj, rect in zip(objs, rects):
# keyword argments: bb(bounding box) and obj(object)
prtree.insert(bb=rect, obj=obj)
# returns indexes genereted by incremental rule.
result = prtree.query((0, 0, 1, 1))
print(result)
# [1]
# returns objects when you specify the keyword argment return_obj=True
result = prtree.query((0, 0, 1, 1), return_obj=True)
print(result)
# [{'name': 'foo'}]
python-prtree>=0.5.0
- [CRUTIAL] Changed the input order from (xmin, xmax, ymin, 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.7-cp310-cp310-win_amd64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | c5a78e96cd17cf9b3657a91adb8aed67fff54b433ab72719f5f51cd5da4cbeb4 |
|
MD5 | b2fe0460d2881e37ef75265793ce9b4b |
|
BLAKE2b-256 | 85228c24fe8e292e4298ce64de390b97f2556b44bacba47a45dfb656d4410fe8 |
Hashes for python_prtree-0.5.7-cp310-cp310-manylinux_2_17_x86_64.manylinux2014_x86_64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 09a13b8af7ac00476b1ea60834ec3e1b5020bbb266e4612db83feb8bbffab0e5 |
|
MD5 | 6ee8c062e933e23a16057550a5b30115 |
|
BLAKE2b-256 | a91debcbd4703f2fd4db980b43f711d40711211c7068f627eef2f4607c256c97 |
Hashes for python_prtree-0.5.7-cp310-cp310-manylinux_2_17_aarch64.manylinux2014_aarch64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 8b5b76494815e7ac1b8368b6528acb3c288803d584d7ca8278b076051a12d8e2 |
|
MD5 | 6206b10f4cbedf5b5105798c8f7657cc |
|
BLAKE2b-256 | 1348aafa177a5e1cd25b77f10a23a746376087564f9eb4e430ba3d6aa5510bb0 |
Hashes for python_prtree-0.5.7-cp310-cp310-macosx_11_0_arm64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 1d815fa82f00aa086c6e99fec61fceefe33e3b7767df946dbaf27a98544d8d20 |
|
MD5 | fc1568118f782319316938e18a94e8dc |
|
BLAKE2b-256 | 48340c479ed848e626972435e613a615cbf793e3f2989c76a21bdbc688847bc3 |
Hashes for python_prtree-0.5.7-cp310-cp310-macosx_10_14_x86_64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | a662d1cdfa972e569f3492beb8d3273b737c02bf8dfaac35101b4714395da7d1 |
|
MD5 | 2399cd4aeede52155f239164181045ea |
|
BLAKE2b-256 | 5bbd763e8218bc1fc6646dbe91f15903762a8cdd221532afb1a444ff74647a2f |
Hashes for python_prtree-0.5.7-cp39-cp39-win_amd64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 7a984a9bea40ae3bdf2ad2c54a3aea546f89dddbb3e3a2b6699251f212131212 |
|
MD5 | 5222945193963bf5c877c981748c8f01 |
|
BLAKE2b-256 | 43d816cc4aa74cf55ac06c05314d206f25cac00203ad54aa156466735b7ef7df |
Hashes for python_prtree-0.5.7-cp39-cp39-manylinux_2_17_x86_64.manylinux2014_x86_64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | a3256d33720b89f2f3f20c03ee6417bb19d3047e20feedec4554a8109de63788 |
|
MD5 | 46495e531243bc0641a81c2d47f6eeae |
|
BLAKE2b-256 | 3d0afc9ab3a2a09a84efaa3a6d752982cc8bd00bf4a6670b627e1170ad01acd2 |
Hashes for python_prtree-0.5.7-cp39-cp39-manylinux_2_17_aarch64.manylinux2014_aarch64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 16bbf25da5ba28f1bf6d33a79908314e25e9b0844b3d659d18a08d2960f1f7be |
|
MD5 | b60556b7346f02a74eefc9b594501bc9 |
|
BLAKE2b-256 | 165f0a222b266dbf33baa0f6ece5e608cac48fc9b12385fbf39b67a721a96863 |
Hashes for python_prtree-0.5.7-cp39-cp39-macosx_11_0_arm64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | f1e8dad72227b771350950291620caa7062385cb8d868b6d8ee36af82df64266 |
|
MD5 | bfcd24798014106af33368c9fc3b4e49 |
|
BLAKE2b-256 | 41c2b898a7397db290903f192f760755f0d9fb9bd6c346ce4095c64148758339 |
Hashes for python_prtree-0.5.7-cp39-cp39-macosx_10_14_x86_64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 5f375255ffb5ea7daf7a838d4df7b3180dd82528160a10a7e25a814022a7ffc9 |
|
MD5 | d598c589a1a9e178093ab57a54a80c06 |
|
BLAKE2b-256 | b61722a232e5f1684ca22d6f2afec387c415762098de319e84db82631cdb23f7 |
Hashes for python_prtree-0.5.7-cp38-cp38-win_amd64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | d9d9e889a343820b681c22d5b735a6733b83af5ddd79d6cd40dfc1cd1078abe7 |
|
MD5 | 5e3e072da14acf4886fe929891afaf46 |
|
BLAKE2b-256 | df138aea5306cf864bfcfa086c57a86897518a07860bb5561fb0a40147292bd3 |
Hashes for python_prtree-0.5.7-cp38-cp38-manylinux_2_17_x86_64.manylinux2014_x86_64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | ddee560573dc2237f7387003677f63c69f00e01e47051580f939d22412323ecc |
|
MD5 | 02bcf469dee6c27c80013f991fd3ca94 |
|
BLAKE2b-256 | 387639378f9dd20913a67141f123fdcf94e2ad9cdfe2806b810d383837f7050e |
Hashes for python_prtree-0.5.7-cp38-cp38-manylinux_2_17_aarch64.manylinux2014_aarch64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 5cda284c4ff8450a0b5e12c4cec85f180b127204eb1c5546dd5e219bac9f395a |
|
MD5 | ed3172466eb26da0171e4cd0012a485e |
|
BLAKE2b-256 | 7c9a74f5f2c45bb03d4ffda54329c87455d3494bd46c89216afcd9c09da22d18 |
Hashes for python_prtree-0.5.7-cp38-cp38-macosx_11_0_arm64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 04b72ee6aa1e73980b415750e548a3173bde71234e993f239e7c769b651ab00d |
|
MD5 | 061fd0306a3e2f11a206860216585151 |
|
BLAKE2b-256 | 815b2f5fb8240ad8fdb53372a6af08b6e1ddfeaa3df3d7302d0045d2a1aeccee |
Hashes for python_prtree-0.5.7-cp38-cp38-macosx_10_14_x86_64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 7d193f6b203bfc7fe53da8f2b4fd0b69fb441a31215adf50402d64ec41f50a4c |
|
MD5 | 89dc6d783f88f90ae78a26627f488cb2 |
|
BLAKE2b-256 | 610e13ea394914e3980a4700a4c656363ce238975b51bde82a85288dfd278284 |
Hashes for python_prtree-0.5.7-cp37-cp37m-win_amd64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 1ec44e82f61af1c4724659c2743cb4eea6bd94d3ff28b01c3b910b77ed8a1f7b |
|
MD5 | 4bf408a70b58a4e039893d8012583571 |
|
BLAKE2b-256 | ea0b2a58308c5f1997f77d8c8a4f5210459b63a1252db9e97883ac10b543d8a4 |
Hashes for python_prtree-0.5.7-cp37-cp37m-manylinux_2_17_x86_64.manylinux2014_x86_64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 79acb44414afb0bd524f6b6c0c96dbbab5449b4a42e470b7da0e19441f002252 |
|
MD5 | 6a01e9a66a245244d530dd4de8ffbc4c |
|
BLAKE2b-256 | f24d6dfcd5f1746935908e996bfd752f2e7379b9eda9cb6f3be9eb47336053a9 |
Hashes for python_prtree-0.5.7-cp37-cp37m-manylinux_2_17_aarch64.manylinux2014_aarch64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 9fea8f38fa9020654319d99f406e87a4ea081d6556befded11862ecb60bd58e3 |
|
MD5 | 17e3505f91c24a3a0505f0f1982c3685 |
|
BLAKE2b-256 | 68d1b79ae0222e4a31680e7833d112ec0bcccbd97e46d7def126973e67fcf7e9 |
Hashes for python_prtree-0.5.7-cp37-cp37m-macosx_10_14_x86_64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | ef82f8faf68d865e13ad72bd44f43f8649ecc2ecdc312f0ad1adc203699372c3 |
|
MD5 | d45d55c21d57fe484c2aa6849fa42198 |
|
BLAKE2b-256 | 8ba732376523fa2c325f5b9b1c798a49c899026dd4f1c5cd735d2ec9d11da9eb |
Hashes for python_prtree-0.5.7-cp36-cp36m-win_amd64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | b795cf584bcf13635605f6db9b532a289c23fdf57eb0fd2ba3e6484ee64cc612 |
|
MD5 | c76c2d9af881e8c9962b5a313e0a1892 |
|
BLAKE2b-256 | d3576d6b8cbaf82c01c09636de7f2856a576141ba205aae8a48c51b6a4062da7 |
Hashes for python_prtree-0.5.7-cp36-cp36m-manylinux_2_17_x86_64.manylinux2014_x86_64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | fb0f1130581049408702aa8bfa7246b02bad55bcc4a61d03b0388122c5c55d46 |
|
MD5 | aa9f83b18cd11ec5a0f64aa9ae3fda97 |
|
BLAKE2b-256 | 482be9feb205cbbf6517f8a9d63bec60fba501304d01f7e4874833a3fc885973 |
Hashes for python_prtree-0.5.7-cp36-cp36m-manylinux_2_17_aarch64.manylinux2014_aarch64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 8d8c6c7ee98489e394a260635b821bbb611d1fb628d4493ae0116c01733c72b0 |
|
MD5 | b1d0101a8193c36df1e9f9560d799835 |
|
BLAKE2b-256 | d61dd9b6f68c1944819ffadab2f8c8914e8c50e9db9ddaa7c2d760f2404251bd |
Hashes for python_prtree-0.5.7-cp36-cp36m-macosx_10_14_x86_64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | e9bf2fdeb7ec94d63340c22739cb4ea76076f54668ea5f7506c8016033b5cbff |
|
MD5 | 1aff46859ea0ba5d00857c29f9e0ecd0 |
|
BLAKE2b-256 | adfcdd627bfe25040322c10520afac85f7e6295e7d3a8088a65c132281f1ec2e |