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