我对Bridson算法PoissonDisk采样的实现似乎陷入了一个无限循环

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.

我基本上在python3.7.2和pygame1.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]