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; an array of (xmin, xmax, ymin, ymax)
- query and batch query with a 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., map-matching).
Usage
import numpy as np
from python_prtree import PRTree
idxes = np.array([1, 2]) # must be unique because it uses 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 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
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
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
- 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 Distributions
Built Distributions
Hashes for python_prtree-0.3.2-cp38-cp38-win_amd64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 3ce3796e2ceeaafeba0eb59ea8328a733c28ec34a1dc329e3650953918f27a4d |
|
MD5 | edaa620b75328d0af4f3787e2278eb5b |
|
BLAKE2b-256 | f1c1d5e89442c1ab44f5a100e66dc24692bccb0747b87165307e68f434c30db3 |
Hashes for python_prtree-0.3.2-cp38-cp38-manylinux2014_x86_64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | d18f58ef262f21fbe79c912b4601a30b96a18cc3764194dfe1577ffeaaf5e2f0 |
|
MD5 | 04c82c02d9e74a3324eb707c7178a243 |
|
BLAKE2b-256 | faac0e2f3047949fcd54fd5495a78885afcad15a252a3a17a2dae0e34de39d23 |
Hashes for python_prtree-0.3.2-cp38-cp38-macosx_10_9_x86_64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 00d805cd92a42d2205349959c966a7976a5af4204a99cbdb99a6ade187eb843e |
|
MD5 | eafada371ad8925bb2d512ed9a29489d |
|
BLAKE2b-256 | 8809ebc03ab314d74682c60a9904e07a7bd6c0a312c15b47f468a1c009f8d7d4 |
Hashes for python_prtree-0.3.2-cp37-cp37m-win_amd64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 3b54a5412a7290903350478c8c3029cab83b2bb8ae286938832809077ee56c41 |
|
MD5 | 102d01eea7003e0fa43c4ea3e92654e0 |
|
BLAKE2b-256 | 7f19a6ac12cbb12af4ee959832f0911dd21339e6f1a3baf7c9e73476f303d38e |
Hashes for python_prtree-0.3.2-cp37-cp37m-manylinux2014_x86_64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 4ee205928a426f411d50fa2f1847e00d1747d549d2f7ecd034a33e219987708a |
|
MD5 | dd4956473aa094dba1d150d3319b83d8 |
|
BLAKE2b-256 | 89ebc78643c89b923296cca0aea8ca382cec1abd46c22a5925ddc7aa33c4a32c |
Hashes for python_prtree-0.3.2-cp37-cp37m-macosx_10_9_x86_64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 9a3278e34c5c76929e34ed400813f3cea2f4163caae1d2e27d8b0623cc35c48c |
|
MD5 | e8b760d03339cd8ecbcfe5cddde8ac96 |
|
BLAKE2b-256 | 8bf2a91f21abe309c23fbc891049ed9a488d2340301e0a3f4ce75af5f1a0f1ef |
Hashes for python_prtree-0.3.2-cp36-cp36m-win_amd64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 1f05bc121aa2177db8cbbdac26c9e3f06907f9cb22b1429cd748830d7573c2ad |
|
MD5 | 2e32ca908f00ee055521b7477bbfbc61 |
|
BLAKE2b-256 | f30dcff4969a6d60d7824a730c39a675f03e77e10d62cf3ef80fd70ff3320b99 |
Hashes for python_prtree-0.3.2-cp36-cp36m-manylinux2014_x86_64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | aff72f964aa8eafcff6149af8fc06df86c6c2aac492cf7711e2020f53247aaaf |
|
MD5 | 6bd4ef42c06ad8b9aedc1df89d668d83 |
|
BLAKE2b-256 | d275104c9b9502cb528ce9e030a8ca6ac3ac59badbe9ab98b84ac2a1b268f646 |
Hashes for python_prtree-0.3.2-cp36-cp36m-macosx_10_9_x86_64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 6ad11ad7ffc329724bf9c11dd3e69cbc1e54db625ced1af39a13ca9d4886abe6 |
|
MD5 | a1aa46deec037d0fc640cf19feb394fc |
|
BLAKE2b-256 | dbd86d4dad03137dd2d6f1b0fb0d67d51f627b9f248398c4fc8d87a404a4305e |
Hashes for python_prtree-0.3.2-cp35-cp35m-win_amd64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 45e96760fc1174fc1774a120cccad27e61f593e1045374221ff2a96aa6876fae |
|
MD5 | 7051d11cdb3a6d09007f59e8bea72226 |
|
BLAKE2b-256 | 1cad1087ac042e77ccc38a5071ee1ecc4f116967b61f66553e3238dde225d053 |
Hashes for python_prtree-0.3.2-cp35-cp35m-manylinux2014_x86_64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 5a75660befd3c3bd13c510bd8cc529d9bd2a88c01165000ecef99e2fc3c0ce69 |
|
MD5 | 3b2e41f7ba7f34d514dde4959b8fb447 |
|
BLAKE2b-256 | 553741ae9f48c2f6061bf63ed286fcaea9d27587d3f4f83f8028ef3107240ab5 |
Hashes for python_prtree-0.3.2-cp35-cp35m-macosx_10_9_x86_64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | a8b27451d1939ca72c246fad7a290b31e2f3d6fc104aee2e8fbbd3cf8194295d |
|
MD5 | 848168c375d165fce324103901c19bb9 |
|
BLAKE2b-256 | 8dce28ac9c60c4570df866d9ff65746d8f62da1e73cff55efbb1bf19d4de7c57 |