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)- 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.3
- Add gzip 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.4-cp39-cp39-win_amd64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 78168f1b3ddefa9645bdd64f6769ce52ab7c8a98ff755b8300625c71f0c030dc |
|
MD5 | 6701611e0fd61872b4a14db3c7661ed2 |
|
BLAKE2b-256 | 52ea60b80e9f307868b94f52c732a127b483c0424f7805e58aa006c605309245 |
Hashes for python_prtree-0.5.4-cp39-cp39-manylinux_2_17_x86_64.manylinux2014_x86_64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | f12e02f4a22d4f91b4bda7a02aa8b4e02742f10f28bae0067494b13a3d9fcf73 |
|
MD5 | b34ced9e2695c552e16f8a25671355a8 |
|
BLAKE2b-256 | 64ef1038877360093702d8981198b539075df7542ff566238e50da2494909e05 |
Hashes for python_prtree-0.5.4-cp39-cp39-manylinux_2_17_aarch64.manylinux2014_aarch64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | fd7a7f5104e1c4a159768172079aac88c5a4e51bd0399609d35fe9687e9a5f51 |
|
MD5 | 69e6ff7e54f376956f6db79bb39bfa3f |
|
BLAKE2b-256 | 7fbe6c23b7660fa8a5ddab22fa5d19e877c800e19cab354cdb80d70cba288311 |
Hashes for python_prtree-0.5.4-cp39-cp39-macosx_10_15_x86_64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | d038a5ce21eea55973b5db5a9a9db5ff22bf8ea4de9ffa035d77da5dc4133bd4 |
|
MD5 | 1241822f261df26a52b6aa86bbf7b738 |
|
BLAKE2b-256 | c753253c9fd4f55f8d6378c6d9e44eec8ea46cb1e2f2171c82f3d893941db3bf |
Hashes for python_prtree-0.5.4-cp38-cp38-win_amd64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 0c5f171806189f35b69d9997229ed19d3eee375d398df11215a2d848985bfd13 |
|
MD5 | f5e3b335fed22a08c99b9025ab8ebc7a |
|
BLAKE2b-256 | c943affe2bcca9e4e4c35cd5c38de2b6d3a37b8fffc208e3157e0880a4e6ec41 |
Hashes for python_prtree-0.5.4-cp38-cp38-manylinux_2_17_x86_64.manylinux2014_x86_64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 999350996d416b53b060cbfae4cf966e60e121b0d1f017020115a9da52a93d40 |
|
MD5 | 23cb3fb5158a655f1450f560f0518e5d |
|
BLAKE2b-256 | 0c9c85b205e6d0cd1095f8645a2064e5726f87e5adca2ffbdbad602a44211414 |
Hashes for python_prtree-0.5.4-cp38-cp38-manylinux_2_17_aarch64.manylinux2014_aarch64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 88cac5be551c9bd97f0d79a39ac7bdd3a753515e4085491b8bdb43009ca1666b |
|
MD5 | 7a069b32d450f9a27cb169c4f7be8ac9 |
|
BLAKE2b-256 | 5918c175cbc5ce29a021dcadfd99b3d919d46677d9a1f2c645efca78ab08e7a1 |
Hashes for python_prtree-0.5.4-cp38-cp38-macosx_10_15_x86_64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | d0f975257714e451b9da84e21388a07b9232bdeb19cce2a0afe74875315f0eda |
|
MD5 | d88e890d4b135e259c621a8c2c2a52fd |
|
BLAKE2b-256 | c694c534675c1af3ca8312670058105129738603bcaede588986f778747fe341 |
Hashes for python_prtree-0.5.4-cp37-cp37m-win_amd64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 8c531e3d65d55137295c38c3d3c4662643a754e5ec699baaf4be59994642c476 |
|
MD5 | 08aa69634318b22e034d93c6f1007470 |
|
BLAKE2b-256 | bc276a02445e69d585d07f96456d6e68de0507cd2f12c9ae8b6b12ff3b8887cc |
Hashes for python_prtree-0.5.4-cp37-cp37m-manylinux_2_17_x86_64.manylinux2014_x86_64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 82fb9af5230021b4cb55d4ee495e7c3542671643bfe2ace39c444c94ed3083a3 |
|
MD5 | db4641bbecf040076394968675afb712 |
|
BLAKE2b-256 | e69c3cd1012438bc4bc6e456cca8f63060416c3e714242b67c768ba1a34e35c3 |
Hashes for python_prtree-0.5.4-cp37-cp37m-manylinux_2_17_aarch64.manylinux2014_aarch64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | a1b54993b5f4c4df193979f8c188b535f3ece798116e9c1338f365420a9625e5 |
|
MD5 | f74f028506cd9fb371f148bbe3ac112b |
|
BLAKE2b-256 | f357e759560f252e1ff5d4116a1494ac87dab71824f4bdf9ac098860975c0f60 |
Hashes for python_prtree-0.5.4-cp37-cp37m-macosx_10_15_x86_64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 6c4d36808a636d3bc0b900f462d1bedfda467b3d9b0a24fb1bc0fcff8a7f613b |
|
MD5 | 7f76db8ef7db3a12a10075f427408899 |
|
BLAKE2b-256 | 935989fe12bed2658abdedaec4d1f607c756b4dc35ec1bcfafe8115d845c2f4f |
Hashes for python_prtree-0.5.4-cp36-cp36m-win_amd64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | c99062815b1a023b0adf9ea068819374f70097b94ca6f7e04864c166df5a4123 |
|
MD5 | 18670a260d40a70c99bd7d4bab4054bd |
|
BLAKE2b-256 | 487f8b26cd5a95549097a895984aff15ad66cb715919cf4ebb7265b8335093cb |
Hashes for python_prtree-0.5.4-cp36-cp36m-manylinux_2_17_x86_64.manylinux2014_x86_64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 6995cdacbf21414522cb089fa93b9a066e1c532e8218d756444a072694e1ee7f |
|
MD5 | d507e3138ba3c0d6d176db8b0214337d |
|
BLAKE2b-256 | 03d5655b7993aed4ebaa7313f2bf759291da4cb6e762669fdc987bc33e5c4aa0 |
Hashes for python_prtree-0.5.4-cp36-cp36m-manylinux_2_17_aarch64.manylinux2014_aarch64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 87b992c82661e30d17405131ebb5819ff084a887958567f6a5a957d7eb280293 |
|
MD5 | 7ecb07c29f7d82416cc7193b80d5e67d |
|
BLAKE2b-256 | 33ddfa5473e9874b2bd3fa36f06a17cc845f13c011f8642b78b70c5db8cfb0f9 |
Hashes for python_prtree-0.5.4-cp36-cp36m-macosx_10_15_x86_64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | c29ccb8341c03ffd0b345844e92a0e084d7e1b203612ae7eb97ba152ecd4bd4b |
|
MD5 | 4111d76f832f9fc48bd98ec01dc8b4fd |
|
BLAKE2b-256 | 4f3df3b5322c5152cf745a3887dc41d7928a3d6724ae0d757fee4d4272cce8be |