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.
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]]
# 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.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.1-cp39-cp39-win_amd64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 3936515830f26f31b506f791d9f9ae37c34dc4900c4dec0d7f4f4449e7ab866e |
|
MD5 | ebdab675f83cb06e2bd4538dbba7c8a1 |
|
BLAKE2b-256 | 1886a6e56aa52279c52db49705b9d491087155d242bce31af3e4693ec52a469f |
Hashes for python_prtree-0.5.1-cp39-cp39-manylinux_2_17_x86_64.manylinux2014_x86_64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | b0251df7c345b6a8bb128a99ee3bb6b7d6b2d1ddd143ee95402e945983b8ff5c |
|
MD5 | 915fcc285112764a5d6467e3de5aa15d |
|
BLAKE2b-256 | ffb122d64f0a93a9bcdd7d5dd725db68c7cee51d1876a465b8a00bceec97ce55 |
Hashes for python_prtree-0.5.1-cp39-cp39-manylinux_2_17_aarch64.manylinux2014_aarch64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 457feeb8d9055d79e4f6193ba96274d3e1284d28eef7d8448ada874c77188bef |
|
MD5 | cc6c51508a8946488a5d1fc41f65d389 |
|
BLAKE2b-256 | 793177cc2e216e31adee5f8cd348ed7902f4e9904f3e31237313fc892997562c |
Hashes for python_prtree-0.5.1-cp39-cp39-macosx_10_9_x86_64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 61203fd7be6a635fce749bf50856941779db7c26a0d126fd33bd256703fda7ab |
|
MD5 | ace91e89a7627a52b470a868c2316ec9 |
|
BLAKE2b-256 | f435b9fe74b18115362fa0ff9f963ec3ff18a43f568b72c79a81f501e1ecf063 |
Hashes for python_prtree-0.5.1-cp38-cp38-win_amd64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 99fcfa76fbdfd653252deba56d8df9026f8a18e550b748f579cc18ad7f3e5f4a |
|
MD5 | 2b5e080c488ce5e6bc4bb1f4fa1acf06 |
|
BLAKE2b-256 | d45f11fcd43d83f5a14b100a03ddc4864d1352ff491faa30bdbdfe5a18230ef3 |
Hashes for python_prtree-0.5.1-cp38-cp38-manylinux_2_17_x86_64.manylinux2014_x86_64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 0ccfeb2f56d383e327fb69be0573ba80e1d7f7694e28bf60d534d7fd22b661bc |
|
MD5 | 727596ece2be014bf8285b7c3b6414cf |
|
BLAKE2b-256 | 7c93bd2991f2d493de310008d1df8dfa6e013e583f46099e9333ce34e2b8970e |
Hashes for python_prtree-0.5.1-cp38-cp38-manylinux_2_17_aarch64.manylinux2014_aarch64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | e760a92790b22450081791c9e35e0d8f49221da46dbd2e7b28ebe4cbe94aba45 |
|
MD5 | 9703df5e5122c78d6bec4bd78f5759a0 |
|
BLAKE2b-256 | 7bde7141ea4430a11618a66c3caf50ddb88727bae00fdcf71946245ceeb94ee0 |
Hashes for python_prtree-0.5.1-cp38-cp38-macosx_10_9_x86_64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 6ddab7a1447ac4d178663468b3eadc86bd10b6792d65044b98a8fbbc09bd3473 |
|
MD5 | e900daa7b05ecff4b1043150c7fa5f0b |
|
BLAKE2b-256 | 603c608f645a144de02408c870fbfa65015574bc302867d56e3350d10e63dbc6 |
Hashes for python_prtree-0.5.1-cp37-cp37m-win_amd64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 3d5c387cf32dace75a7e6447e4a1512abd6135883087ad9d8de24b162bc0fd33 |
|
MD5 | 3823d8e828ed04f256db2a1d9c918e8c |
|
BLAKE2b-256 | 052ab9f6af69e9af46754da8f369a6d538a43161b2916eb3d37cce02fc62b979 |
Hashes for python_prtree-0.5.1-cp37-cp37m-manylinux_2_17_x86_64.manylinux2014_x86_64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | d6053bf9d2d2d187f90a3543d0456fb120fb4163e4d82422918bc3e448ec12e5 |
|
MD5 | 236c0313bf93199941ba7da63893839c |
|
BLAKE2b-256 | b6b083abc8026242713871624299856e80e1461c12a6fd0aace5c7d1387ae10d |
Hashes for python_prtree-0.5.1-cp37-cp37m-manylinux_2_17_aarch64.manylinux2014_aarch64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 11d752589f7afde2f018873074465c971cd5aaba6b29fc06bf56ec1300d08552 |
|
MD5 | 0f6dd8642aee09aa974aff336dc4ec7e |
|
BLAKE2b-256 | 3b69a8171ef74c3ac1358aa131517264bf9bf6cf70cd71aec5ec204cb1bb8624 |
Hashes for python_prtree-0.5.1-cp37-cp37m-macosx_10_9_x86_64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 8e71b2715a677de10c11f62a3f3ab45553addef16f061308a219fd2a7741b068 |
|
MD5 | 8fba660dc1c8a1da9b6d1fc5b9891df3 |
|
BLAKE2b-256 | 71e29d941c385fd788dc540e5cf5dd0be17799e184ae851c50fe56faf45f6c51 |
Hashes for python_prtree-0.5.1-cp36-cp36m-win_amd64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 7490bf8c37b1e95dfa2e11450f8d804bf73931aaa4bab32a07ae69179cbbd911 |
|
MD5 | 5942eed00e7d6dc6333df020b655094c |
|
BLAKE2b-256 | 2b21569e4dc400e11b408e641916c9379ca818b5e297f3c13edcbb354c007fa6 |
Hashes for python_prtree-0.5.1-cp36-cp36m-manylinux_2_17_x86_64.manylinux2014_x86_64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 77d8695d34d6f6ef9ee84e57cbcd4bd9f1075324993c81ba106b651f453340c2 |
|
MD5 | 3522fddd777c58a663c80cee263ac5e3 |
|
BLAKE2b-256 | 79fbce4d7960973bfaeed72a1171444d67cac3e8ad14aa5cc231e7bcbc8fa2c7 |
Hashes for python_prtree-0.5.1-cp36-cp36m-manylinux_2_17_aarch64.manylinux2014_aarch64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 92a18127ba4d4b94e4c9d2a8a983779663e88e3a5401cdc253af8aaf785b550a |
|
MD5 | 3c0c6640c91ca7a0a48496af12ce28aa |
|
BLAKE2b-256 | a341d8604f3212cd5d6395336886865dbf4c822eb4af50911dbbc29cfa345ef1 |
Hashes for python_prtree-0.5.1-cp36-cp36m-macosx_10_9_x86_64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 09e3619f8c232923d2f66d1db76d1f6f1fadffde5c97b9596e8cb65530f20d13 |
|
MD5 | af92527d7db11638c95155b0f7b6428e |
|
BLAKE2b-256 | 638f054a01ffe79b0054074ca90b16c2f6cff785d211d2ae7603c32e4d4d6fb5 |