pythonrecursionpygamequadtree

What is wrong with this recursive quadtree/subdivision algorithm?


this function is supposed to find if there is above a set number of points within the window, and if there is draw a rectangle around it and then subdivide by recursively calling the same function on all four quadrants of the previous rectangle. The behaviour seems almost right for the first 2 recursions and then seems to go a bit awry.. I also set a max depth so that it dosn't recurse too long. Im using pygame to draw the rectangles on the screen. Im assuming I have got muddled in my logic somewhere.

def recursion(x,x2,y,y2,max):
    #draws a square
    pygame.draw.rect(screen,(0,255,255),(x,y,x2,y2),1)

    currentMax = 0
    total_points = 0
    if max >= 30:
        return None
    currentMax = max + 1
   
    for i in range(len(xlist)):
        if xlist[i] in range(x,x2) and ylist[i] in range(y,y2):
            total_points += 1
    if total_points > 3:
      recursion(int(x),int(x2/2),int(y),int(y2/2),currentMax)#top_left
      recursion(int(x2/2),int(x2),int(y),int(y2/2),currentMax)#top_right
      recursion(int(x),int(x2/2),int(y2/2),int(y2),currentMax)#bottom_left 
      recursion(int(x2/2),int(x2),int(y2/2),int(y2),currentMax)#bottom_right

I also call it once to start the recursion with:

recursion(int(0),int(1000),int(0),int(1000),0)

The points are generated using:

for i in range(5):
    xlist.append(random.randint(0,1000))
    ylist.append(random.randint(0,1000))

Solution

  • When drawing a rectangle with pygame.draw.rect you have to specify the top, left point and the width and height instead of the bottom right point.
    Furthermore, the computation of the center is wrong. A maximum depth of 30 (2^30) is far too much and you can use the // (floor division) operator.

    Start with max >= 5 and total_points >= 1:

    def recursion(x,x2,y,y2,depth):
        if depth >= 5:
            return
        depth += 1
       
        total_points = 0
        for i in range(len(xlist)):
            if x < xlist[i] <= x2 and y < ylist[i] <= y2:
                total_points += 1
    
        if total_points >= 1:
            pygame.draw.rect(screen, (0,255,255), (x, y, x2-x, y2-y), 1)
            centerx = (x+x2) // 2
            centery = (y+y2) // 2
            recursion(x,       centerx, y,       centery, depth)
            recursion(centerx, x2,      y,       centery, depth)
            recursion(x,       centerx, centery, y2,      depth)
            recursion(centerx, x2,      centery, y2,      depth)
    

    Minimal example:

    import pygame, random
    
    pygame.init()
    screen = pygame.display.set_mode((500, 500))
    clock = pygame.time.Clock()
    
    def recursion(x,x2,y,y2,depth):
        if depth >= 5:
            return
        depth += 1
       
        total_points = 0
        for i in range(len(xlist)):
            if x < xlist[i] <= x2 and y < ylist[i] <= y2:
                total_points += 1
    
        if total_points >= 1:
            pygame.draw.rect(screen, (0,255,255), (x, y, x2-x, y2-y), 1)
            centerx = (x+x2) // 2
            centery = (y+y2) // 2
            recursion(x,       centerx, y,       centery, depth)
            recursion(centerx, x2,      y,       centery, depth)
            recursion(x,       centerx, centery, y2,      depth)
            recursion(centerx, x2,      centery, y2,      depth)
    
    xlist = []
    ylist = []
    for i in range(5):
        xlist.append(random.randrange(screen.get_width()))
        ylist.append(random.randrange(screen.get_height()))
    
    screen.fill(0)
    recursion(0, screen.get_width(), 0, screen.get_height(), 0)
    for p in zip(xlist, ylist):
        pygame.draw.circle(screen, (255, 0, 0), p, 8)
    pygame.display.flip()
    #pygame.image.save(screen, "grid.png")
    
    run = True
    while run:
        for event in pygame.event.get():
            if event.type == pygame.QUIT:
                run = False 
    
        pygame.display.flip()
        clock.tick(60)
    
    pygame.quit()
    exit()