Determinar o número mínimo de polígonos do shapefile para cobrir uma área de interesse

Eu tenho um grande número de shapefiles representando áreas de interesse para uma análise que será realizada usando várias fontes de imagens de satélite (IKONOS, RapidEye, etc.). Infelizmente, as imagens não usam um sistema de caminho como o Landsat, por exemplo, portanto as extensões variam muito.

Eu tenho shapefiles recortados em cada AOI, representando as extensões de diferentes aquisições de imagens, todas já consideradas aceitáveis. Alguns desses shapefiles possuem 500 ou mais polígonos.

Preciso encontrar uma abordagem, de preferência uma que possa ser automatizada (Python e ArcInfo 10, de preferência, o FOSS também seria aceitável) para determinar o menor número de polígonos para cobrir cada uma das minhas áreas de interesse.

Conforme observado pela whuber, generalizar esse tipo de problema para encontrar uma solução de alta qualidade seria complicado, mas essa abordagem pode aproximá-lo o suficiente sem muito trabalho. Aqui está um pseudo-código com base nas seguintes suposições:

1. Área de Interesse A

2. Conjunto de polígonos Y que cobrem completamente A

   Start loop
    Iterate through Y
      Select the polygon x from Y that has greatest area of intersection with A
   
    Clip A with polygon x
    Remove x from Y 
    If A is null then end program
   

A idéia é que você esteja reduzindo iterativamente sua Área de Interesse com a extensão do satélite que tem a maior sobreposição com a Área de Interesse restante. A AOI fica menor a cada iteração até que nada seja deixado. Provavelmente, essa não será uma solução ideal, mas deve ser razoável e deve ser executada rapidamente.

Ok, você tem a área A que representa uma área e várias extensões de imagens que podem ser definidas como o conjunto Y.

Se eu estiver correto, você pode executar várias funções diferentes:

1. recorte as extensões de imagens pela área A
2. Execute uma seleção por local usando os polígonos de extensão e a opção contém completamente

Em seguida, você pode examinar as áreas de cada uma e determinar se possui polígonos auto-selecionados, fazendo uma classificação de geometria espacial usando ArcPy e cursores.

Espero que esta ajuda.