Das deutsche Python-Forum

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)