Определите минимальное количество полигонов из шейп-файла, чтобы охватить область интереса

10

У меня есть большое количество шейп-файлов, представляющих интересующие области для анализа, который будет проводиться с использованием различных источников спутниковых изображений (IKONOS, RapidEye и т. Д.). К сожалению, на снимках не используется система траекторий, как, например, Landsat, поэтому экстенты сильно различаются.

У меня есть шейп-файлы, прикрепленные к каждому AOI, представляющие пределы различных приобретений изображений, все из которых уже были сочтены приемлемыми. Некоторые из этих шейп-файлов имеют 500 или более полигонов.

Мне нужно найти подход, предпочтительно тот, который можно автоматизировать (предпочтительно Python и ArcInfo 10, а также FOSS), чтобы определить наименьшее количество полигонов, охватывающих каждую из моих областей интересов.

arcgis-10.0 python shapefile geoprocessing Чед Хокинс
источник
3
В общем и целом, это трудная проблема NP, поэтому, скорее всего, потребуется какое-то мощное программное обеспечение. Один из подходов состоит в том, чтобы сформировать ее как целочисленную линейную программу: многоугольники разделяют AOI на «атомарные» многоугольники, и каждый исходный многоугольник либо полностью покрывает, либо не покрывает каждый атомный многоугольник. Эта информация может быть закодирована в двоичных векторах. Вы стремитесь минимизировать количество таких векторов, сумма которых равна 1 или больше в каждом компоненте. Работающие примеры того, как решить подобные проблемы, можно найти на сайтах mathematica.stackexchange.com/a/6888 и gis.stackexchange.com/a/27678 .
whuber

Ответы:

3

Как отметил Уубер, обобщение проблемы такого типа для поиска высококачественного решения было бы непросто, но такой подход может приблизить вас к цели без большой работы. Вот некоторый псевдокод, основанный на следующих предположениях:

  1. Область интересов A

  2. Набор полигонов Y, которые полностью покрывают 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

Идея состоит в том, что вы итеративно уменьшаете свою область интересов с помощью экстента спутника, который имеет наибольшее перекрытие с оставшейся областью интересов. AOI уменьшается на каждой итерации, пока ничего не останется. Это, вероятно, не будет оптимальным решением, но оно должно быть разумным и должно выполняться довольно быстро.

dblanchett
источник
0

Итак, у вас есть область A, представляющая некоторую область, и набор экстентов изображения, которые можно определить как набор Y.

Если я правильно понял, вы можете выполнять множество различных функций:

  1. обрезка экстерьера изображения областью A
  2. Выполните выбор по местоположению, используя многоугольники Экстента и опцию полностью содержит

Затем вы можете изучить области каждого из них и определить, есть ли у вас собственные выборки полигонов, выполнив некоторую пространственную сортировку геометрии с использованием ArcPy и курсоров.

Надеюсь, это поможет.

кодовая база 5000
источник
1
Можете ли вы подробнее рассказать о том, как использовать курсоры? Войдя, я предположил, что это как-то сводится к этому, но я не смог разработать методологию. Я решил начать с первых n полигонов в области, исключив из оставшихся многоугольников те, которые полностью содержатся, и продолжая выполнять итерации таким образом. Это может быть началом, но, конечно, у тех многоугольников с самыми большими областями, может не быть очень различной протяженности.
Чед Хокинс