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.
PRTree2D
,PRTree3D
andPRTree4D
(2D, 3D and 4D respectively)
insert
anderase
- The
insert
method can be passed pickable Python objects instead of int64 indexes.
- The
query
andbatch_query
batch_query
is parallelized bystd::thread
and is much faster than thequery
method.- The
query
method has an optional keyword argumentreturn_obj
; ifreturn_obj=True
, a Python object is returned.
rebuild
- It improves performance when many insert/delete operations are called since the last rebuild.
- Note that if the size changes more than 1.5 times, the insert/erase method also performs
rebuild
.
This package is mainly for mostly static situations where insertion and deletion events rarely occur.
Installation
You can install python_prtree with the pip command:
pip install python-prtree
If the pip installation does not work, 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
Examples
import numpy as np
from python_prtree import PRTree2D
idxes = np.array([1, 2])
# rects is a list of (xmin, ymin, xmax, ymax)
rects = np.array([[0.0, 0.0, 1.0, 0.5],
[1.0, 1.5, 1.2, 3.0]])
prtree = PRTree2D(idxes, rects)
# batch query
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 by insert method,
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]]
# Plus, you can erase by an index.
prtree.erase(2)
result = prtree.batch_query(q)
print(result)
# [[1], [1, 3]]
# Non-batch query is also supported.
print(prtree.query([0.5, 0.5, 1.0, 1.0]))
# [1, 3]
# Point query is also supported.
print(prtree.query([0.5, 0.5]))
# [1]
print(prtree.query(0.5, 0.5)) # 1d-array
# [1]
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]])
prtree = PRTree2D()
for obj, rect in zip(objs, rects):
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'}]
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.1, 0.5, 0.2])) # add a new rectangle to the PRTree
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 that cross-version compatibility is NOT guaranteed, so please reconstruct your tree when you update this package.
Performance
Construction
2d
3d
Query and batch query
2d
3d
Delete and insert
2d
3d
New Features and Changes
python-prtree>=0.5.8
- The insert method has been improved to select the node with the smallest mbb expansion.
- The erase method now also executes rebuild when the size changes by a factor of 1.5 or more.
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:
python-prtree>=0.5.0
- Changed the input order from (xmin, xmax, ymin, ymax, ...) to (xmin, ymin, xmax, ymax, ...).
- Added rebuild method to build the PRTree from scratch using the already given data.
- Fixed a bug that prevented insertion into an empty PRTree.
python-prtree>=0.4.0
- You can use PRTree3D:
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.6.1-cp312-cp312-win_amd64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | ba00a5dcca9a0ccfe73a59c5396403f1278f35aeed98274338b666a94c1fc43f |
|
MD5 | 87bbb76a1396f2f2727c2b4b055bf5da |
|
BLAKE2b-256 | c9c83304ebcd006adbae373595652d2a7f6f74506d5dbefa7f380aa9f50d6931 |
Hashes for python_prtree-0.6.1-cp312-cp312-manylinux_2_17_x86_64.manylinux2014_x86_64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | c55c1a945d1008f0236668e4d5657586573f5f0153e6d89ce2527c6513fa30b3 |
|
MD5 | 17b76e4ec534f86791fcbd35ff727e26 |
|
BLAKE2b-256 | be16729605b9e3fdf825ecd90287f1f063c1906d08f457cde4eb00a2610ef619 |
Hashes for python_prtree-0.6.1-cp312-cp312-manylinux_2_17_aarch64.manylinux2014_aarch64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | b26b4762028e4877c3c4e862b3ccee5aead8984b186039d5b179b6b4eeedb724 |
|
MD5 | 69d245fca3c58aac7210cac61dd8e482 |
|
BLAKE2b-256 | f017d72643ff2b6e6a76c9c5edb0263a147e806537b40a40aac6fea5e4ff1c3e |
Hashes for python_prtree-0.6.1-cp312-cp312-macosx_11_0_arm64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | a5d0caf1267dc1dba426fae57ce62892316e06ba245199625bb624dcb63eeaa4 |
|
MD5 | 078e123a7644b0ac80508246c1d1238c |
|
BLAKE2b-256 | e1b98d178a2a77e26ab8dcc9b74368dedba8a66373c3dcfc7db45e812139cb8a |
Hashes for python_prtree-0.6.1-cp312-cp312-macosx_10_14_x86_64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | dda032b0a05d72e8642ecf1de264f5768bff856c5face7964f746f12b89739c7 |
|
MD5 | b63d20d9f125503ca5017a19aee5b7c4 |
|
BLAKE2b-256 | 0e70c50c9f7495e0d42899b4433105ed833a614eeed894e16d31ae4c8da7aa42 |
Hashes for python_prtree-0.6.1-cp311-cp311-win_amd64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 096e66ab9498f143e527d7faea801e3ede5e8f224e7e09588ef67ab5a6da0a9c |
|
MD5 | c36020c0d70e4d0894b838c6db31a212 |
|
BLAKE2b-256 | 73495bebe9f8ed551b682623b6acd6af5450f99f20b618e00969b35295a2f694 |
Hashes for python_prtree-0.6.1-cp311-cp311-manylinux_2_17_x86_64.manylinux2014_x86_64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 029f4791dbc8fb0fd6e6a6becfc59bc03f9dc86e5f120f121e3a30750f84476a |
|
MD5 | bba52c3d45997c62ee97adc081fe7f60 |
|
BLAKE2b-256 | 9ea7a389448267dab689045d0411c98e81c84cfe4b34e0fdcf90a57dba8f824a |
Hashes for python_prtree-0.6.1-cp311-cp311-manylinux_2_17_aarch64.manylinux2014_aarch64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 31691b885ca3dc1b0a5f10603eab60e802be7fd99eaf36c138f893d54f0ccc8b |
|
MD5 | 70c56ee6108edbb4079669b9cc688841 |
|
BLAKE2b-256 | e0c5a4b199cf589345114506be0ab77fa28cc2a8f606af60fc5f595ff65877f3 |
Hashes for python_prtree-0.6.1-cp311-cp311-macosx_11_0_arm64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | cfc1f15ffccef869f7ceae2e719480f6ebac49986ee54e7a57308c1672a569df |
|
MD5 | 927bb60b211b509d060663896d68253e |
|
BLAKE2b-256 | 202f69ee7a648bdd7e87f50481a2be683ef52f39788988bf674d663e6f231569 |
Hashes for python_prtree-0.6.1-cp311-cp311-macosx_10_14_x86_64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 0c12d089cde1c0421241a9f8682e4b3d3d93e7fd22418054aefc5398d01a71e7 |
|
MD5 | 69f86c4a5e2fd33fbb0b2e50b382c1f1 |
|
BLAKE2b-256 | cb3889e25a075dc38e9755ec0cc7b75c656f41239da457f76e4787a748a5b274 |
Hashes for python_prtree-0.6.1-cp310-cp310-win_amd64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 5f677b1504d54fe434257727b3d1ff2e9457a9da218a17ae5c69928ea3cee367 |
|
MD5 | e01d87d423d1a32dfcc06f94f5f8cdab |
|
BLAKE2b-256 | 460880fcb1a992bf467d261d6e51549012a463daffc59ef365df8d6c5f767fda |
Hashes for python_prtree-0.6.1-cp310-cp310-manylinux_2_17_x86_64.manylinux2014_x86_64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 4b77f1caba35421e62b8d7c59fe73c4d6d1b6b752da0a46a557b8c7587a04ead |
|
MD5 | d341c561c84f0444ca66d7e9985728aa |
|
BLAKE2b-256 | 3156f169d783c01ac97d107084238c0b41c3021694624dc0a8719816f1b1fdf9 |
Hashes for python_prtree-0.6.1-cp310-cp310-manylinux_2_17_aarch64.manylinux2014_aarch64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 6fffd416bf08c064aba9db1e62ef754b3884e3ebc069d4b2f4be606dc6e99172 |
|
MD5 | 37198b4e6e81f1d768eca18d4b214afa |
|
BLAKE2b-256 | 2057e95090f5ad2084f91591f0c3db5bc527a36f32fcb4e7af99dd88a776cbde |
Hashes for python_prtree-0.6.1-cp310-cp310-macosx_11_0_arm64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | ffb0522d25bcaa2dee2db3e9000c0f233c5439fa9b508be7cb49aab7b2c5eb7b |
|
MD5 | 235bdb9e675cb6240fc1c198617ef6a8 |
|
BLAKE2b-256 | 3ecbf4b55e4befa9c198831df7d0cb3ca5e9e73ce3e24161f5bf74ce696b3489 |
Hashes for python_prtree-0.6.1-cp310-cp310-macosx_10_14_x86_64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 33c1b07873433ae4a4f936420f694d82541f7e7ff5c5b0abdcc85482684f5e75 |
|
MD5 | 1b580d1f344eef1515578ab1b58b60bd |
|
BLAKE2b-256 | 7af50cb4a786ac259a60641ec2b5bdefb0065403c193643f13aa41f5330287f5 |
Hashes for python_prtree-0.6.1-cp39-cp39-win_amd64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | d755ab0b6dab7b07bfa725f9217e892f8d7974bcc96ae6d34ca36c42eaa641b2 |
|
MD5 | bcea0bf7dfdef4013357425dfd17251a |
|
BLAKE2b-256 | 2950e8d5a7203acae2cd84a346fa5c638a7c2a938f26e0d813cfe97f63702ea4 |
Hashes for python_prtree-0.6.1-cp39-cp39-manylinux_2_17_x86_64.manylinux2014_x86_64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | df3a6b006681d36e24c2a7740602debceb8dcd8e1d68f2286fc9fdb39ded0407 |
|
MD5 | 039f9cdbf47c4829d4b5b2abf6f4a10e |
|
BLAKE2b-256 | 3837ee33d96fd588b3ccc4f5252892de8233dc7c972d134de314220423b903d0 |
Hashes for python_prtree-0.6.1-cp39-cp39-manylinux_2_17_aarch64.manylinux2014_aarch64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | ffce169a8988c5e391efdb1168d3cda1ef42daa9a11006af3068c94b7f094386 |
|
MD5 | c3a224202bea44d88babe2472b78c180 |
|
BLAKE2b-256 | 3a754af06e5040372054f7036c0393cf40ef500c778a6518925c35fe66a170e4 |
Hashes for python_prtree-0.6.1-cp39-cp39-macosx_11_0_arm64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | b349deaf525d77d8f6a9a773d2cbe80bebc948a12cb2a30916a7e4e607092787 |
|
MD5 | 3de97f607c45fe154e1a99d0aa030acc |
|
BLAKE2b-256 | cfb8e45d05c064629e24a4a274cce75f035d62417f9ff4129ca30fcb4c9b6093 |
Hashes for python_prtree-0.6.1-cp39-cp39-macosx_10_14_x86_64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | b2104de3dfd9e489331fc9c1d61db6656d2b31a634cdcfffe96f82006490b7f7 |
|
MD5 | dff9653c99627b8e3a2bc730baed84a9 |
|
BLAKE2b-256 | 45ebcfd06c0860cccefccd34802ef1d622e2ad416aa6193dae00d2d8db2cc4c0 |
Hashes for python_prtree-0.6.1-cp38-cp38-win_amd64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 992009e6123ff24ea5d7d9a3469670535cc6328392fdead891a47cb786ddf826 |
|
MD5 | 84473b8a2eaadcd94809d497b78481d5 |
|
BLAKE2b-256 | 9f0ed2901d2b5c75644010dab6fa5829b551b00be7b190dc6fb541eef5d0f6c2 |
Hashes for python_prtree-0.6.1-cp38-cp38-manylinux_2_17_x86_64.manylinux2014_x86_64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | ee8a2ae3d68470b5d63c97ac5af0e7d69e26097a1bdbcfcfd5eb822aaef138b2 |
|
MD5 | 94ddf0991e5c0d1cf62de9cb96a67fee |
|
BLAKE2b-256 | 5c6f3e7cdadddc78a381d352539ee319e26a37e744d736270986f7af19d8374f |
Hashes for python_prtree-0.6.1-cp38-cp38-manylinux_2_17_aarch64.manylinux2014_aarch64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | add3b6456d79d4e17ff9854dd70ca3498f765df190e79568f41633d29cd51572 |
|
MD5 | ea9a0526e687522d949e6682c2f44f7f |
|
BLAKE2b-256 | c286d58343c3c69ab15f13cac484594d310134b2345f842f5e4746d2af996f2a |
Hashes for python_prtree-0.6.1-cp38-cp38-macosx_11_0_arm64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 0995da325fa5093452748bc393005c54c8d044d34244cb101117e747fc2919c8 |
|
MD5 | 3c2bc7f0dfdaf27d4f3459de75ddc7ea |
|
BLAKE2b-256 | b175e710cf1a3b5617a410757ea63fb82c0abfa20e7dc712b9bd105f8b3681b8 |
Hashes for python_prtree-0.6.1-cp38-cp38-macosx_10_14_x86_64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | a96f98242503c77251262aa15c76556de9eae52d5377efce4d664a3c3721a199 |
|
MD5 | 475abd5c952404cf62b7e3c9b2934e63 |
|
BLAKE2b-256 | 1a8dd5d9c7a6436e073ad224eef715dd6e755f68b2237b59a8e430bcdd736d64 |
Hashes for python_prtree-0.6.1-cp37-cp37m-win_amd64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 253bf93fe186485274558ce348e2412244817490f7aa73c0d60c4921982c319d |
|
MD5 | 3324e3abecfa3166c08e5971800bf0a6 |
|
BLAKE2b-256 | ee1022a053931e90aff01dbe56c10102e99250c3353c34b0db214c69f41a16c2 |
Hashes for python_prtree-0.6.1-cp37-cp37m-manylinux_2_17_x86_64.manylinux2014_x86_64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 0c5f456ffd302c835fb5bd99dc20dbf2de07fc2df4dafabe5e51cdde082a964b |
|
MD5 | 4e147b39a1d5516d5181eaad8b3d6647 |
|
BLAKE2b-256 | 05136ae9dc3627f1e66b93849af15cab98c49faaa11d31ae7246f48a74207aec |
Hashes for python_prtree-0.6.1-cp37-cp37m-manylinux_2_17_aarch64.manylinux2014_aarch64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 55b26311b9e2881e8d1535db8be8dad16b3fbc8a2b18ae0900097a4935d6b844 |
|
MD5 | 05d00518fe71d84a9da4dbe6300cc3ba |
|
BLAKE2b-256 | b370a92f77af258eb6e02976d771da013e46ef9d9724344f7f23570a2a6c6bc9 |
Hashes for python_prtree-0.6.1-cp37-cp37m-macosx_10_14_x86_64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | aee367dcce419a7defe512f70b5415589f6f04464f5b56a95e72ce31d3385530 |
|
MD5 | 0f092204823d6e0da2dd30f49af69f0c |
|
BLAKE2b-256 | bd1a0b605dc9d2da90f8b4f177b77ee0177d529da7ba71c70ff629ab2a0470ee |
Hashes for python_prtree-0.6.1-cp36-cp36m-win_amd64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 484b6d1edd00ba8d534afc924380f138bfcc5d4db4a7aeff4691dc943da06f93 |
|
MD5 | f984a4dfa96c4d3521612bc29f5bfda0 |
|
BLAKE2b-256 | 39196fcb7ce6512186dc925abf28db5910516542572b40fceee7f51a234f9e23 |
Hashes for python_prtree-0.6.1-cp36-cp36m-manylinux_2_17_x86_64.manylinux2014_x86_64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 16ac6c32a497cf8416938222a246b7dc5974cd33760ea5499ff91496217a976b |
|
MD5 | 9a2d808f36bd91f7095aa0bc6ebc83b6 |
|
BLAKE2b-256 | 9a35da17fbfb8ebee7d026343b2ac99bfb1cc39309f3191130886db01282e4ae |
Hashes for python_prtree-0.6.1-cp36-cp36m-manylinux_2_17_aarch64.manylinux2014_aarch64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | f5e4bb3950d79b319805f1dbb362cd074bd349c54fc66e4cb2a73bfe3dd6468b |
|
MD5 | 61bcb4c0764b0151c9bd45bd795cdfb3 |
|
BLAKE2b-256 | 7bdf5201878e6911ef23808369fc1b426615e8360f7d47350b06c64f9193f9c7 |
Hashes for python_prtree-0.6.1-cp36-cp36m-macosx_10_14_x86_64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | f1555d4e4cdafd4822234398ba5c8c88ddac412f4c5d937d3f7d1f220931038a |
|
MD5 | 5c31f7401ea438af8452208b11e9688d |
|
BLAKE2b-256 | 5b98adc5bdfeaafee317ee128952a8de421f7145936b5eb1cea91670a5d82885 |