algoritmo para colocar el máximo número de puntos dentro de la restringida área en un espacio mínimo

Question

Tengo una capa de polígono que describe una restricción; quiero sumar puntos dentro de esta área. Quiero añadir tantos puntos como sea posible, pero deben tener un espacio mínimo entre ellos. Es posible hacer esto con GIS?

Para aclarar, lo mejor sería que si una cuadrícula ordenada puede ser generada, ya que permitiría garantizar la mayor cantidad de puntos. Sin embargo, la restricción rara vez permiten esto, y puede ser preferible a quitar puntos para permitir un desplazamiento para un mejor ajuste dentro de la restricción.

Answer 1

Yo no conozco a ninguna herramienta SIG para hacer eso, pero tengo una idea en el algoritmo.

En primer lugar, una aproximación del punto máximo número puede ser obtenido con esta fórmula:

Nb = 4.A / Pi.d^2

(donde A es el área del polígono y d el espaciamiento mínimo de distancia).

Entonces, para tratar de localizar estos puntos en el polígono, el mejor patrón no es el cuadrado de la cuadrícula, pero la rejilla hexagonal. Ver:

Por último, algunas técnicas de optimización de uso de la fuerza de los modelos podría ser utilizado para refinar la posición relativa de los puntos.

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

Answer 2

Ver el hilo en http://math.stackexchange.com/questions/15624/distribute-a-fixed-number-of-points-uniformly-inside-a-polygon . En particular, la nota de la referencia (en un comentario) "Poisson disco de proceso" y hacer algunas buscar en la Web. La conexión con la cuestión actual es que cuando usted puede distribuir un número determinado de puntos uniformemente, entonces usted puede de manera sistemática a aumentar ese número hasta que no hay más puntos se puede poner en el polígono y que resuelve el problema de maximizar el número de puntos sujetos a un mínimo requisito de la distancia. (Técnicamente, los dos problemas son el doble de problemas de optimización, en donde los objetivos y las restricciones son intercambiados.)

Answer 3

Creo que esto podría ser considerado como un "empaque" problema.

Si es así, es posible que desee probar un Algoritmo Genético, tal vez similar a la De los Algoritmos Genéticos para el Embalaje de los Polígonos.

Answer 4

La solución debe ser triángulos equiláteros, http://en.wikipedia.org/wiki/Equilateral_triangle. Sólo pregunta es la longitud de los lados y el "x-y-offset" en relación a su polígono.

(igual que la malla hexagonal se menciona a continuación)