Eu tenho uma grade de peças de tamanho finito conhecido que forma um mapa. Algumas das peças dentro do mapa são colocadas em um conjunto conhecido como território. Este território está conectado, mas nada se sabe sobre sua forma. Na maioria das vezes, era um blob bastante regular, mas poderia ser muito alongado em uma direção e potencialmente até ter orifícios. Estou interessado em encontrar a fronteira (externa) do território.
Ou seja, eu quero uma lista de todos os ladrilhos que tocam em um dos ladrilhos no território sem ele próprio estar no território. Qual é uma maneira eficiente de encontrar isso?
Para uma dificuldade extra, acontece que meus blocos são hexágonos, mas suspeito que isso não faça muita diferença, cada bloco ainda é rotulado com uma coordenada inteira xey, e, dado um bloco, posso encontrar facilmente seus vizinhos. Abaixo estão alguns exemplos: o preto é o território e o azul a borda que quero encontrar.
Isso por si só, não é um problema difícil. Um algoritmo simples para isso, em pseudo-python, é:
def find_border_of_territory(territory):
border = []
for tile in territory:
for neighbor in tile.neighbors():
if neighbor not in territory and neighbor not in border:
border.add(neighbor)No entanto, isso é lento e eu gostaria de algo melhor. Eu tenho um loop O (n) sobre o território, outro loop (um curto, mas ainda) sobre todos os vizinhos e, em seguida, tenho que verificar a associação em duas listas, uma das quais é do tamanho n. Isso fornece uma terrível escala de O (n ^ 2). Posso reduzi-lo para O (n) usando conjuntos em vez de listas para fronteira e território, para que a associação seja rápida, mas ainda não é ótima. Espero que existam muitos casos em que o território é grande, mas a fronteira é pequena devido a uma simples área versus escala de linha. Por exemplo, se o território é um hexágono de raio 5, é do tamanho 91, mas a borda é apenas do tamanho 36.
Alguém pode propor algo melhor?
Editar:
Para responder a algumas das perguntas abaixo. O território pode variar em tamanho, de cerca de 20 a 100 ou mais. O conjunto de peças que formam o território é um atributo de um objeto, e é esse objeto que precisa de um conjunto de todas as peças de borda.
Inicialmente, o território é criado como um bloco e, em seguida, ganha principalmente peças uma a uma. Nesse caso, é verdade que a maneira mais rápida é manter um conjunto de bordas e atualizá-lo apenas no bloco ganho. Ocasionalmente, uma grande mudança no território pode acontecer - portanto, ele precisará ser recalculado completamente.
Agora sou da opinião de que fazer um algoritmo simples para encontrar fronteiras é a melhor solução. A única complexidade adicional que isso gera é garantir que a borda seja recalculada toda vez que for necessário, mas não mais do que isso. Estou bastante confiante de que isso pode ser feito de maneira confiável na minha estrutura atual.
Quanto ao tempo, no meu código atual, tenho algumas rotinas que precisam verificar todos os blocos do território. Nem todo turno, mas na criação e, ocasionalmente, depois. Isso leva mais de 50% do tempo de execução do meu código de teste, mesmo que seja uma parte muito pequena do programa completo. Eu estava, portanto, empenhado em minimizar qualquer repetição. NO ENTANTO, o código de teste envolve muito mais criação de objetos do que uma execução normal do programa (naturalmente), então eu sei que isso pode não ser muito relevante.
fonte
Respostas:
Encontrar um algoritmo geralmente é melhor feito com uma estrutura de dados que facilita o algoritmo.
Nesse caso, seu território.
O território deve ser um conjunto não ordenado (O (1) de hash) de fronteiras e elementos.
Sempre que você adiciona um elemento ao território, itera sobre os blocos adjacentes e verifica se eles devem ser um bloco de borda; nesse caso, eles são um bloco de borda se não forem um bloco de elemento.
Sempre que subtrair um elemento do território, você assegura que seus blocos adjacentes ainda estejam no território e vê se você deve se tornar um bloco de borda. Se você precisar que isso seja rápido, faça com que os blocos de borda acompanhem sua "contagem adjacente".
Isso requer O (1) trabalho sempre que você adiciona ou remove um bloco de ou para um território. Visitar a borda leva O (comprimento da borda). Contanto que você queira saber "o que é a fronteira" significativamente mais frequentemente do que adicionar / remover elementos do território, isso deve vencer.
fonte
Se você também precisar encontrar bordas de buracos no meio do seu território, seu linear na área do território delimitado é o melhor que podemos fazer. Qualquer peça no interior pode ser um buraco que precisamos contar, então precisamos olhar para cada peça na área delimitada pelo contorno do território pelo menos uma vez para ter certeza de que encontramos todos os buracos.
Mas se você estiver preocupado apenas em encontrar a borda externa (não os orifícios internos), podemos fazer isso de forma um pouco mais eficiente:
Encontre uma extremidade que separa seu território. Você pode fazer isso ...
(se você conhece pelo menos um bloco de território e sabe que possui exatamente um blob de território conectado no seu mapa)
... começando em um bloco arbitrário em seu território e movendo-se para a borda mais próxima do seu mapa. Ao fazer isso, lembre-se da última aresta em que você fez a transição de um bloco de território para um bloco que não seja de território. Depois de atingir a borda do mapa, essa borda lembrada é a sua borda inicial.
Essa digitalização é linear no diâmetro do mapa.
ou (se você não souber onde algum dos blocos de seu território está adiantado ou se seu mapa pode conter vários territórios desconectados)
... começando em uma borda do mapa, digitalize ao longo de cada linha até atingir um terreno. A última aresta que você cruzou de não terrenos para terrenos é a sua aresta inicial.
Essa digitalização pode ser, na pior das hipóteses, linear na área do mapa (quadrática em seu diâmetro), mas se você tiver limites para restringir sua pesquisa (digamos, você sabe que o território quase sempre cruza as linhas do meio), você pode melhorar essa pior comportamento do caso.
Começando na extremidade inicial encontrada na etapa 1, siga-a pelo perímetro do terreno, adicionando cada lado que não seja da parte externa à coleção de bordas, até retornar à margem inicial.
Esta etapa de seguimento de aresta é linear no perímetro do contorno do terreno, e não na área. A desvantagem é que o código é mais complicado porque você precisa levar em conta cada tipo de curva que a borda pode dar e evitar a contagem dupla de bordas nas entradas.
Se os seus exemplos são representativos do tamanho real dos dados dentro de algumas ordens de magnitude, então eu faria a pesquisa de área ingênua - ainda será incrivelmente rápido em um número tão pequeno de blocos e é substancialmente mais simples de escrever , entenda e mantenha (normalmente levando a menos bugs!)
fonte
Aviso : se um bloco está ou não no limite depende apenas dele e de seus vizinhos.
Por causa disso:
É fácil executar essa consulta lentamente. Por exemplo: Você não precisa procurar o limite em todo o mapa, apenas no que é visível.
É fácil executar esta consulta em paralelo. Na verdade, eu poderia imaginar um código de sombreador que faça isso. E se você precisar para algo diferente dessa visualização, poderá renderizar uma textura e usá-la.
Se um bloco for alterado, o limite será alterado apenas localmente, o que significa que você não precisa calcular a coisa toda novamente.
Você também pode pré-calcular o limite. Ou seja, se você estiver preenchendo o hexadecimal, poderá decidir se um bloco é um limite nesse momento. Isso significa que:
Não use uma lista para o limite. Use um conjunto se for realmente necessário ( não sei para que você deseja o limite. ). No entanto, se você definir o limite de um bloco ou não um atributo do bloco, não precisará ir para outra estrutura de dados para verificar.
fonte
Mova sua área para cima um bloco, depois para cima, para a direita e para baixo para a direita, etc. Depois, remova a área original.
A mesclagem dos seis conjuntos deve ser O (n), classificando O (n.log (n)), definir diferença O (n). Se os blocos originais forem armazenados em algum formato classificado, o conjunto mesclado também poderá ser classificado em O (n).
Eu não acho que exista um algoritmo com menos de O (n), pois você precisa acessar cada bloco pelo menos uma vez.
fonte
Acabei de escrever um post sobre como fazer isso. Isso usa o primeiro método mencionado pelo @DMGregory, iniciando com uma célula de borda e marchando ao redor do perímetro. Está em C # em vez de Python, mas deve ser bem fácil de adaptar.
https://dillonshook.com/hex-city-borders/
fonte
POST ORIGINAL:
Como não posso comentar neste site, tentarei responder com um algoritmo de pseudocódigo.
Você sabe que todo território tem no máximo seis vizinhos que fazem parte da fronteira. Para cada bloco no território, adicione os seis blocos vizinhos a uma lista de fronteiras em potencial. Subtraia todos os blocos do território da borda e você ficará com apenas os blocos da borda. Funcionará melhor se você usar um conjunto não ordenado para armazenar cada lista. Espero ter sido útil.
EDITAR Existem maneiras muito mais eficazes que a iteração simples. Como tentei declarar na minha resposta (agora excluída) abaixo, você pode obter O (1) nos melhores casos e O (n) no pior caso.
Adicionando um bloco a um território O (1) - O (N):
No caso de nenhum vizinho, você simplesmente cria um novo território.
No caso de um vizinho, você adiciona o novo bloco ao território existente.
No caso de 5 ou 6 vizinhos, você sabe que está tudo conectado, portanto, adicione o novo bloco ao território existente. Essas são todas as operações O (1) e a atualização dos novos territórios de fronteira também é O (1), pois é uma mesclagem simples de um conjunto com outro.
No caso de 2, 3 ou 4 territórios vizinhos, talvez seja necessário mesclar até 3 territórios exclusivos. Este é O (N) no tamanho combinado do território.
Remoção de um ladrilho de um território O (1) - O (N):
Com zero vizinhos, apague o território. O (1)
Com um vizinho, remova o azulejo do território. O (1)
Com dois ou mais vizinhos, até 3 novos territórios podem ser criados. Este é O (N).
Passei meu tempo livre nas últimas semanas desenvolvendo um programa de demonstração que é um simples jogo de território baseado em hexadecimal. Tente aumentar sua renda colocando territórios próximos um do outro. 3 jogadores, vermelho, verde e azul competem para gerar mais receita colocando estrategicamente peças em um campo de jogo limitado.
Você pode baixar o jogo aqui (em formato .7z ) hex.7z
Controle simples do mouse O LMB coloca um bloco (só pode ser colocado onde está realçado com o mouse). Pontuação no topo, renda no fundo. Veja se você consegue criar uma estratégia eficaz.
O código pode ser encontrado aqui:
Eagle / EagleTest
Para criar a partir do código-fonte, você precisa do Eagle e do Allegro 5. Ambos são criados com o cmake. Atualmente, o jogo Hex é desenvolvido com o projeto CB.
Vire os votos negativos de cabeça para baixo. :)
fonte