BridsonのアルゴリズムPoisson-DiskSamplingの実装が無限ループに陥っているようです

Sebastion Lagueによるビデオは、Bridsonのアルゴリズムを非常によく説明しています。

単純化しすぎると、

1. radius / sqrt（2）の辺を持つセルグリッドを作成します。

2. 最初のポイントを配置し、スポーンポイントとしてリストします。

3. ポイントをグリッドのセルに配置します。

4. スポーンポイントについては、半径と2 *半径の間のポイントをスポーンします。

5. 新しい点のセルから2単位離れたセルを見てください。

6. 他の点が含まれている場合は、距離を比較します。

7. 半径よりも新しい点に近い点がある場合、新しい点は無効です。

8. 新しいポイントが有効な場合、新しいポイントはスポーンポイントとしてリストされ、グリッドのセルに配置されます。

9. スポーンポイントがスポーンする無効なポイントが多すぎると、スポーンポイントが削除されてポイントに変わります。

10. スポーンポイントがなくなるまで繰り返します。

11. リターンポイント。

基本的にPython3.7.2とpygame1.7〜で同じことを書き留めましたが、タイトルで述べたように、再帰的な煉獄で立ち往生しています。

このアルゴリズムに1つの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

助けてください。