Skip to content

Commit bbd91d9

Browse files
heinemanheineman
committed
Uploaded Python code for KDtree Module
Fixed defect in app_nn which had mistakenly computed minimum distances in the case where it was "too close to call".
1 parent 6de7a0d commit bbd91d9

4 files changed

Lines changed: 425 additions & 0 deletions

File tree

‎5. KD Tree Data Structure/README.txt‎

Lines changed: 31 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,31 @@
1+
Module 5 KD Tree
2+
3+
This module contains the KD Tree implementation as developed in this module.
4+
Because the project required changes to the data structure, I have updated
5+
the kdtree.py file to contain all necessary functionality.
6+
7+
Files contained within this module include:
8+
9+
* kdtree.py Implements KDtree and supports nearest neighbor query
10+
* app.py App for demonstrating construction of KD tree graphically
11+
* app_nn.py App that demonstrates nearest neighbor query to current cursor
12+
while the KD tree is being constructed
13+
14+
The applications are self-launching. Simply load each one in Idle and execute.
15+
16+
When reviewing the code you may be surprised to see that the nearest() function may
17+
execute two recursive calls. This happens if the logic determines that the nearest
18+
point might be in either of the above or below child trees, and it can't conclusively
19+
determine without checking both. This happens when the perpendicular distance (to the
20+
axis along which the node partitions the plane) is in fact smaller than the current
21+
mind distance being passed in the recursion. When this happens, it is possible that
22+
the minimum distance point is in either partition, so the code must check both.
23+
24+
Change Log
25+
26+
1. 2014.05.23 KDNode:nearest() function
27+
defect: in double recursion case, was comparing
28+
distance to self.above (and self.below)
29+
instead of the returned point pt.
30+
31+
2. 2014.05.23 changes name of import in app_nn.py to reflect kdtree.py

‎5. KD Tree Data Structure/app.py‎

Lines changed: 78 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,78 @@
1+
# MouseClick.py - To demonstrate Tkinter key clicks
2+
3+
import Tkinter
4+
from kdtree import *
5+
6+
class KDTreeApp:
7+
def __init__(self):
8+
"""App for creating KD tree dynamically"""
9+
10+
self.tree = KDTree()
11+
12+
self.master = Tkinter.Tk()
13+
self.w = Tkinter.Frame(self.master, width=410, height=410)
14+
self.canvas = Tkinter.Canvas(self.w, width=400, height=400)
15+
16+
self.paint()
17+
18+
self.canvas.bind("<Button-1>", self.click)
19+
self.w.pack()
20+
self.w.mainloop()
21+
22+
def toCartesian(self, y):
23+
"""Convert y-coordinate into Cartesian equivalent"""
24+
return self.w.winfo_height() - y
25+
26+
def toTk(self,y):
27+
"""Convert Cartesian coordinate into Tk-equivalent"""
28+
if y == maxValue: return 0
29+
tk_y = self.w.winfo_height()
30+
if y != minValue:
31+
tk_y -= y
32+
return tk_y
33+
34+
def click(self, event):
35+
"""Add point to KDtree"""
36+
p = (event.x, self.toCartesian(event.y))
37+
38+
self.tree.add(p)
39+
self.paint()
40+
41+
def drawPartition (self, r, p, orient):
42+
if orient == VERTICAL:
43+
self.canvas.create_line(p[X_], self.toTk(r.y_min), p[X_], self.toTk(r.y_max))
44+
else:
45+
xlow = r.x_min
46+
if r.x_min == minValue: xlow = 0
47+
xhigh = r.x_max
48+
if r.x_max == maxValue: xhigh = self.w.winfo_width()
49+
50+
self.canvas.create_line(xlow, self.toTk(p[Y_]), xhigh, self.toTk(p[Y_]))
51+
52+
self.canvas.create_rectangle(p[X_] - 4, self.toTk(p[Y_]) - 4, p[X_] + 4, self.toTk(p[Y_]) + 4, fill='Red')
53+
54+
def visit (self, n):
55+
if n == None: return
56+
57+
self.drawPartition(n.region, n.point, n.orient)
58+
59+
self.visit (n.below)
60+
self.visit (n.above)
61+
62+
def prepare(self, event):
63+
"""prepare to add points"""
64+
if self.label:
65+
self.label.destroy()
66+
self.label = None
67+
self.canvas.pack()
68+
69+
def paint(self):
70+
if self.tree.root:
71+
self.visit(self.tree.root)
72+
else:
73+
self.label = Tkinter.Label(self.w, width=100, height = 40, text="Click To Add Points")
74+
self.label.bind("<Button-1>", self.prepare)
75+
self.label.pack()
76+
77+
if __name__ == "__main__":
78+
KDTreeApp()

