这种递归Quadtree/细分算法有什么问题？

Question

如果窗口内有一定的点，则应该找到此功能，以及是否在其周围有一个矩形，然后通过递归调用上一个矩形所有四个象限的相同函数来细分。这种行为对于前两个递归几乎是正确的，然后似乎有点糟糕。.我还设定了一个最大深度，以使其不会恢复太久。我使用pygame在屏幕上绘制矩形。我假设我在某个地方的逻辑中陷入困境。

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

我还称其为启动递归：

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

使用以下方式生成：这些点是使用以下方式生成的：

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

Answer 1

当用您必须指定顶部，左点以及宽度和高度，而不是右下点。
此外，中心的计算是错误的。最大深度为30（2^30）太多了，您可以使用//（落地）操作员。

以最大= 5和total_points＆gt; = 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)

---

最小示例：

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