Como calcular quantos polígonos posso colocar dentro de um polígono?

9

Eu costumo usar qgis. Explico meu problema com um exemplo: existe uma floresta (geometria irregular1) e uma árvore (geomery2). Quero saber o número máximo de árvores que a floresta pode conter. Além disso, eu quero uma saída shapefile da melhor disposição dessas árvores dentro da floresta.insira a descrição da imagem aqui

qgis polygon ksatzu
fonte
3
Bom problema ....
WKT
Eu não sei como eu começaria. Parece um problema / algoritmo do grau Maters.
HeikkiVesanto
2
Se você pode obter acesso a uma avaliação gratuita do ArcGIS (ou fazer o download gratuito do R), o software Geospatial Modeling Environment possui uma gencirclesinpolys (Generate Circles In Polygons)ferramenta que pode ser útil.
1313 Joseph
2
Você está procurando uma ferramenta para resolver problemas de embalagem, mas não conheço nenhum para o QGIS
underdark
11
@ Joseph Eu usei a ferramenta Geospatial Modeling Environment, ela funciona. Infelizmente, a ferramenta gera um arranjo regular de círculos (ou hexágonos) dentro dos limites dos polígonos, isso implica que a forma de saída não mostra (necessariamente) a melhor disposição dos recursos, quero dizer o número máximo possível dele.
Ksatzu

Respostas:

5

Experimente este aplicativo online svgnest.com/

etapas: 1. svg cria um arquivo (como na Figura 1); 2. Vá para o link e faça o upload de svg; 3. Selecione com o mouse o polígono do contêiner; 4. começar

após várias iterações, você pode bloquear e baixar o arquivo svg (veja a Figura 2)

NB: polígono e círculos devem estar no mesmo arquivo svg

figura 1

Figura 2

pigreco
fonte
4

Problema interessante!

Fiz uma coisa semelhante com polígonos irregulares (neste caso, os edifícios estavam lotados para não se sobrepor)

insira a descrição da imagem aqui

Utilizou postgresql e postgis, e python. O algoritmo aproximado foi

  • Localizar ponto aleatório na caixa delimitadora do polígono (ST_Envelope)
  • Se apontar para fora do polígono, volte um passo
  • Faça uma geometria para a árvore centralizada neste ponto aleatório
  • Se isso se sobrepuser a qualquer árvore colocada existente (ST_Overlaps), volte para iniciar
  • Adicionar árvore no ponto
  • Voltar ao início

Não posso garantir que isso ofereça o melhor global, você precisaria de um algoritmo de 'empacotamento circular' para isso (como outros já mencionaram).

Isso continuará para sempre, portanto, você precisará inserir algum código para decidir quando sair, por exemplo,

  • quando a área combinada de árvores colocadas é uma certa porcentagem da área do polígono
  • quando são necessárias mais de N iterações para encontrar uma árvore não sobreposta.

De acordo com a Circle Packing na Wikipedia, a melhor densidade de empacotamento é obtida com uma grade hexagonal. Pode ser possível criar uma grade usando o MMQGIS, cujo espaçamento é baseado no tamanho das suas árvores, que eu assumo serem idênticas. Em seguida, coloque uma árvore em cada vértice. Mas então, você tem o problema de saber onde posicionar a grade para maximizar o número de árvores.

Steven Kay
fonte