Произвольно сгенерируйте Самодействующий Полигон на сетке размером M на N - PullRequest
Новая
       6

Произвольно сгенерируйте Самодействующий Полигон на сетке размером M на N

1 голос
/ 24 марта 2019

Мне нужен алгоритм, чтобы случайным образом генерировать самозападающий многоугольник на двумерной сетке, в пределах размера (M x N).Определение избегающего многоугольника находится на здесь .Это закрывающий путь (кольцо) в сетке, который не взаимодействует сам по себе.

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

Я могупродумал алгоритм генерации лабиринта, используя поиск в глубину, чтобы сгенерировать дерево wiki-link , тогда периметр округления дерева - это просто избегающий многоугольник.Но этот подход не может генерировать все возможные самоопределяющиеся многоугольники, такие как самый большой прямоугольник (M x N) в сетке.

A example

1 Ответ

0 голосов
/ 24 марта 2019

Следующий алгоритм сгенерирует 1 замкнутый многоугольник.Это не использует какие-либо концепции теории графов, хотя.Поскольку язык не был упомянут, я написал код на python.Его можно легко изменить, чтобы найти все полигоны, если это необходимо.

import random

currentpath = [(0,0)]
length = 2 #any actual grid is 3x3 length is 2 however
height = 2
initial = (0,0)
allpaths = []

def backtrack(currentpath,currentnode):
    if(currentnode == (0,0) and len(currentpath)>1):
        return True
    directions = [0,1,2,3]
    while(len(directions) > 0):
        x = random.choice(directions)
        if(x == 0):
            #left
            nextnode = (currentnode[0] + 1, currentnode[1])
            if(currentnode[0] == length or (nextnode in currentpath and nextnode != (0,0)) or (nextnode ==(0,0) and len(currentpath)<4)):
                directions.remove(x)
                continue
            else :
                currentpath.append(nextnode)
                if(backtrack(currentpath,nextnode)):
                    return True
                else :
                    directions.remove(x)
                    currentpath.remove(nextnode)
                    continue
        if(x == 1):
            #right
            nextnode = (currentnode[0] - 1, currentnode[1])
            if (currentnode[0] == 0 or (nextnode in currentpath and nextnode != (0,0)) or (nextnode ==(0,0) and len(currentpath)<4)):
                directions.remove(x)
                continue
            else:
                currentpath.append(nextnode)
                if(backtrack(currentpath,nextnode)):
                    return True
                else :
                    directions.remove(x)
                    currentpath.remove(nextnode)
                    continue
        if(x == 2):
            #up
            nextnode = (currentnode[0], currentnode[1] + 1)
            if (currentnode[1] == height or (nextnode in currentpath and nextnode != (0,0)) or (nextnode ==(0,0) and len(currentpath)<4)):
                directions.remove(x)
                continue
            else:
                currentpath.append(nextnode)
                if(backtrack(currentpath,nextnode)):
                    return True
                else :
                    directions.remove(x)
                    currentpath.remove(nextnode)
                    continue
        if(x == 3):
            #down
            nextnode = (currentnode[0], currentnode[1] - 1)
            if (currentnode[1] == 0 or (nextnode in currentpath and nextnode != (0,0)) or (nextnode ==(0,0) and len(currentpath)<4)):
                directions.remove(x)
                continue
            else:
                currentpath.append(nextnode)
                if(backtrack(currentpath,nextnode)):
                    return True
                else :
                    directions.remove(x)
                    currentpath.remove(nextnode)
                    continue
    if(len(directions)==0):
        return False

backtrack(currentpath,initial)
print (currentpath)
...