Sprich:
Ich habe eine n Zahl an Punkten mit k Dimensionen und einen Punkt zu dem der nächst gelegende gefunden werden soll.
Er funktioniert auch eigentlich, bloß es kommen nur ungefähr die richtigen Punkte raus und nicht die absolut Nächsten.
Code: Alles auswählen
class kd_Tree:
def __init__(self,k):
self.firstNode = None
self.k = k
def createTree(self,points,axis=0):
class Node:
def __init__(self,pointList,t):
self.pointList = pointList
self.lowNode = None
self.highNode = None
self.mAxis = 0
self.t = t
pointList = points+[]
placedPoints = []
n = 1
t = 1
k = self.k
while len(placedPoints) != len(points):
if n == 1:
firstNode = node = Node(points,t)
currentNodes = [node]
newNodes = []
elif n > 5:
break
else:
newNodes = []
for node in currentNodes:
pointList = node.pointList
if len(pointList) == 1:
placedPoints.append(pointList[0])
elif len(pointList) == 0:
continue
mAxis = 0#Achse die die Punktmenge unterteilt
for point in pointList:
mAxis += point[axis]
mAxis /= len(pointList)
node.mAxis = mAxis
pointsLow = []
pointsHigh = []
for point in pointList:
if point[axis] < mAxis:
pointsLow.append(point)
else:
pointsHigh.append(point)
node.lowNode = Node(pointsLow,t)
node.highNode = Node(pointsHigh,t)
newNodes.append(node.lowNode)
newNodes.append(node.highNode)
t += 1
axis += 1
if axis > k-1:
axis = 0
currentNodes = newNodes+[]
n += 1
kd_Tree.firstNode = firstNode
def nearestNeighbour(self,point):
node = self.firstNode
axis = 0
k = self.k
while len(node.pointList) > 1:
if point[axis] < node.mAxis:
node = node.lowNode
else:
node = node.highNode
bestNode = node
axis += 1
if axis > k-1:
axis = 0
return bestNode.pointList
kd_Tree = kd_Tree(2)
kd_Tree.createTree(points)
testPoint = (0,4)
neighbour = kd_Tree.nearestNeighbour(testPoint)lg theotter
