Buscando algoritmo para colocar o número máximo de pontos dentro da área restrita com espaçamento mínimo?

17

Eu tenho uma camada de polígono que descreve uma restrição; Desejo acrescentar pontos nesta área. Quero adicionar o máximo de pontos possível, mas eles devem ter um espaçamento mínimo entre eles. É possível fazer isso com o GIS?

Para esclarecer, seria melhor se uma grade ordenada pudesse ser gerada, pois isso garantiria mais pontos. No entanto, a restrição raramente permitiria isso, e pode ser preferível remover pontos para permitir que um deslocamento se ajuste melhor à restrição.

algorithm point Matthew Snape
fonte
1. sim 2. Deseja aleatória ou ordenada (grade)?
precisa saber é o seguinte
Parece haver duas perguntas. Deseja que um algoritmo faça isso fora do software? Ou você quer saber qual sistema GIS pode fazer isso?
Brad Nesom
1
Os pontos são restritos para que eles sejam> = a distância mínima do limite do polígono? Se, então, a pergunta pode ser mais claramente definida como: Como posso agrupar o número máximo de círculos em um polígono?
Kirk Kuykendall
De alguma forma relacionados: gis.stackexchange.com/q/4927/162
julien
1
@qva Não, não há, porque as soluções exatas que podem ser encontradas são assimétricas e difíceis de obter, mesmo para formas simples, como retângulos. Os melhores métodos de computação que encontrei são baseados no recozimento simulado espacial (e funcionam muito bem, embora exijam muita computação). Utilizando-os, procurei soluções para muitos polígonos de formas variadas. É claro que os limites do polígono controlam as soluções próximas aos limites; no interior, tendem a aproximar-se dos pacotes hexagonais de discos.
whuber

Respostas:

5

Eu acho que isso pode ser pensado como um problema de "empacotamento".

Nesse caso, convém tentar um algoritmo genético, talvez semelhante ao do algoritmo On Genetic for the Packing of Polygons .

Kirk Kuykendall
fonte
Referência interessante, obrigado. Uma rápida olhada sugere que o algoritmo do artigo precisa que os polígonos sejam retângulos. Você sabe se pode ser generalizado para polígonos arbitrários?
whuber
9

Não conheço nenhuma ferramenta GIS para fazer isso, mas tenho uma ideia sobre o algoritmo.

Primeiro, uma aproximação do número máximo de pontos pode ser obtida com esta fórmula:

Nb = 4.A / Pi.d^2

(onde Aé a área do polígono e da distância mínima de espaçamento).

Então, para tentar localizar esses pontos no polígono, o melhor padrão não é a grade quadrada, mas a grade hexagonal. Vejo:

quadrada vs grade hexagonal

Finalmente, algumas técnicas de otimização usando modelos de força podem ser usadas para refinar o posicionamento relativo dos pontos.

NB: É um problema bem conhecido na cristalografia .

julien
fonte
ferramenta gis para fazer isso ... ian-ko.com ponto aleatório do geo-assistente no polígono.
precisa saber é o seguinte
1
Obrigado! Mas a questão não é exatamente sobre pontos aleatórios no polígono, certo?
Jul11
Como uma aproximação rápida e suja inicial, a embalagem hexagonal funciona bem. Porém, quase nunca é o ideal. Eu esperaria que a melhoria potencial fosse proporcional ao comprimento do perímetro do polígono, portanto, para polígonos não tortuosos com muitos pontos, essa não é uma abordagem ruim.
whuber
6

Consulte o encadeamento em /math/15624/distribute-a-fixed-number-of-points-uniformly-inside-a-polygon . Em particular, observe a referência (em um comentário) ao "processo de disco de Poisson" e faça algumas pesquisas na Web. A conexão com a questão atual é que quando você pode distribuir um determinado número de pontos uniformemente, então você pode aumentar sistematicamente esse número até que não haja mais pontos pode ser colocado no polígono e que resolve o problema de maximizar o número de pontos sujeitos a uma requisito de distância mínima. (Tecnicamente, os dois problemas são problemas de otimização dupla, onde os objetivos e as restrições são trocados.)

whuber
fonte
0

A solução deve ser triângulos equilaterais, http://en.wikipedia.org/wiki/Equilateral_triangle . A única questão é o comprimento dos lados e o "deslocamento xy" em relação ao seu polígono.

(igual à grade hexagonal mencionada abaixo)

Uffe Kousgaard
fonte
1
Isso é verdade apenas dentro de um plano infinito. O limite de um polígono finito restringe severamente a configuração. Quando existem muitos pontos, eles formam aproximadamente triângulos equilaterais.
whuber