Minimalizowanie liczby stron dynamicznych w celu mapowania rozproszonych punktów za pomocą ArcGIS Desktop?

Od czasu do czasu muszę tworzyć mapy, aby pokazać interesujące miejsca. Pierwszy krok do tworzenia stron przy użyciu zwykłej siatki:

Nie podoba mi się to rozwiązanie, ponieważ a) jest kilka stron z pojedynczymi punktami (np. Strona 25) siedzącymi na krawędzi ib) zbyt wielu stron.

Pierwszy problem można łatwo naprawić za pomocą kodu, - przenieś prostokąt zasięgu strony na środek zakresu odpowiednich punktów:

Nadal mi się to nie podoba, wygląda na bardzo zatłoczone, ponieważ liczba stron pozostaje taka sama. Pamiętaj, że wszystkie kończą się faktycznymi stronami A3 w wielu kopiach raportu!

Więc przygotowałem kod, który zmniejsza liczbę stron. W tym przykładzie od 45 do 34.

Nie jestem pewien, czy to najlepszy wynik, jaki można osiągnąć,

Jaka jest najlepsza strategia (pseudo kod, publikacja, biblioteka Python), aby przechodzić między punktami w celu zminimalizowania liczby prostokątów o danym rozmiarze w celu przechwycenia wszystkich punktów? Z pewnością ktoś odkrył to w teorii gier, sztuce wojskowej lub przemyśle rybnym

To jest aktualizacja pierwotnego pytania:

Pokazuje rzeczywisty zasięg i wymagany rozmiar strony:

Bliższe powiększenie pokazujące 10 ze 164 stron:

Przykładowa klasa elementów

Rozmiar prostokąta może się zmienić, gdy tylko znajdzie się w granicach, tzn. Mniejszy jest w porządku.

To nie jest odpowiedź, myślałem, że opublikuję rozwiązanie Python dla tych, którzy są zainteresowani:

# ---------------------------------------------------------------------------
# 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()

zastosował go ostatnio do planowania ankiet:

AKTUALIZACJA:

Wydaje się, że w przypadku niektórych wzorców zajmujących się „zbłąkanymi” punktami najpierw należy postępować. Użyłem skórki „wypukłego kadłuba”, aby je zidentyfikować, wyobrażenie o sobie, nie mogę znaleźć postu, przepraszam.

Wygląda to na geometryczną wersję problemu maksymalnego pokrycia, który jest ściśle związany z problemem ustawiania pokrycia , a te dwa są NP-Complete.

Aby to rozwiązać, można użyć przybliżenia. Wypróbowałbym następujący algorytm i wydaje się on działać idealnie. Chociaż ze względu na złożoność problemu nie możemy znaleźć najlepszej odpowiedzi.

1. Punkt przedni generuje N = 10 prostokątów w losowych odległościach; tylko po to, aby upewnić się, że prostokąt pokrywa punkt (każdy prostokąt ma co najmniej jeden punkt należy do niego i każdy punkt należy do co najmniej jednego prostokąta)
2. Powtarzaj, aż wszystkie punkty zostaną pokryte: uzyskaj prostokąt obejmujący maksymalną liczbę odkrytych punktów. Oznacz punkty jako objęte.

implementacja tego algorytmu, tylko dla koła, jest tutaj: http://jsfiddle.net/nwvao72r/3/