Моя реализация алгоритма Бридсона Выборка Пуассона-Диска, похоже, застряла в бесконечном цикле

Question

Видео Себастион Лиге очень хорошо объяснило алгоритм Бридсона.

Чтобы упростить задачу,

1. Создать сетку ячеек, в которой естьстороны радиуса / sqrt (2).

2. Поместить начальную точку и список в качестве точки появления.

3. Поместить точку в ячейку в сетке.

4. Для любой точки появления, создать точку между радиусом и радиусом 2 *.

5. Посмотрите на ячейки в 2 единицах от ячейки новой точки.

6. Если содержит другие точки, сравните расстояние.

7. Если какая-либо точка ближе к новой точке, чем радиус, новая точка недействительна.

8. Если новая точка действительна, новая точка указывается как точка появления и помещается в ячейку в сетке.

9. Если точка вызова порождает слишком много недействительных точек, точка появленияудаляется и превращается в точку.

10. Повторяйте до тех пор, пока не появится больше точек появления.

11. Верните точки.

Я написал одно и то же в Python 3.7.2 и pygame 1.7 ~, но, как сказано в названии, я застрял в рекурсивном чистилище.

Я использовалодин класс Point () для этого алгоритма, который может показаться избыточным, учитывая, что pygame.Vector2 () существует, но мне потребовалось несколько элементов для отдельного алгоритма (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

Код, связанный сАлгоритм Бридсона:

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

Вероятно, наиболее важный шаг в вашем коде отсутствует:

Если новая точка действительна, новая точка указывается как точка появления и помещается в ячейку в сетке .

Предлагаю добавить точку к 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 в start <= x < stop.
Таким образом, останов должен быть 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:

---

Можно добиться еще лучшего результата, если всегда использовать 1-ю точку spawnpoints вместо случайной точки:

# spawnIndex = random.randint(0,len(spawnpoints)-1)
spawnIndex = 0 # 0 rather than random
spawnpoint = spawnpoints[spawnIndex]