我对 Bridson 算法 Poisson-Disk Sampling 的实现似乎陷入了无限循环

Question

Sebastion Lague 的一段视频很好地解释了 Bridson 的算法。过于简单化，创建具有半径/sqrt(2) 边的单元格网格。放置初始点并将列表作为生成点。将点放入网格中的单元格中。对于任何生成点，生成半径和 2*radius 之间的点。查看距离新点单元格 2 个单位的单元格。如果包含其他点，则比较距离。如果任何点比半径更接近新点，则新点无效。如果新点有效，则将新点列为生成点并放入网格中的单元格中。如果 spawnpoint 生成了太多无效点，则 spawnpoint 将被删除并变成点。重复直到不再存在生成点。返回积分。我在 Python 3.7.2 和 pygame 1.7~ 中基本上写了同样的东西，但正如标题中所说，我陷入了递归炼狱。我为这个算法使用了一个 Point() 类，考虑到 pygame.Vector2() 存在，这似乎是多余的，但我需要一些元素用于需要这个类才能工作的单独算法（具有无限顶点的 Delaunay）。为了简单起见，我将删除所有特定于 Delaunay 的元素，并展示该算法所需的此类的基本框架：class Point:    def __init__(self, x, y):        self.x = x        self.y = y    def DistanceToSquared(self,other):        return (self.x-other.x)**2 + (self.y-other.y)**2与 Bridson 算法相关的代码是：def PoissonDiskSampling(width, height, radius, startPos = None, spawnAttempts = 10):    if startPos == None:        startPos = [width//2,height//2]    cellSize = radius / math.sqrt(2)    cellNumberX = int(width // cellSize + 1)  # Initialise a cells grid for optimisation    cellNumberY = int(height // cellSize + 1)    cellGrid = [[None for x in range(cellNumberX)] for y in range(cellNumberY)]    startingPoint = Point(startPos[0],startPos[1]) # Add an iniial point for spawning purposes    cellGrid[startingPoint.x//radius][startingPoint.y//radius] = startingPoint    points = [startingPoint] # Initialise 2 lists tracking all points and active points    spawnpoints = [startingPoint]    while len(spawnpoints) > 0:        spawnIndex = random.randint(0,len(spawnpoints)-1)        spawnpoint = spawnpoints[spawnIndex]        spawned = False        for i in range(spawnAttempts):            r = random.uniform(radius,2*radius)            radian = random.uniform(0,2*math.pi)            newPoint = Point(spawnpoint.x + r*math.cos(radian),                            spawnpoint.y + r*math.sin(radian))            if 0 <= newPoint.x <= width and 0 <= newPoint.y <= height:                isValid = True            else:                continue

Answer 1

您的代码中可能缺少最重要的步骤：

如果新点有效，则将新点列为 spawnpoint 并放入 grid 中的单元格中。

我建议将这一点添加到cellGrid是否有效：

if isValid:

    cellGrid[newPointIndex[0]][newPointIndex[1]] = newPoint

    points.append(newPoint)

    spawnpoints.append(newPoint)

    spawned = True

    break

newPointIndex此外，在可以添加点之前，您必须验证具有索引的单元格是否尚未被占用：

newPointIndex = [int(newPoint.x/cellSize), int(newPoint.y/cellSize)]

if cellGrid[newPointIndex[0]][newPointIndex[1]] != None:

    continue

neighbours = FindNeighbours(cellNumberX,cellNumberY,newPointIndex,cellGrid)

最后，函数存在问题FindNeighbours。range(start, stop)为 x in 创建一个范围start <= x < stop。

所以停止必须是index[0]+3而不是index[0]+2。

此外，控制 2 个嵌套for循环的范围从x-2toy+2而不是 from x-2tox+2分别从y-2to运行y+2：

for cellX in range(max(0,(index[0]-2)), min(cellNumberX,(index[1]+2))):

   for cellY in range(max(0,(index[0]-2)), min(cellNumberY,(index[1]+2)))

固定功能必须是：

def FindNeighbours(cellNumberX, cellNumberY, index, cellGrid):

    neighbours = []

    for cellX in range(max(0, index[0]-2), min(cellNumberX, index[0]+3)):

        for cellY in range(max(0, index[1]-2), min(cellNumberY, index[1]+3)):

            if cellGrid[cellX][cellY] != None:

                neighbours.append(cellGrid[cellX][cellY])

    return neighbours

查看结果，尺寸为 300 x 300，半径为 15：

spawnpoints如果始终使用第一个点而不是随机点，则可以获得更好的结果：

# spawnIndex = random.randint(0,len(spawnpoints)-1)

spawnIndex = 0 # 0 rather than random

spawnpoint = spawnpoints[spawnIndex]