forked from heineman/python-kd-webinar
-
Notifications
You must be signed in to change notification settings - Fork 0
/
app3.py
151 lines (118 loc) · 5.44 KB
/
app3.py
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
"""
Demonstration application for range search using kd tree.
Left mouse adds point, right mouse click begins drag of rectangle.
Adds balancing capability
Iteration: 3
Author: George Heineman
"""
import tkinter
from kd2 import KDTree, X, Y, VERTICAL
import kd_factory
from region import Region, minValue, maxValue
BoxSize = 4 # size of box representing point
Size = 400 # size of canvas containing drawn KD-Tree
class KDTreeApp:
def __init__(self):
"""App for creating KD tree dynamically and executing range queries."""
self.tree = KDTree()
# for range query
self.selectedRegion = None
self.queryRect = None
master = tkinter.Tk()
master.maxsize(width=Size, height=Size+26)
master.minsize(width=Size, height=Size+26)
master.title('KD Tree Drawing and Query Application')
self.w = tkinter.Frame(master, width=Size, height=Size+26)
self.canvas = tkinter.Canvas(self.w, width=Size, height=Size)
self.paint()
b = tkinter.Button(master, text="Reset", command=self.reset)
b.pack()
b = tkinter.Button(master, text="Balance", command=self.rebalance)
b.pack()
self.canvas.bind("<Button-1>", self.click)
self.canvas.bind("<Button-3>", self.range) # when right mouse clicked
self.canvas.bind("<ButtonRelease-3>", self.clear)
self.canvas.bind("<B3-Motion>", self.range) # only when right mouse dragged
# Different bindings on Macintosh platform
self.canvas.bind("<Button-2>", self.range) # when right mouse clicked
self.canvas.bind("<ButtonRelease-2>", self.clear)
self.canvas.bind("<B2-Motion>", self.range) # only when right mouse dragged
self.canvas.pack()
self.w.pack()
def rebalance(self):
"""Rebalance points in tree"""
points = [p for p in self.tree]
if points:
self.tree = kd_factory.generate(points)
self.paint()
def reset(self):
"""Reset to initial state."""
self.tree = KDTree()
self.paint()
def toCartesian(self, y):
"""Convert tkinter point into Cartesian."""
return Size - y
def toTk(self,y):
"""Convert Cartesian into tkinter point."""
if y == maxValue: return 0
tk_y = Size
if y != minValue:
tk_y -= y
return tk_y
def clear(self, event):
"""End of range search."""
self.selectedRegion = None
self.paint()
def range(self, event):
"""Initiate a range search using a selected rectangular region."""
p = (event.x, self.toCartesian(event.y))
if self.selectedRegion is None:
self.selectedStart = Region(p[X],p[Y], p[X],p[Y])
self.selectedRegion = self.selectedStart.unionPoint(p)
self.paint()
# return (node,sub-tree) where sub-tree is True if draining entire tree
# rooted at node. Draw these as shaded red rectangle to identify whole
# sub-tree is selected.
for pair in self.tree.range(self.selectedRegion):
p = pair[0].point
if pair[1]:
self.canvas.create_rectangle(pair[0].region.x_min, self.toTk(pair[0].region.y_min),
pair[0].region.x_max, self.toTk(pair[0].region.y_max),
fill='Red', stipple='gray12')
else:
self.canvas.create_rectangle(p[X] - BoxSize, self.toTk(p[Y]) - BoxSize,
p[X] + BoxSize, self.toTk(p[Y]) + BoxSize, fill='Red')
self.queryRect = self.canvas.create_rectangle(self.selectedRegion.x_min, self.toTk(self.selectedRegion.y_min),
self.selectedRegion.x_max, self.toTk(self.selectedRegion.y_max),
outline='Red', dash=(2, 4))
def click(self, event):
"""Add point to KDtree."""
p = (event.x, self.toCartesian(event.y))
self.tree.add(p)
self.paint()
def drawPartition (self, r, p, orient):
"""Draw partitioning line and points itself as a small square."""
if orient == VERTICAL:
self.canvas.create_line(p[X], self.toTk(r.y_min), p[X], self.toTk(r.y_max))
else:
xlow = r.x_min
if r.x_min <= minValue: xlow = 0
xhigh = r.x_max
if r.x_max >= maxValue: xhigh = Size
self.canvas.create_line(xlow, self.toTk(p[Y]), xhigh, self.toTk(p[Y]))
self.canvas.create_rectangle(p[X] - BoxSize, self.toTk(p[Y]) - BoxSize,
p[X] + BoxSize, self.toTk(p[Y]) + BoxSize,
fill='Black')
def visit (self, n):
""" Visit node to paint properly."""
if n == None: return
self.drawPartition(n.region, n.point, n.orient)
self.visit (n.below)
self.visit (n.above)
def paint(self):
"""Paint KD Tree by visiting all nodes."""
self.canvas.delete(tkinter.ALL)
self.visit(self.tree.root)
if __name__ == "__main__":
app = KDTreeApp()
app.w.mainloop()