Gere áreas de tamanho igual no polígono

Estou procurando uma lógica de pseudo-código que encontre náreas de tamanho igual em um determinado polígono. Nenhum espaço deve estar entre ou fora das áreas correspondentes. A primeira correspondência válida de áreas deve ser retornada.

Supondo o seguinte polígono [2,2, 3,1, 5,1, 5,4, 4,5, 2,3]como uma entrada:

... e 3como parâmetro uma saída válida pode ser [ [2,2, 3,2, 3,3, 4,3, 4,5, 2,3], [2,2, 3,1, 5,1, 4,2, 4,3, 3,3, 3,2], [4,5, 4,2, 5,1, 5,4] ]:

Outra saída válida com o parâmetro 3é [ [3,4, 3,3, 4,3, 4,2, 3,2, 3,1, 2,2, 2,3], [4,3, 4,2, 3,2, 3,1, 5,1, 5,3], [3,4, 3,3, 5,3, 5,4, 4,5] ]:

Observe que as áreas não precisam compartilhar o mesmo ponto central. Uma ou mais áreas podem cair entre outras áreas dentro do polígono.

Aqui está outro exemplo de amostra de entrada / saída.

Supondo o seguinte polígono [1,3, 1,1, 7,1, 7,2, 8,2, 8,3, 5,6, 4,6]como uma entrada:

..e 5como parâmetro uma saída válida pode ser [ [1,3, 1,1, 3,1, 3,2, 4,3, 3,4, 3,3], [3,2, 3,1, 7,1, 7,2, 6,2, 6,3, 5,3, 5,2], [6,2, 8,2, 8,3, 6,5, 5,5, 5,4, 6,4], [1,3, 3,3, 3,4, 5,5, 6,4, 6,5, 7,5, 6,6, 5,6], [3,4, 4,3, 3,2, 5,2, 5,3, 6,3, 6,4, 5,4, 4,5] ]:

As seguintes premissas são feitas:

• direção de todas as fronteiras é divisível por 45

• coordenadas inteiras são usadas para todos os polígonos

• A área inteira do polígono de entrada é sempre divisível por n

• todos os polígonos podem ser tanto convexas ou côncavas queridos

• solucionáveis, as náreas de significado podem se encaixar adequadamente no polígono especificado

Não solucionável. Eu tentei vários métodos até perceber que não podia ser feito.

Assuma uma forma com a área 4, que deve ser dividida em 2 partes com a área 2 cada:

O triângulo e o quadrado mais à esquerda devem fazer parte da forma 1, mas precisam de outro triângulo. O único local que pode ser retirado é o quadrado à direita, mas o restante é dividido em duas regiões.

Como eu disse no meu comentário à resposta do Doc Browns (de outra forma excelente), existe uma questão de escolha da divisão quadrado> triângulo que torna um pouco mais difícil o dispositivo de um algoritmo. Além disso, você não precisa fazê-lo em série, mas pode fazê-lo em paralelo, como mostram algumas das minhas sugestões.

Fiz várias abordagens heurísticas no início.

Voronoi: Escolha N pontos (coordenadas não inteiras) na forma, crie um mapa de voronoi. Deixe os pontos se atraírem e repelirem um ao outro em relação à sua área (atrair muito grande, repelir muito pequeno).

Útil para E / S grandes, fácil de cair nos máximos locais.

Método de círculo: o objetivo é remover áreas problemáticas e continuar usando outro método.

Escolha um ponto (não inteiro) no interior e um raio r. O interior menos o círculo criará k sub-regiões desconectadas. Se alguma das sub-regiões for do tamanho A / n, remova-a. Além disso, se houver 2 * A / n, será fácil dividi-lo e removê-los também. Abaixe um pouco o raio e continue (possivelmente use alguma pesquisa binária).

Crescimento problemático de pontos: comece a usar o método que Doc Brown menciona, mas como existem duas opções no máximo, pule o gráfico e aumente cada região na borda de maneira a criar o mínimo possível de novos pontos problemáticos (pontos problemáticos = apenas triângulos) compartilhando uma borda com o restante da forma). Por exemplo, ao escolher novos vizinhos para incluir, adicione-os em ordem de convexidade (côncava = convexidade negativa)

Crescimento da fita: Para áreas quase convexas ou convexas. Escolha um ponto na borda externa, faça uma fita de largura da unidade seguir a borda externa até que ela tenha o comprimento certo, certificando-se de nunca criar um novo ponto desconectado. Se necessário, pule os últimos triângulos e faça-o crescer um pouco de largura. Deixe a próxima faixa de opções seguir onde a última terminou até a área final ter o tamanho certo.

Orgânico ou de jogo: crie N "países". Coloque-os em locais aleatórios. Deixe-os crescer organicamente. Quando eles se encontram, aquele com a menor área atual é o mais forte e vence o triângulo. Provavelmente propenso a máximos locais?

A estratégia geral deve ser remover a primeira parte da área A / n do seu polígono P0 (onde A é a área total), deixando um novo polígono P1 da área AA / n. Repita isso produzindo um polígono P2, depois P3 e depois de n repetições, você terá sua solução. Observe que em cada etapa é possível que você não consiga encontrar uma peça nova em que as peças restantes ainda formem um polígono conectado, no qual é necessário voltar uma etapa e tentar encontrar outra peça ou interromper o algoritmo sem resultado. .

Para construir esse pedaço de tamanho A / n, comece dividindo seu polígono em "pedaços de grade". Qualquer quadrado da grade dentro do polígono forma uma peça assim como qualquer meio quadrado em forma de triângulo, onde a borda do polígono divide o quadrado em duas metades. Você pode utilizar um teste de ponto no polígono para iterar sobre todos os meios-quadrados dentro da caixa delimitadora do polígono e testar se o ponto médio está dentro do polígono fornecido (se as duas metades de um quadrado estiverem contidas, é possível usar o quadrado cheio). Em seguida, você cria um gráfico planar, em que cada uma das peças define um vértice (com uma "área" ou "peso" de 1 ou 1/2). As arestas desse gráfico são dadas pelas peças vizinhas. Isso reduz seu problema geométrico a um problema gráfico, em que você está procurando um subgráfico conectado com vértices de peso total A / n, e o gráfico restante ainda está conectado .

O último problema pode ser resolvido com um retornoaproximação. Comece com um vértice que pode ser removido do gráfico sem torná-lo desconectado. Você pode escolher o vértice aleatoriamente, se quiser, ou embaralhar a lista de todos os vértices aleatoriamente uma vez, para reutilização nas etapas a seguir. Agora tente encontrar um segundo vértice que esteja conectado ao primeiro, que possa ser removido do gráfico restante sem destruir sua conexão também. Se houver várias possibilidades, escolha uma aleatoriamente. Para vértices que representam um quadrado, você também pode permitir uma operação gráfica em que você divide o quadrado em dois triângulos (isso cria novos vértices de peso 1/2) por uma ou outra maneira possível. Isso é apenas um pouco mais complicado do que apenas mover um vértice do gráfico original para o sub-gráfico, mas não deve ser muito difícil.

Repita isso até que seu subgráfico atinja um peso total A / n ou você não encontre outro vértice. Se for esse o caso, "retorne" um nível e tente um vértice diferente primeiro.

Existem várias maneiras de otimizar isso, por exemplo, você precisa escolher um teste rápido de conectividade para gráficos. Acho que você encontrará muitos algoritmos para esse subproblema, use o Google ou comece aqui . Pode valer a pena procurar um algoritmo que possa verificar rapidamente se um gráfico conectado ainda está conectado quando um vértice é removido.

Espero que isto ajude.