‎5. KD Tree Data Structure/app_nn.py‎

Lines changed: 121 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,121 @@
1+
# App to demonstrate NearestNeighbor queries in action
2+
import Tkinter
3+
from kdtree import *
4+
5+
class KDTreeApp:
6+
def __init__(self):
7+
"""App for creating KD tree dynamically"""
8+
9+
self.tree = KDTree()
10+
self.match = None
11+
self.redraw = False
12+
self.shortline = None
13+
14+
self.master = Tkinter.Tk()
15+
self.w = Tkinter.Frame(self.master, width=410, height=410)
16+
self.canvas = Tkinter.Canvas(self.w, width=400, height=400)
17+
18+
self.paint()
19+
20+
self.canvas.bind("<Button-1>", self.click)
21+
self.canvas.bind("<Motion>", self.moved)
22+
self.w.pack()
23+
self.w.mainloop()
24+
25+
def toCartesian(self, y):
26+
return self.w.winfo_height() - y
27+
28+
def toTk(self,y):
29+
if y == maxValue: return 0
30+
tk_y = self.w.winfo_height()
31+
if y != minValue:
32+
tk_y -= y
33+
return tk_y
34+
35+
def view(self):
36+
"""Show window with points"""
37+
38+
def moved(self, event):
39+
"""React to mouse move events"""
40+
p = (event.x, self.toCartesian(event.y))
41+
42+
match = self.tree.find(p)
43+
if match:
44+
self.redraw = True
45+
p = match.point
46+
self.canvas.create_rectangle(p[X_] - 4, self.toTk(p[Y_]) - 4, p[X_] + 4, self.toTk(p[Y_]) + 4, fill='Red')
47+
self.canvas.delete(self.shortline)
48+
self.shortline = None
49+
else:
50+
if self.redraw:
51+
self.paint()
52+
self.redraw = False
53+
n = self.tree.nearest(p)
54+
if n:
55+
pn = n.point
56+
if self.shortline is None:
57+
self.shortline = self.canvas.create_line(pn[X_], self.toTk(pn[Y_]), p[X_], self.toTk(p[Y_]), tags="shortline")
58+
else:
59+
self.canvas.coords("shortline", pn[X_], self.toTk(pn[Y_]), p[X_], self.toTk(p[Y_]))
60+
61+
62+
def click(self, event):
63+
"""Add point to KDtree"""
64+
p = (event.x, self.toCartesian(event.y))
65+
66+
self.tree.add(p)
67+
if self.shortline:
68+
self.canvas.delete(self.shortline)
69+
self.shortline = None
70+
71+
self.paint()
72+
73+
def drawPartition (self, r, p, orient):
74+
if orient == VERTICAL:
75+
self.canvas.create_line(p[X_], self.toTk(r.y_min), p[X_], self.toTk(r.y_max))
76+
else:
77+
xlow = r.x_min
78+
if r.x_min == minValue: xlow = 0
79+
xhigh = r.x_max
80+
if r.x_max == maxValue: xhigh = self.w.winfo_width()
81+
82+
self.canvas.create_line(xlow, self.toTk(p[Y_]), xhigh, self.toTk(p[Y_]))
83+
84+
self.canvas.create_rectangle(p[X_] - 4, self.toTk(p[Y_]) - 4, p[X_] + 4, self.toTk(p[Y_]) + 4, fill='Black')
85+
86+
def visit (self, n):
87+
if n == None: return
88+
89+
self.drawPartition(n.region, n.point, n.orient)
90+
91+
self.visit (n.below)
92+
self.visit (n.above)
93+
94+
def prepare(self, event):
95+
"""prepare to add points"""
96+
if self.label:
97+
self.label.destroy()
98+
self.label = None
99+
self.canvas.pack()
100+
101+
def paint(self):
102+
if self.tree.root:
103+
for child in self.canvas.winfo_children():
104+
child.destroy()
105+
self.visit(self.tree.root)
106+
else:
107+
self.label = Tkinter.Label(self.w, width=100, height = 40, text="Click To Add Points")
108+
self.label.bind("<Button-1>", self.prepare)
109+
self.label.pack()
110+
111+
112+
if __name__ == "__main__":
113+
KDTreeApp()
114+
115+
"""
116+
Change Log
117+
118+
1. 2014.05.23 import changed to use KDTree from kdtree.py file
119+
120+
121+
"""

0 commit comments

Comments
 (0)