Line
1	from pos import Pos
2
3	class Quadtree:
4	def __init__(self, entities):
5
6	self.leaves = [[],[],[],[]]
7	self.center = Pos()
8
9	if len(entities) <= 1:
10	return
11
12	self.entities = entities
13
14	self.min = Pos(min([e.pos[0] for e in self.entities]), \
15	min([e.pos[1] for e in self.entities]))
16
17	self.max = Pos(max([e.pos[0] for e in self.entities]), \
18	max([e.pos[1] for e in self.entities]))
19
20	self.center = Pos((self.max[0] - self.min[0]) / 2 + self.min[0], \
21	(self.max[1] - self.min[1]) / 2 + self.min[1])
22
23	bins = [[],[],[],[]]
24	for e in self.entities:
25	if e.pos[0] < self.center[0]:
26	if e.pos[1] < self.center[1]:
27	bins[0].append(e)
28	else:
29	bins[1].append(e)
30	else:
31	if e.pos[1] < self.center[1]:
32	bins[2].append(e)
33	else:
34	bins[3].append(e)
35
36	if bins[0]: self.leaves[0] = Quadtree(bins[0])
37	if bins[1]: self.leaves[1] = Quadtree(bins[1])
38	if bins[2]: self.leaves[2] = Quadtree(bins[2])
39	if bins[3]: self.leaves[3] = Quadtree(bins[3])
40
41	def dump(self, depth = 1):
42	print ' ' * depth * 3, self.center
43	for a in range(4):
44	if self.leaves[a]:
45	self.leaves[a].dump(depth + 1)

Note: See TracBrowser for help on using the browser.