Диссертация (1137226), страница 9
Текст из файла (страница 9)
Среднее число полигонов, пересекающих ячейку, установим из того, что число пересечений всех полигонов со всемиячейками равно числу пересечений всех ячеек с полигонами, и равночим1 . Обозна–– искомое среднее число полигонов, пересекающих ячейку. Всего ячеек /2 ,поэтому /2 = 1 ,откуда получаем:⎧⎪2⎪⎪⎨ 2 = 1= ⎪2⎪⎪⎩ Так как обрабатывается список длинойка внутри полигона, имеет сложность>.при(2.25)≤точек и проверка, лежит ли точ(1), получаем сложность сопоставления:⎧⎪⎪⎪⎨2 2 = = ⎪2⎪⎪⎩ При этом, отношениеприпри>.при(2.26)≤2 ограничено условием непересечения полигонов,из которого следует, что суммарная площадь всех полигонов меньше, чем площадь ограничивающего прямоугольника :2 < .Таким образом,2 =(), при при ≤ .
Из соотношений 2.26, 2.24 видно, что оптимальный размерячейки ≃ ,так как при увеличении растет сложность поиска точки, а сложность индексации не изменяется, а при уменьшении - наоборот, не изменяетсясложность поиска, но увеличивается сложность индексации.54Сложность метода в целом:(︂)︂22 = 1 + 2 = 1 + ()1= 1 ()+1 . При оптимальном выборе размера ячейки=(2.27)общая сложность составляет = () + ().(2.28)Оценим также объем памяти, необходимый для содержания структуры.При размере ячейки = количество ячеек, а, значит, объем памяти, необходимый структуре, оценивается как(( /)( /)), т.е. пропорционален площадиобласти векторного файла и обратно пропорционален характерной площади полигона.
На практике размеры полигонов различаются, поэтому действительнооптимальный размер ячейки может дать только экспериментальная проверка,но так или иначе, он должен быть одного порядка с характерным размеромполигона.2.4.3. Реализация и численный экспериментРазработанный алгоритм был реализован в виде программы для ЭВМ наязыке программирования Си для численного эксперимента по определению егобыстродействия и дальнейшего использовании.
Проверка работы алгоритма иопределение его быстродействия были проведены с использованием действительных данных дистанционного зондирования. В качестве векторных файловиспользовались векторные файлы (шейпфайлы), содержащие полигоны – территории, пострадавшие от природных пожаров, сформированные автоматическина основе космических изображений MODIS с пространственным разрешением1км в надире. Точки земной поверхности, положение которых по отношениюк полигонам векторного файла проверялось, брались из файла другого изоб55ражения MODIS, растрового изображения территории, пересекающей областьвекторного файла, содержащего более43миллионов пикселей.
Средняя площадь зоны активного горения лесного пожара составляет менее квадратногокилометра [11], на изображении детектированный пожар отображается чащевсего одним пикселем, и при формировании векторных данных представляется в виде четырехугольника. Исходя из оценки алгоритмической сложности,наименьшее время работы должно быть при размерах ячейки, близких размеру пикселя. Во всех исследованных векторных файлах, содержащих реальныеспутниковые данные об активных пожарах, средний размер полигона составил0, 015 − 0, 042градуса. При этом средние размеры по широте и по долготе различаются не более чем в 3 раза, значит ограничение по слабой вытянутостиполигонов также справедливо.В исследовании первоначальный (наибольший) размер ячейки выбран равным одному градусу географических координат, и на каждой следующей итерации уменьшался вдвое, пока время работы не достигало локального минимума(т.е.
точки, когда время в следующей итерации оказывалось уже больше), илидо тех пор, когда создание индексной структуры становилось невозможным изза ограничений памяти.На рис. 2.7, 2.8 приведены графики зависимости времени работы алгоритмаи используемой оперативной памятиот размера ячейки на векторномфайле, содержащем обнаруженные по космическим изображениям природныепожары за различные периоды 2010 г. , всего18486 полигонов.
Шкала по обеимосям логарифмическая. Видно, что при уменьшении размера ячейки от большого (1 градус, т.е. порядка0, 150линейных размеров полигона) до размеров менееградуса время падает, но затем при уменьшении размеров до значений,меньших характерного размера полигона, растет.Одновременно с этим при уменьшении размера ячейки монотонно растетобъем занимаемой памяти. Учитывая, что характерный диаметр полигонаданных файлах составляетв0, 01−0, 02 градуса, оптимальное время достигается56Рисунок 2.7 – Зависимость времени работы алгоритма от размера ячейкипри размере ячейки порядка = 3и близко к оптимальному при < < 10.Рисунок 2.8 – Зависимость объёма памяти, занимаемой индексной структурой, от размераячейкиАлгоритмы реализованы на языке C++ в 32-разрядном варианте и испытывались на ПК с процессором Intel Core i7 2700 MHz.
Результаты работыалгоритма на шести различных векторных файлах в сравнении с алгоритмом,использующим дерево квадрантов [93], приведены в таблице. Из неё видно, чтопредложенный метод работает значительно быстрее (приблизительно на одинпорядок величины), особенно при больших размерах файлов, однако при этом57для работы метода требуется больше оперативной памяти.Таблица 2.2 – Сравнительный результат работы методов индексации.Вектор- КоличествоДеревоквадДеревоквадныйполигоноврантов,времярантов,объём795118486344273589805работы, сфайлtest1.shptest2.shptest3.shptest4.shptest5.shptest6.shp1,9433,2440,9722,0693,1772,025памяти, МБ0,2930,6630,0140,0110,020,03РазработанныйРазработанныйметод,метод,времяработы, с0,1280,1670,110,1110,1010,103объёмпамяти, МБ6,8536,5313,1612,7232,5311,817Таким образом, разработан метод, позволяющий ускорить совместную обработку растровых и векторных данных ДЗЗ путем индексации векторного файла.
Ключевым условием эффективности индексации является верный выборразмера ячейки. Оптимальное значение – порядка среднего размера полигона– было обосновано теоретически и подтверждено практическими испытаниями.Предложенный метод имеет набор ограничений, за пределами которых он заведомо не является эффективным, однако на реальных данных, отвечающихэтим ограничениям, при условии подбора правильного размера ячейки, он дает хорошие результаты, обеспечивая ускорение по сравнению с методом дереваквадрантов.2.5. Эффективные алгоритмы для полученияпересечения, объединения, разности объектоввекторной модели данных в виде многоугольниковпри работе с большими объёмами данныхВ различных приложениях, связанных с обработкой данных ДЗЗ, появляется задача вычисления объединения, пересечения, разности множеств, представляющих собой площади земной поверхности, заданные в векторной модели, а именно как набор замкнутых многоугольников, описанных последовательностями вершин [11].
Типичными задачами являются: объединение площадей,58полученных при обработке данных последовательных пролётов спутников надзаданным участком; получение пересечения такой объединённой площади (имеющей обычно весьма сложную форму) с границами административных образований или областями определённого типа растительности; вычисление разностидвух множеств с целью выявления изменений объектов. Требуется построитьалгоритмы, вычисляющие объединение, пересечение, разность таких множеств.2.5.1. Постановка задачиКаждое множество, называемое также операндом, представляет собой набор контуров — многоугольников, которые могут пересекаться между собой (ноне самопересекаться).Особенностью практических задач такого типа, возникающих при обработке данных ДЗЗ, является большой объём информации, поступающей на обработку: количество контуров в каждом операнде может достигать десятковтысяч, количество вершин в каждом контуре, как правило, порядка десяти,однако в отдельных случаях может достигать тысячи.2.5.2.
Существующие алгоритмыПодобные задачи решались многими исследователями при помощи различных методов. В [70] проводится обзор алгоритмов, предложенных Sutherland,O’Rourke, Weiler, Леонов, Schutte, Holwerda, Margalit и сравнение их по ряду таких параметров, как вычислительная устойчивость, ресурсоёмкость, скоростьработы, простота программной реализации. Кроме этого, рассматривались также алгоритмы Liang-Barsky, Maillot, Vatti, Greiner-Horman, рекомендованные в[78]. Однако, несмотря на кажущееся обилие методов, большая часть из нихоказалась непригодной из-за большой размерности задачи.
Многие из перечисленных методов рассчитаны на работу с очень сложными, но малочисленнымиконтурами, в то время как в исследуемой задаче — большое число относительно59простых контуров.Алгоритмы Сазерленда, О’Рурка, Шутте, Лианга-Барского и Maillot признаны непригодными, так как требуют связности, односвязности и/или выпуклости хотя бы одного из операндов. Алгоритм Вейлера-Азертона пригоден дляоперации лишь с двумя (пусть и очень сложными) контурами, а алгоритм Маргалита-Кнотта пригоден лишь в случае когда один из операндов представленединственным многоугольником. Поскольку число многоугольников может составлять десятки тысяч (хоть и очень простых), для операций в нашем случаепотребуются десятки тысяч вызовов этих алгоритмов с последующим объединением результатов; причём оптимальное объединение результатов само по себеявляется сложной задачей.
Алгоритм Холверда является предшественником более быстрого и стабильного алгоритма Ватти, а алгоритм Леонова - модификацией алгоритма Грейнера-Хормана. Таким образом, более подробному разбору,в том числе экспериментальной проверке, подверглись три алгоритма: триангуляции [58], Леонова [41] и Ватти [154].2.5.3. Анализ выбранных алгоритмовТриангуляцией многоугольника называется его представление в виде полного набора взаимно не пересекающихся треугольников.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
