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.
- The
insert
andquery
methods can now be passed pickable Python objects instead of int64 indexes since>=0.5.2
.- See the example below for more details.
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
A Simple Example
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.3
- Add gzip compression for pickled objects.
python-prtree>=0.5.2
You can use pickable Python objects instead of int64 indexes for insert
and query
methods:
import numpy as np
from python_prtree import PRTree2D
objs = [{"name": "foo"}, (1, 2, 3)] # must NOT be unique but pickable
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()
for obj, rect in zip(objs, rects):
# keyword argments: bb(bounding box) and obj(object)
prtree.insert(bb=rect, obj=obj)
# returns indexes genereted by incremental rule.
result = prtree.query((0, 0, 1, 1))
print(result)
# [1]
# returns objects when you specify the keyword argment return_obj=True
result = prtree.query((0, 0, 1, 1), return_obj=True)
print(result)
# [{'name': 'foo'}]
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.6-cp39-cp39-win_amd64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 26f35be8f3bfe81d7cac262c47e6b900a8d83a922e47d9d82e55c983c1613dab |
|
MD5 | 987d5065347629ba9350fa7d9c4521b2 |
|
BLAKE2b-256 | 2062bb6c7ef3fb4f7146e194a375f878cb420e65d8ea64ff9207aecf427f0236 |
Hashes for python_prtree-0.5.6-cp39-cp39-manylinux_2_17_x86_64.manylinux2014_x86_64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | acc89220e329b77f4cf316dc8366795fab633a6e97dea1614869e756e94f366b |
|
MD5 | 9513a260fa1feeb1adaa565399662b92 |
|
BLAKE2b-256 | e8be0e3fea5cbf32368973aef33da299a77420bcacabda860557f69dabbaefed |
Hashes for python_prtree-0.5.6-cp39-cp39-manylinux_2_17_aarch64.manylinux2014_aarch64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 990adfc9accd0847d1929a667bd3ddde5ee7d8e707163880843e80769de48865 |
|
MD5 | 4aa21c660a94e95cb15d9fcd44c2beae |
|
BLAKE2b-256 | 6fb02ae8d4aba92d9cb8a574bddb6fd68b3a425639f08ba980c3e20184efe21a |
Hashes for python_prtree-0.5.6-cp39-cp39-macosx_10_15_x86_64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | f115917f5dc1217eb3098dfa0cc9d0d5d45f8ae52080723b804b67228a491b18 |
|
MD5 | a3f27545a2f6c12f7fb4552a6eddc3c8 |
|
BLAKE2b-256 | e4207c3786e7d455984c107e0b13372de0c92a4f703c9414d5a0c98d4bee2781 |
Hashes for python_prtree-0.5.6-cp38-cp38-win_amd64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 0d80322ae1138b57bd4c04dd94511c8ad94f5bf762e9f63c7247804fc556cb23 |
|
MD5 | 661acb34200cc06aa804248599bfa52b |
|
BLAKE2b-256 | 2a81d840458437b8bf7086639537b7eefb9543be6f2626fc8778a194c9c16ac5 |
Hashes for python_prtree-0.5.6-cp38-cp38-manylinux_2_17_x86_64.manylinux2014_x86_64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 46db0232e2ead03131fed492e02366119c52f496d58567bfdba56acae017e350 |
|
MD5 | 6cf926180569bb59a80bab05b4b3acfd |
|
BLAKE2b-256 | 3a365983c338d50d2328a8038700b9431baac15bbd92bb56cddb65911a6d3c8c |
Hashes for python_prtree-0.5.6-cp38-cp38-manylinux_2_17_aarch64.manylinux2014_aarch64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 557d5e2252e6d9cb44d75627573c3dc78aeb616467b21566c88fee12fcda0782 |
|
MD5 | f6710b425c322a8f04bb612b6a6c9613 |
|
BLAKE2b-256 | b051687d90948763c6d2042a505e7dd107c954bcd8fe766f94549a729b486956 |
Hashes for python_prtree-0.5.6-cp38-cp38-macosx_10_15_x86_64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | a48505c3f9cc703b5e9b5adaa6059e441ed0bbe15d690456d99f615756dfb596 |
|
MD5 | 1efa5d766724b978db4cd617e318c8f8 |
|
BLAKE2b-256 | 98015cd69a55d597728ff13fbea31e158b516889bd60c5f602fb55c977a5a83c |
Hashes for python_prtree-0.5.6-cp37-cp37m-win_amd64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | a95994021da9c4cd703bd5ffef8e07e053d8552064ce9008cf2dddfdeff5ca6e |
|
MD5 | 604bb8152005a34a3e6c5d9b921f8950 |
|
BLAKE2b-256 | fd97776f72b972416d2a8db60f140232cb41d0d28682210e3fca9eba051a593a |
Hashes for python_prtree-0.5.6-cp37-cp37m-manylinux_2_17_x86_64.manylinux2014_x86_64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 04500f7c988b5165b8540ae863cf3a289e4b4a665217a4d4696b595ebe7961ff |
|
MD5 | c9b220db36e808c8533da91d63df1c2e |
|
BLAKE2b-256 | 02ff50caf447e94126d137c40115aa22587dcaad8c2684d2e3967a98538839ce |
Hashes for python_prtree-0.5.6-cp37-cp37m-manylinux_2_17_aarch64.manylinux2014_aarch64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 784bb564c40e9065f5e3e7be613d63744ff41dab894e31553d4f2528a4026d34 |
|
MD5 | f848d72905e651b63c7bfa6ca32a4eea |
|
BLAKE2b-256 | 0774abdddd521642f6e5cac5464fe7140d6073979f070761242f0e514101bb4a |
Hashes for python_prtree-0.5.6-cp37-cp37m-macosx_10_15_x86_64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 9602d520af0ae4eba150e80c910679b724dedf9999f755a4b887975548b29135 |
|
MD5 | 504fc47436a34234b20f8aafbc7d900a |
|
BLAKE2b-256 | 4538eea7f4549ffc58fee51beb1044434af62e61b47df77e3ee25d88bf2fd9f6 |
Hashes for python_prtree-0.5.6-cp36-cp36m-win_amd64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 49f1eb155d5b346592f597ceb212b5f79591349910c18f35fc4efa0afa3c1d96 |
|
MD5 | 172b9c673530495393d00d6df0b4dae3 |
|
BLAKE2b-256 | 0c93a4e23293b27649648cf72f2cc9175108eb50daa4603d082b17047038dc55 |
Hashes for python_prtree-0.5.6-cp36-cp36m-manylinux_2_17_x86_64.manylinux2014_x86_64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 731fcd0f64e9cc2c85ba56df5dd959e9480fb626c58374f21f193d485627b22e |
|
MD5 | cf738e98c6337163aef5e22004924e5f |
|
BLAKE2b-256 | 01dd3b6d8bd855f9178d4c43d639b7f2e87ae84291ac8f2d802a5ea4100c17e1 |
Hashes for python_prtree-0.5.6-cp36-cp36m-manylinux_2_17_aarch64.manylinux2014_aarch64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 57fc5b398beb70d6ed3db1e9d1a85fd5b32cdbfee20620588d9c7e2565b9a578 |
|
MD5 | 52eb9366ca645c658df65341af893471 |
|
BLAKE2b-256 | ab5f9610eb5e6f1e7ff4f3b90b549990bd0ec24b1f86a867eab0be1efb73075b |
Hashes for python_prtree-0.5.6-cp36-cp36m-macosx_10_15_x86_64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 4e6fdff201f0068edd1da9ccf3b8c09a0866a60d0e8d4647fee8b856963914ee |
|
MD5 | 051e82581aa32340936d43ebb5a7c63f |
|
BLAKE2b-256 | 20eb7f6af867b4fe1120779398409aaa73d456701190e3ef893501a610cb73af |