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.4-cp38-cp38-win_amd64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 1953ccdd338840a71df47dfff6c8b413253b8711c131f8b3b72018662cbc65f2 |
|
MD5 | 6c7333f85ac69cc1acaf3ba0b4c01547 |
|
BLAKE2b-256 | 73b973005e1b50a51efc3e7f3deea0ba06f900c6eff6c992f396547cd0af5905 |
Hashes for python_prtree-0.3.4-cp38-cp38-manylinux2014_x86_64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 8ea158289b66c2d6baa0199c739e83d101d295bc7c892c979436c35ca0f6de35 |
|
MD5 | be5cc86e02f0a89d990d3c9ea8998107 |
|
BLAKE2b-256 | 040618b56dceb91cdf277e1348c26ec42de2408728f8b616e4804828d43d0465 |
Hashes for python_prtree-0.3.4-cp38-cp38-macosx_10_9_x86_64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 97188c7102618fd6805ad85fb871d1942ac43e5c3c1fbc29f3097f4e0e4d6339 |
|
MD5 | 514f25c3dbba511a3ada7f2d017420c0 |
|
BLAKE2b-256 | c999b30ce20307308f76dbab8d3359c1a067daea66a1802b58c791575a02fa13 |
Hashes for python_prtree-0.3.4-cp37-cp37m-win_amd64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 95556d1cfd8b50920992b8d6439af436c42ec7a304ef05eeb7a5f55f873dc3fa |
|
MD5 | f4b3e92ad4ced2565d64a41b1285dd0c |
|
BLAKE2b-256 | 09e0edd503b6394ca4747653232bda7694e22e4ff12b5f3e63569fe4cea3aa7b |
Hashes for python_prtree-0.3.4-cp37-cp37m-manylinux2014_x86_64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | d2f342063ce7e07685f65f46b96e0dbff435ba622474071e573a7d0d05aee586 |
|
MD5 | 2b4f207847e4c9d5cb54aad4f6dfbf5e |
|
BLAKE2b-256 | 92004f7c4803a90c43a83b595f2448befd7b1d0c7d200e2b92ef0e0c4edc5658 |
Hashes for python_prtree-0.3.4-cp37-cp37m-macosx_10_9_x86_64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 45e77be3224dcb1bf997e29224a7d5fc0fb1d5c1ef878f179ecf3898658ca070 |
|
MD5 | db6f0c1387285c445491b427352bcfce |
|
BLAKE2b-256 | 3bb01e39057aa7fb1a1b82b33df267d3927daa0e06f71c759324618eb0fed3a7 |
Hashes for python_prtree-0.3.4-cp36-cp36m-win_amd64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | ee513777e594ac233614b78262da202594a78a19f5ca0feafc81084198223c3e |
|
MD5 | ead3a4800086dc8d6562fc765fa0644b |
|
BLAKE2b-256 | f1beccf9c7ff17ba4b45852557b1872a77f62f75b630ccbbad464ed258c9f232 |
Hashes for python_prtree-0.3.4-cp36-cp36m-manylinux2014_x86_64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | c8d06795cdd6b43a7a890df078c9e1905f46e08f68ccf1aa6be612dc3e1b2501 |
|
MD5 | 4caec54a7e5b0700c555d33c1390f384 |
|
BLAKE2b-256 | 02e74e8f63da0da3ebe3b405a2b2d80a0a2cdf7dd3127fcec357a6b3e227d98e |
Hashes for python_prtree-0.3.4-cp36-cp36m-macosx_10_9_x86_64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 3f2901ba0a69817e424689c7a9082439b11e5f44397eac1a8539119e64ea7d69 |
|
MD5 | 388abefc801fb8703167fdf6adb6c71e |
|
BLAKE2b-256 | 8982680a39c0a5890349596494a88a476f71743179ca8bd1a5c88ea470220878 |
Hashes for python_prtree-0.3.4-cp35-cp35m-win_amd64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 7dce6f9d26a169456368eb71b7ef314b3f474d0c6849fbafdb237f20470ec501 |
|
MD5 | 51293852f6a4a807e344e771df70fd96 |
|
BLAKE2b-256 | 1e9f5292a49bf9844f69ef84c575e59e44432466376cbe907fbaf2f739b843e0 |
Hashes for python_prtree-0.3.4-cp35-cp35m-manylinux2014_x86_64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | aff2964bea860c7730308d202ab91ed6054d862206c0d5a64675af9ec6a337a7 |
|
MD5 | 0080ce5b0313bc982c2e95b73ccd0ab5 |
|
BLAKE2b-256 | af29d5dd79e798c0d5564630e80329f8caca4d2a3c9822cb8ec96aec2aef007e |
Hashes for python_prtree-0.3.4-cp35-cp35m-macosx_10_9_x86_64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 5a93ffc837fd6445771f859f0fe88e8ab9a82db89d5d372f3701301910d400c3 |
|
MD5 | edb2d609f40970cf1e46a8705b175ad0 |
|
BLAKE2b-256 | 07f61a3481e924f40a87ab4ad0afaa9787c7c604acccafa5c8904574d0266b6d |