What is wrong with this recursive quadtree/subdivision algorithm?

Issue

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()
``````

Answered By – Rabbid76

This Answer collected from stackoverflow, is licensed under cc by-sa 2.5 , cc by-sa 3.0 and cc by-sa 4.0