¿Busca algoritmo para colocar el número máximo de puntos dentro del área restringida con un espaciado mínimo?

17

Tengo una capa de polígono que describe una restricción; Deseo agregar puntos dentro de esta área. Quiero agregar tantos puntos como sea posible, pero deben tener un espacio mínimo entre ellos. ¿Es posible hacer esto con SIG?

Para aclarar, sería mejor si se pudiera generar una cuadrícula ordenada, ya que esto garantizaría la mayor cantidad de puntos. Sin embargo, la restricción raramente permitiría esto, y puede ser preferible eliminar puntos para permitir que un desplazamiento se ajuste mejor a la restricción.

algorithm point Matthew Snape
fuente
1. Sí 2. ¿Quieres aleatorio u ordenado (cuadrícula)?
Brad Nesom el
Parece ser dos preguntas. ¿Quieres un algoritmo para hacer esto fuera del software? ¿O quieres saber qué sistema SIG puede hacer esto?
Brad Nesom el
1
¿Están los puntos restringidos de modo que deben ser> = la distancia mínima desde el límite del polígono? Si es así, la pregunta podría formularse más claramente como: ¿Cómo puedo empaquetar el número máximo de círculos en un polígono?
Kirk Kuykendall el
Relacionado de alguna manera: gis.stackexchange.com/q/4927/162
julien
1
@qva No, no lo hay, porque las soluciones exactas que se pueden encontrar son asimétricas y difíciles de obtener incluso para formas simples como rectángulos. Los mejores métodos informáticos que he encontrado se basan en el recocido espacial simulado (y funcionan muy bien, aunque requieren muchos cálculos). Utilizándolos, he buscado soluciones para muchos polígonos de diferentes formas. Está claro que los límites del polígono controlan las soluciones cercanas a los límites; En el interior, tienden a aproximarse a los empaques hexagonales de los discos.
whuber

Respuestas:

5

Creo que esto podría considerarse como un problema de "embalaje".

Si es así, es posible que desee probar un Algoritmo genético, quizás uno similar al de Algoritmos genéticos para el embalaje de polígonos .

Kirk Kuykendall
fuente
Interesante referencia, gracias. Un vistazo rápido sugiere que el algoritmo del papel necesita que los polígonos sean rectángulos. ¿Sabes si se puede generalizar a polígonos arbitrarios?
whuber
9

No conozco ninguna herramienta SIG para hacer eso, pero tengo una idea sobre el algoritmo.

Primero, se puede obtener una aproximación del número máximo de puntos con esta fórmula:

Nb = 4.A / Pi.d^2

(donde Aestá el área del polígono y dla distancia mínima de separación).

Luego, para tratar de ubicar estos puntos en el polígono, el mejor patrón no es la cuadrícula cuadrada sino la cuadrícula hexagonal. Ver:

cuadrícula vs cuadrícula hexagonal

Finalmente, algunas técnicas de optimización que usan modelos de fuerza podrían usarse para refinar el posicionamiento relativo de los puntos.

NB: es un problema bien conocido en cristalografía .

julien
fuente
esta es la herramienta para hacer eso ... ian-ko.com punto aleatorio de geo-asistente en polígono.
Brad Nesom el
1
¡Gracias! Pero la pregunta no es exactamente sobre puntos aleatorios en el polígono, ¿verdad?
julien
Como una aproximación inicial rápida y sucia, el empaque hexagonal funciona bien. Sin embargo, casi nunca es óptimo. Esperaría que la mejora potencial sea proporcional a la longitud del perímetro del polígono, por lo que para polígonos no tortuosos con muchos puntos, este no es un mal enfoque.
whuber
6

Vea el hilo en /math/15624/distribute-a-fixed-number-of-points-uniformly-inside-a-polygon . En particular, tenga en cuenta la referencia (en un comentario) al "proceso de disco de Poisson" y realice algunas búsquedas en la Web. La conexión con la pregunta actual es que cuando puede distribuir un número dado de puntos de manera uniforme, entonces puede aumentar ese número sistemáticamente hasta que no se puedan colocar más puntos en el polígono y eso resuelve el problema de maximizar el número de puntos sujetos a un Distancia mínima requerida. (Técnicamente, los dos problemas son problemas de optimización dual donde los objetivos y las restricciones se intercambian).

whuber
fuente
0

La solución debe ser triángulos equiláteros, http://en.wikipedia.org/wiki/Equilateral_triangle . La única pregunta es la longitud de los lados y el "desplazamiento xy" en relación con su polígono.

(igual que la cuadrícula hexagonal mencionada a continuación)

Uffe Kousgaard
fuente
1
Esto es cierto solo dentro de un plano infinito. El límite de un polígono finito restringe severamente la configuración. Cuando hay muchos puntos, aproximadamente forman triángulos equiláteros.
whuber