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]]
New features(python-prtree>=0.3.0
)
You can save and load 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
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.3.0-cp38-cp38-win_amd64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | b1da31d8f33d42f28a4240da955957524dd57cde3f657c02742df59573e6cdb6 |
|
MD5 | 7309182106c3d68b4679e1aae7b4ae60 |
|
BLAKE2b-256 | e16dc7699c452681fcb4cbb04cfbb3ff5d0617f223da3ca61cf86f24e1d5a74b |
Hashes for python_prtree-0.3.0-cp38-cp38-manylinux2014_x86_64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 0d0aaffc498e0ae8ad1c703b1614747d572942e847b7d8af75f45b13f415dfbf |
|
MD5 | 5c0feef6b36c4d5c352a409401abc995 |
|
BLAKE2b-256 | 388d1541e3630f4d3479c11aa6321735d7037140a5fe72d7a52ec80a193ef77e |
Hashes for python_prtree-0.3.0-cp38-cp38-macosx_10_9_x86_64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | c78bdbe8ce84cdf541431acf35f84110517430a6e6dd95185449d564fd07acde |
|
MD5 | 57de92d060247621b2e04a59417d4c9d |
|
BLAKE2b-256 | 2a5af3d4da0b8ba7a5ffe54aa37125065c638f430b747ffaa9a0cd99950f4044 |
Hashes for python_prtree-0.3.0-cp37-cp37m-win_amd64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 636f8e5a6b9569ff610daa09d5ba7d3b3d91a6156d6cbc68140619baea8db622 |
|
MD5 | f31520181851f8d7091b4c5e5b1b7b65 |
|
BLAKE2b-256 | 02a0ea227bc597db0a96842d289dd0ac2d6b9d7efad0906d4382e0fe20f4a7a6 |
Hashes for python_prtree-0.3.0-cp37-cp37m-manylinux2014_x86_64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | f3a11fab5efb34d9784db02c6326c2de65366c6969a05418267d131852b9b3c7 |
|
MD5 | 99a63a69f6ef945da7508274f4e1d583 |
|
BLAKE2b-256 | 288fbfeca38ab685a26731da848ae2ac5622fae6d4f3f1d939e5a57948b2a6de |
Hashes for python_prtree-0.3.0-cp37-cp37m-macosx_10_9_x86_64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 7d92e1f49b4657f28ba2bed720736cd43806d496966d8ac907b68de97061ddb0 |
|
MD5 | 67e5463e993598a7a6ef79b25bb1fcb2 |
|
BLAKE2b-256 | f34f161660b46f1c6a920fcfa3b729484651e66ff7de98ec8d364f8570abfaea |
Hashes for python_prtree-0.3.0-cp36-cp36m-win_amd64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 9e2e89e780ac0f4f09ab5ffcd7ec1d338ae7687130c93b140345ab791c725493 |
|
MD5 | db41a02a3dfedad009f8c6e59e342995 |
|
BLAKE2b-256 | 3ed4384fb66196d20396228b9c6ff5f2f6e3f514a2deafa04b7b81e5fb4c2c99 |
Hashes for python_prtree-0.3.0-cp36-cp36m-manylinux2014_x86_64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | e0f8aa0dbc780d4fc9331ae7435b94af1a4e96b4e2ee57c0283c6d2ada3688c1 |
|
MD5 | 5cdf89ab77bbf6813479608ed88b0d52 |
|
BLAKE2b-256 | ae9736b3442a71cedceaf61e0efcbd1b50bbbbdb855f06b873e6886181c750ed |
Hashes for python_prtree-0.3.0-cp36-cp36m-macosx_10_9_x86_64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | e8b646f36e124ff9bd56d784c1a24b31c149b22dde77f6f0be1be445c8b2ec98 |
|
MD5 | a7077def74dd62ac026bcba13f2f9f0b |
|
BLAKE2b-256 | ae51ac01ac89d4772329cd6049345f89c68b101488ec3f522a7a501e09350fab |
Hashes for python_prtree-0.3.0-cp35-cp35m-win_amd64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | ea520bc0fd5917a28c6c68d015688e62deae608f36e0fb47774d9a67046b42e2 |
|
MD5 | fe7bdc681e719ab41525f5b501438fc1 |
|
BLAKE2b-256 | deb0a4f1d3eb148f727549a7e56d125df492839a4b547668648b0b175f3aa9c9 |
Hashes for python_prtree-0.3.0-cp35-cp35m-manylinux2014_x86_64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | d738cce2fb61611e2ad466d353e42a8a4daee12a4065f9f21b7cca2f6ddca2ef |
|
MD5 | 35d19f152b866bd85fc88dadafc83a9b |
|
BLAKE2b-256 | 57cc511c4a19c13c2fd2920b59a8c2d9896e52b099fe017cc8e83e26270551d6 |
Hashes for python_prtree-0.3.0-cp35-cp35m-macosx_10_9_x86_64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 220eaa74d0ccd94842ebd3d89293d7432bae715c1beb71c91a92e6e05f353775 |
|
MD5 | efe3db125a24439edafdda16fb7cf4a4 |
|
BLAKE2b-256 | fa1cec1b63e394e677499fd37e4d98df683b0f5c5101114bb1e957baf21a0f3b |