De vez en cuando tengo que producir un libro de mapas para mostrar puntos de interés. Primer paso para crear páginas, utilizando mallas regulares:
No me gusta la solución porque a) hay algunas páginas con puntos únicos (por ejemplo, la página 25) en el borde yb) demasiadas páginas.
El primer problema es fácil de solucionar usando código; mueva el rectángulo de la extensión de la página al centro de la extensión de los puntos relevantes:
Todavía no me gusta, parece muy concurrido porque el número de páginas sigue siendo el mismo. ¡Recuerde, todos terminan siendo páginas de papel A3 reales en múltiples copias del informe!
Así que he cocinado un código que reduce el número de páginas. En este ejemplo de 45 a 34.
No estoy seguro de si este es el mejor resultado que se puede lograr,
¿Cuál es la mejor estrategia (pseudocódigo, publicación, biblioteca de Python) para barajar los puntos a fin de minimizar el número de rectángulos de tamaño dado para capturar todos los puntos? Seguramente, alguien lo descubrió en teoría de juegos, arte militar o industria pesquera
Esta es la actualización de la pregunta original:
Esto muestra la extensión real y el tamaño de página requerido:
Zoom más cercano que muestra 10 de 164 páginas:
Clase de entidad de punto de muestra
El tamaño del rectángulo puede cambiar tan pronto como se mantenga dentro de los límites, es decir, más pequeño está bien.
Respuestas:
Esta no es la respuesta, solo pensé en publicar la solución Python para aquellos interesados:
lo aplicó últimamente para la planificación de encuestas:
ACTUALIZAR:
Parece que para algunos patrones tratar con puntos 'extraviados' primero es el camino a seguir. He utilizado la cáscara 'casco convexo' para identificarlos, idea de whuber, no puedo encontrar la publicación, lo siento.
fuente
Esto parece una versión geométrica del problema de cobertura máxima que está estrechamente relacionado con el problema de cobertura de conjunto , y esos dos son NP-Complete.
Entonces, para resolverlo, uno podría usar la aproximación. Intentaría el siguiente algoritmo y parece funcionar perfectamente. Aunque debido a la complejidad del problema, no podemos encontrar la mejor respuesta.
Una implementación de este algoritmo, solo para círculo, está aquí: http://jsfiddle.net/nwvao72r/3/
fuente