Python implementation of Priority R-Tree
Project description
python_prtree
"python_prtree" is a python implementation of Priority R-Tree (see reference below). Supported futures are as follows:
- Construct Priority R-Tree(PRTree) from rectangles; array of (xmin, xmax, ymin, ymax)
- query and batch query with rectangle(s)
- insert and erase(delete) (but not optimized yet)
This package is mainly for nearly static situations, which mean few insert/delete events happen (e.g., mapmatching).
Usage
import numpy as np
from python_prtree import PRTree
idxes = np.array([1, 2]) # must be unique because using idx as key for hash map
rects = np.array([[0.0, 1.0, 0.0, 0.5],
[1.0, 1.2, 2.5, 3.0]]) # (xmin, xmax, ymin, ymax)
prtree = PRTree(idxes, rects) # initial construction
q = np.array([[0.5, 0.6, 0.2, 0.3],
[0.8, 1.5, 0.5, 3.5]])
result = prtree.batch_query(q)
print(result)
# [[1], [1, 2]]
1d-array batch query will be implicitly treated as 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 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
Installation
To install python_prtree with pip command
pip install python-prtree
Or, you can clone and install just like
git clone --recursive https://github.com/atksh/python_prtree
cd python_prtree
python setup.py install
This installation needs cmake.
Performance
Construction
Query and batch query
Delete and insert
Requirement
- numpy
NOTE
- This PRTree is implemented by C++ with Pybind11, and much faster than numba implementation of PRTree.
- If you can use C++, you should use boost::geometry (I didn't 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 Distributions
Built Distributions
Hashes for python_prtree-0.2.0-cp38-cp38-win_amd64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 2c62a6ef917f1c4e44df5624e12b411a6303c76eb9c0540eda8c923c7bbe23e7 |
|
MD5 | 3442e0afa778b24e4dba7ca599d64549 |
|
BLAKE2b-256 | 558256fec62115daea47d7cf1a89fc7ab55d2638d07ea70ab0189b6bdadedcfb |
Hashes for python_prtree-0.2.0-cp38-cp38-manylinux2014_x86_64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 18af88a44baa7d1fdbe80de3e38c49ac9ba2ffc2ec3e8295b6f850a14a6af75a |
|
MD5 | 72513d4e00aab6493327d45fe4fa3676 |
|
BLAKE2b-256 | de442d17da67f64d9696ee227e7e987169a3dbb99db4dea63c36d18515365116 |
Hashes for python_prtree-0.2.0-cp38-cp38-macosx_10_9_x86_64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 8cde43d53f6f7a1a5fe8fa2be1416a0819c9580267e70e1c5e5ae497ae3c5725 |
|
MD5 | 7b279c7cd4ae12411169dfdde09de8a2 |
|
BLAKE2b-256 | 4835ec0ab2fabbddcb33f15b7261b64748d8d329997fb4bbf2d47e005f5aa11f |
Hashes for python_prtree-0.2.0-cp37-cp37m-win_amd64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 45a6e1fdb19c32670a63d9824440935b79a489e03cd12d76a24313303996871a |
|
MD5 | 5bc85f24ce9ea5b0036b1107dd04fecb |
|
BLAKE2b-256 | 9f6f4d9c1e5e6c669f66a83c0dd5dca43d56e4f9caa294fc8a8e75cbd62fc66e |
Hashes for python_prtree-0.2.0-cp37-cp37m-manylinux2014_x86_64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | d764f8299584752eaff1e764bd8ef32b36a37bc3f43581993c966d5ea04bf435 |
|
MD5 | 8ff33148c480ee8d8e622332d00ea318 |
|
BLAKE2b-256 | 3223963c69e5162ec49c09eb70889c3b7c60aaad84c419093c404ff5e4abd42b |
Hashes for python_prtree-0.2.0-cp37-cp37m-macosx_10_9_x86_64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 56f46196a6a7fd966cafc67bfb3ab31e1c1442d7f79efaacc41130d90a93b60a |
|
MD5 | 35af29b44fdff2c581e8390d597bc660 |
|
BLAKE2b-256 | 73537b58f008808f32dbfb1ff934a7a23638feb92fb48bfb1e88c915c15d0645 |
Hashes for python_prtree-0.2.0-cp36-cp36m-win_amd64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 3d93d4ebebfdda0189113bc5a0c2276f4ccd9064b3eb6aedaba960195ab12415 |
|
MD5 | 509eaa3be810e848a7cc3977e529e8cb |
|
BLAKE2b-256 | d3b8e2b292baf2aa2401f3db237c149cc9fcee3f064153e1849e5e219082ca58 |
Hashes for python_prtree-0.2.0-cp36-cp36m-manylinux2014_x86_64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 4d61e62a2dc2d563ccbf7262668f45ca6ecc2e9f6e7cfb89d86cf41020943f7f |
|
MD5 | 4d9486c1c1ead42efe532f0bcddb9398 |
|
BLAKE2b-256 | 530013c5d64b82a5a55c8cb1ec55ade9fe232cde808b79e6d43578dc577af19b |
Hashes for python_prtree-0.2.0-cp36-cp36m-macosx_10_9_x86_64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | cf1f873d16ee1055c880e2345e8dbaf6455f0aecf8f4cb08ff309dd16c9cf55d |
|
MD5 | 4aec286ff3ed3d3b84fe4ee7ae2fe7b9 |
|
BLAKE2b-256 | a7bd338b3b8690431a3547716db2155089e4f2f7dd6e80fcb865a1717d4c41ad |
Hashes for python_prtree-0.2.0-cp35-cp35m-win_amd64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 11ea862d32bb14583b65d88eae21f9a69711afe8f6ec126e6c4b600c8590630b |
|
MD5 | 05fab0701abd736a3c1c133e931c1628 |
|
BLAKE2b-256 | 65c3038323d0ee96503fc509fea5006150ba8e22120b508ca636f406870097a1 |
Hashes for python_prtree-0.2.0-cp35-cp35m-manylinux2014_x86_64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | b5f126a4cce4fec0ae58ae91db687552e5d94d6d8ed85312ea5915b25e891566 |
|
MD5 | 0acd6de6d3c5e87e0d4f37701b14ae51 |
|
BLAKE2b-256 | b27945ffaef63c39a3f2fdac5452e340b13bce6d4dcc28eb598e995825102629 |
Hashes for python_prtree-0.2.0-cp35-cp35m-macosx_10_9_x86_64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 42b132d6d6898ac30d36362ad5f7ba875e60e491593874d9660925a02b3bc70f |
|
MD5 | 9c58e45e9f164efaf4ebd8497ee24ca4 |
|
BLAKE2b-256 | 009af57aa15814a429b7b011e238803725be048c9e0d8ec243d55ebc9d5ee07d |