1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
|
# -*- coding:utf-8 -*-
# <pep8 compliant>
"""
# Pyqtree
Pyqtree is a pure Python spatial index for GIS or rendering usage.
It stores and quickly retrieves items from a 2x2 rectangular grid area,
and grows in depth and detail as more items are added.
The actual quad tree implementation is adapted from
[Matt Rasmussen's compbio library](https://github.com/mdrasmus/compbio/blob/master/rasmus/quadtree.py)
and extended for geospatial use.
## Platforms
Python 2 and 3.
## Dependencies
Pyqtree is written in pure Python and has no dependencies.
## Installing It
Installing Pyqtree can be done by opening your terminal or commandline and typing:
pip install pyqtree
Alternatively, you can simply download the "pyqtree.py" file and place
it anywhere Python can import it, such as the Python site-packages folder.
## Example Usage
Start your script by importing the quad tree.
from pyqtree import Index
Setup the spatial index, giving it a bounding box area to keep track of.
The bounding box being in a four-tuple: (xmin, ymin, xmax, ymax).
spindex = Index(bbox=(0, 0, 100, 100))
Populate the index with items that you want to be retrieved at a later point,
along with each item's geographic bbox.
# this example assumes you have a list of items with bbox attribute
for item in items:
spindex.insert(item, item.bbox)
Then when you have a region of interest and you wish to retrieve items from that region,
just use the index's intersect method. This quickly gives you a list of the stored items
whose bboxes intersects your region of interests.
overlapbbox = (51, 51, 86, 86)
matches = spindex.intersect(overlapbbox)
There are other things that can be done as well, but that's it for the main usage!
## More Information:
- [Home Page](http://github.com/karimbahgat/Pyqtree)
- [API Documentation](http://pythonhosted.org/Pyqtree)
## License:
This code is free to share, use, reuse, and modify according to the MIT license, see LICENSE.txt.
## Credits:
- Karim Bahgat (2015)
- Joschua Gandert (2016)
"""
__version__ = "0.25.0"
# PYTHON VERSION CHECK
import sys
PYTHON3 = int(sys.version[0]) == 3
if PYTHON3:
xrange = range
class _QuadNode(object):
def __init__(self, item, rect):
self.item = item
self.rect = rect
class _QuadTree(object):
"""
Internal backend version of the index.
The index being used behind the scenes. Has all the same methods as the user
index, but requires more technical arguments when initiating it than the
user-friendly version.
"""
def __init__(self, x, y, width, height, max_items, max_depth, _depth=0):
self.nodes = []
self.children = []
self.center = (x, y)
self.width, self.height = width, height
self.max_items = max_items
self.max_depth = max_depth
self._depth = _depth
def _insert(self, item, bbox):
if len(self.children) == 0:
node = _QuadNode(item, bbox)
self.nodes.append(node)
if len(self.nodes) > self.max_items and self._depth < self.max_depth:
self._split()
else:
self._insert_into_children(item, bbox)
def _intersect(self, rect, results=None):
if results is None:
results = set()
# search children
if self.children:
if rect[0] <= self.center[0]:
if rect[1] <= self.center[1]:
self.children[0]._intersect(rect, results)
if rect[3] >= self.center[1]:
self.children[1]._intersect(rect, results)
if rect[2] >= self.center[0]:
if rect[1] <= self.center[1]:
self.children[2]._intersect(rect, results)
if rect[3] >= self.center[1]:
self.children[3]._intersect(rect, results)
# search node at this level
for node in self.nodes:
if (node.rect[2] >= rect[0] and node.rect[0] <= rect[2] and
node.rect[3] >= rect[1] and node.rect[1] <= rect[3]):
results.add(node.item)
return results
def _insert_into_children(self, item, rect):
# if rect spans center then insert here
if (rect[0] <= self.center[0] and rect[2] >= self.center[0] and
rect[1] <= self.center[1] and rect[3] >= self.center[1]):
node = _QuadNode(item, rect)
self.nodes.append(node)
else:
# try to insert into children
if rect[0] <= self.center[0]:
if rect[1] <= self.center[1]:
self.children[0]._insert(item, rect)
if rect[3] >= self.center[1]:
self.children[1]._insert(item, rect)
if rect[2] > self.center[0]:
if rect[1] <= self.center[1]:
self.children[2]._insert(item, rect)
if rect[3] >= self.center[1]:
self.children[3]._insert(item, rect)
def _split(self):
quartwidth = self.width / 4.0
quartheight = self.height / 4.0
halfwidth = self.width / 2.0
halfheight = self.height / 2.0
x1 = self.center[0] - quartwidth
x2 = self.center[0] + quartwidth
y1 = self.center[1] - quartheight
y2 = self.center[1] + quartheight
new_depth = self._depth + 1
self.children = [_QuadTree(x1, y1, halfwidth, halfheight,
self.max_items, self.max_depth, new_depth),
_QuadTree(x1, y2, halfwidth, halfheight,
self.max_items, self.max_depth, new_depth),
_QuadTree(x2, y1, halfwidth, halfheight,
self.max_items, self.max_depth, new_depth),
_QuadTree(x2, y2, halfwidth, halfheight,
self.max_items, self.max_depth, new_depth)]
nodes = self.nodes
self.nodes = []
for node in nodes:
self._insert_into_children(node.item, node.rect)
|
