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

Question

A video by Sebastion Lague explained the Bridson's algorithm really well.

过度简化，

1. Create cell grid that has sides of radius/sqrt(2).

2. Place initial point and list as spawnpoint.

3. Place point into cell in grid.

4. For any spawnpoint, spawn a point between radius and 2*radius.

5. Look at the cells 2 units away from cell of new point.

6. If contains other points, compare distance.

7. If any point is closer to new point than the radius, new point is invalid.

8. If new point is valid, new point is listed as spawnpoint and placed into cell in grid.

9. If spawnpoint spawns too many invalid points, spawnpoint is removed and turns into point.

10. Repeat until no more spawnpoints exists.

11. Return points.

我基本上在 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

            newPointIndex = [int(newPoint.x//cellSize), int(newPoint.y//cellSize)]
            neighbours = FindNeighbours(cellNumberX,cellNumberY,newPointIndex,cellGrid)

            for neighbour in neighbours:
                if newPoint.DistanceToSquared(neighbour) < radius**2:
                    isValid = False
                    break

            if isValid:
                points.append(newPoint)
                spawnpoints.append(newPoint)
                spawned = True
                break
            else:
                continue

        if spawned == False:
            spawnpoints.remove(spawnpoint)

    return points

def FindNeighbours(cellNumberX, cellNumberY, index, cellGrid):
    neighbours = []
    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))):
            if cellGrid[cellX][cellY] != None:
                neighbours.append(cellGrid[cellX][cellY])
    return neighbours

请帮忙。

Answer 1

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

8. If new point is valid, new point is listed as spawnpoint and placed into cell in 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)在 start <= x < stop 中为 x 创建一个范围.
所以止损点必须是index[0]+3而不是 index[0]+2 .

进一步控制 2 个嵌套的范围 for循环，从 x-2 运行至 y+2而不是来自 x-2至 x+2分别来自y-2至 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]