Метод вычислительной оптимизации в задаче сопоставления растровой и векторной информации при анализе спутниковых данных

Географическая привязка растровых аэрокосмических изображений как правило осуществляется поточечно и представляет собой растровые поля широты и долготы. В практических задачах возникает проблема взаимного расположения точки растрового файла и объектов векторного, в частности - выяснения, лежит ли некоторая точка растрового файла в полигоне векторного. Учитывая, что векторные файлы могут содержать большое число записей, и требуется просмотр их всех, решение проблемы занимает значительное время.
Представлен метод, позволяющий уменьшить вычислительную сложность этой задачи в случае большого объема используемых файлов. Основываясь на количестве записей в векторном файле и на размере растрового файла, производится деление области векторного файла на равные ячейки. Записи этого файла организуются в виде списков для каждой ячейки. Для каждой точки растрового файла, для которой требуется проверить её положение в векторном файле, явным образом вычисляется номер ячейки в векторном файле и затем проверяется взаимное расположение лишь с теми записями, которые соответствуют данной ячейке, что значительно снижает вычислительную сложность алгоритма.
Данный метод экспериментально проверен на наборе растровых космических изображений MODIS и векторных шейпфайлах, содержащих данные об активных пожарах в виде полигонов. Приведены графики зависимости времени вычисления и объема занимаемой памяти от мелкости разбиения векторного файла при различных его объемах. Полученные значения эффективности метода позволяют применять его при решении практических задач. Работа выполнена в рамках НИР «Проблемно – ориентированные поисковые исследования в области разработки космических методов и технологий мониторинга и прогнозирования эмиссий вредных примесей в атмосферу при лесных и торфяных пожарах», проводимой в НИИ «Аэрокосмос» по государственному контракту № 16.515.11.5028.