Cómo minimizar el número de páginas dinámicas para asignar dispersos punto

Question

A partir de tiempo al tiempo tengo para producir mapbook para mostrar los puntos de interés. Primer paso para crear las páginas, el uso regular de malla:

No me gusta la solución porque: a) hay algunas páginas con puntos (por ejemplo, página 25) sentado en el borde y b) demasiadas páginas.

El primer problema es fácil de solucionar, mediante el código, - mover el rectángulo de la página de grado en el centro de los puntos relevantes medida:

Yo aún no le gusta, se ve muy concurrido porque el número de páginas sigue siendo el mismo. Recuerde, todos terminan siendo reales de papel A3 páginas en múltiples copias del informe !.

Así que he cocinado un código que reducir el número de páginas. En este ejemplo de 45 a 34.

No estoy seguro de si este el mejor resultado que se puede lograr,

¿Cuál es la mejor estrategia (pseudo código, la publicación, la biblioteca de Python) para reproducir de forma aleatoria a través de los puntos con el fin de minimizar el número de dado el tamaño de los rectángulos para capturar todos los puntos? Sin duda, alguien descubrió que en la teoría del juego, el arte militar o de la industria de la pesca

Esta es la actualización a la pregunta original:

Esta muestra real de la medida y el tamaño de página requiere:

Más cerca de zoom que muestra los 10 de 164 páginas:

Muestra De La Clase De Entidad De Punto

Rectángulo de tamaño puede cambiar tan pronto como se mantiene dentro de los límites, es decir, más pequeño está bien.

Answer 1

Esta no es la respuesta, yo pensaba que el post de Python solución para los que está interesado:

# ---------------------------------------------------------------------------
# PAGE MAKER
# 
# ---------------------------------------------------------------------------
# Import arcpy module
import arcpy, traceback, os, sys
from arcpy import env

width=650
height=500

try:
    def showPyMessage():
            arcpy.AddMessage(str(time.ctime()) + " - " + message)
    mxd = arcpy.mapping.MapDocument("CURRENT")
    points = arcpy.mapping.ListLayers(mxd,"points")[0]
    pgons = arcpy.mapping.ListLayers(mxd,"pages")[0]

    g=arcpy.Geometry()
    geometryList=arcpy.CopyFeatures_management(points,g)
    geometryList=[p.firstPoint for p in geometryList]
    curT = arcpy.da.InsertCursor(pgons,"SHAPE@")
    while True:
        nPoints=len(geometryList)
        small=[geometryList.pop(0)]
        for p in geometryList:
            small.append(p)
            mPoint=arcpy.Multipoint(arcpy.Array(small))
            ext=mPoint.extent
            cHeight=ext.height
            cWidth=ext.width
            if cHeight>height or cWidth>width:
                small.remove(p)
        mPoint=arcpy.Multipoint(arcpy.Array(small))
        ext=mPoint.extent
        xC=(ext.XMin+ext.XMax)/2
        yC=(ext.YMin+ext.YMax)/2
        LL=arcpy.Point (xC-width/2,yC-height/2)
        UL=arcpy.Point (xC-width/2,yC+height/2)
        UR=arcpy.Point (xC+width/2,yC+height/2)
        LR=arcpy.Point (xC+width/2,yC-height/2)
        pgon=arcpy.Polygon(arcpy.Array([LL,UL,UR,LR]))
        curT.insertRow((pgon,))
        short=filter(lambda x: x not in small,geometryList)
        arcpy.AddMessage('Grabbed %i points, %i to go' %(len(small),len(short)))
        if len(short)==0: break
        geometryList=short[:]
    del mxd
except:
    message = "\n*** PYTHON ERRORS *** "; showPyMessage()
    message = "Python Traceback Info: " + traceback.format_tb(sys.exc_info()[2])[0]; showPyMessage()
    message = "Python Error Info: " +  str(sys.exc_type)+ ": " + str(sys.exc_value) + "\n"; showPyMessage()

aplicado últimamente para el estudio de planificación:

ACTUALIZACIÓN:

Parece que para algunos patrones de tratar con 'perdida' puntos primero es el camino a seguir. He utilizado "convex hull" peel para identificar a ellos, la idea de whuber, no se puede encontrar el post, lo siento.

Answer 2

Esto se parece a una versión geométrica de la Máxima Cobertura Problema que está estrechamente relacionado con el Conjunto de la Cubierta Problema, y los dos son NP-Completos.

Por lo que para solucionar esto, se puede usar la aproximación. Me gustaría tratar el siguiente algoritmo y parece que funciona perfectamente. Aunque debido a la complejidad del problema, no podemos encontrar la mejor respuesta.

1. Foreach punto de generar N=10 rectángulos en el azar distancias; sólo para asegurarse de que el rectángulo que abarca el punto (cada rectángulo tiene al menos un punto pertenece a él y en cada punto pertenece al menos a un rectángulo)
2. Repita hasta que todos los puntos están cubiertos: obtener rectángulo que cubre el número máximo de descubierto puntos. Los puntos de la marca como cubierto.

una implementación de este algoritmo, sólo para el círculo, está aquí: http://jsfiddle.net/nwvao72r/3/