Диссертация (1137226), страница 8
Текст из файла (страница 8)
Координаты объектов векторного файла соответствуют географическим координатам(широта и долгота). Растровый файл является геопривязанным, т.е. для каждого пикселя известны его географические координаты, иными словами заданоотображение : (, ) → (, )Эту задачу можно решать двумя путями:прямым и обратным. Обратный путь состоит в том, чтобы для каждого полигона определить пиксели растрового изображения, лежащие внутри него. Дляэтого требуется построить отображение = −1 : (, ) → (, ).В этомслучае было бы возможно применение алгоритмов, ориентированных на выборпростой процедуры, описывающей окрестности векторного объекта на растровом изображении, и перебор ограниченного числа пикселов для проверки ихпересечения с векторным объектом.
Однако отношение G является немонотонным и разрывным в областях проекционных искажений (так называемый bowtie effect [159]), что приводит к невозможности построения отображения H инеприемлемому возрастанию перебора при поиске. Поэтому для решения проблемы был выбран прямой путь: для каждого обрабатываемого пикселя растра48(, )взятьгоны ,географические координаты и найти в векторном файле все поливключающие точку с этими координатами : (, ) = (, ) ∈ Проверка нахождения точки в границах одного полигона может осуществляться, например, методом трассировки луча с подсчетом количества пересечений[100].
Для проверки всех полигонов требовалось бы провести трассировку лучапо всему их набору, что неприемлемо для реальных задач, включающих десятки тысяч полигонов. Таким образом, необходимо ввести некоторую структуру,упорядочивающую полигоны и уменьшающую перебор. В этом случае работаалгоритма сопоставления состоит из двух шагов: построение индекса (индексация) и собственно сопоставление с использованием индекса. Для подобныхзадач разработано множество методов индексации, таких как различные варианты R-деревьев (R*, R+, Priority R, X- деревья). Эти достаточно сложныеструктуры позволяют быстро решать разнообразные трудоемкие задачи взаимного расположения пространственных объектов. Основой для всех этих методовявляется заключение объектов пространства в ограничивающий прямоугольник и построение сбалансированного, сильно разветвленного дерева, в которомкаждая вершина представляет прямоугольник, содержащий в себе все объекты,размещенные в ее потомках, а листовая вершина представляет собой ограничивающий прямоугольник одного объекта.
Первый из этих методов, R-дерево,способен ускорять решение множества задач на взаимное расположение многомерных протяженных объектов [99]. Близок к исследуемой задаче метод дереваквадрантов [93]. В нем заранее выбирается допустимая емкость листовой вершины – наибольшее количество объектов в ней, а внутренняя вершина деревавсегда имеет четыре потомка, представляющих квадранты (четверти) областиродительской вершины. С учетом этого при добавлении в дерево новой записиона либо добавляется в листовую вершину, соответствующую ее координатам,если в этой вершине есть еще неиспользованная емкость, либо, если вершиназаполнена, она становится внутренней, а все объекты, отнесенные к ней, распределяются между четырьмя ее потомками.
Однако при решении простейшей49задачи – взаимного расположения точки и набора непересекающихся полигонов – возможно применение существенно более простого метода индексации,который в этом случае дает лучший результат, чем универсальные алгоритмы2.4.2. Описание методаПусть задан векторный файл, содержащий полигоныследовательности вершин в координатах широта–долгота ,заданные как по = {( , )},причем большинство полигонов имеют размер одного порядка и не являются сильновытянутыми, т.е. отношение длин любых двух сечений полигона порядка единицы. Характерный размер (средний диаметр) полигона обозначимОбщий размер области, содержащей полигоны, обозначим = ( ).( , ).Построение индексной структуры производится следующим образом.
Для всех записейвекторного файла ищется общий ограничивающий прямоугольник( , ) : = ( ) − ( ); = ( ) − ( ),,,,,,размеракоторый делитсяна некоторое количество равных, не пересекающихся прямоугольников-ячеек,таким образом, чтобы каждая ячейка имела наиболее близкую к квадратуформу. Размеры ячеек (соответственно, их количество) выбираются из соображений минимизации общего времени вычислений, более подробно описанныхниже. Затем для каждой ячейки создается список полигонов, пересекающихячейку (иными словами полностью или частично содержащихся в ней):, = { | ∩ , ̸= ∅}.(2.21)Координаты ячеек и списки номеров полигонов записываются, на этом построение индексной структуры заканчивается.
На рисунке 2.5 показан пример разбиения на ячейки и порождаемые списки контуров для ячеек. Полигонкается с ячейками1,1 , 1,2 , 2,1 ; полигон полностью лежит в ячейке1,1 .– с ячейкамипересе1,1 и 2,1 ; полигон Соответственно, списки полигонов для ячеек:501,1 = {, , }, 1,2 = {}, 2,1 = {, }, 2,2 = ∅.(2.22)Рисунок 2.5 – Пример векторного файла, разбитого на ячейки.На этапе сопоставления, когда нужно выяснить, лежит ли точка с определенными координатами в каком-либо из полигонов векторного файла, по этимкоординатам явным образом вычисляется номер ячейки, в которой лежит точка, и затем происходит перебор всех полигонов, находящихся в списке для данной ячейки, с проверкой, лежит ли точка в каком-либо из них. Следует отметить важное упрощение, сделанное на шаге индексации. Задача определениятого, пересекается ли полигон с прямоугольником, решается захудшем случае, где()шагов в –– число вершин полигона, так как для каждой вершинытребуется сравнение координат с координатами границ прямоугольника.
В случае большого количества вершин полигона и большого его размера это можетпривести к квадратичному(2 )возрастанию сложности вычислений за счетвозрастания числа ячеек, которые могут пересекаться с полигоном. На практикетакие большие полигоны появляются достаточно часто. Однако для решаемойзадачи не является критичным добавление в список ячейки полигона, даже ес51ли он не пересекается с ней. В этом случае на этапе сопоставления производятсядополнительные излишние вычисления при обработке точек ячейки, не пересекающейся с данным полигоном, но ошибочно содержащей его в своем списке.Порядок сложности избыточных вычислений равен(), , где ,точек в ячейке, что может оказаться существенно меньше затрат–– число(2 ) на этапеиндексации.Поэтому для установления факта пересечения полигона с ячейкой используется не обсчет самого полигонапрямоугольником этого полигона:( )−, а сравнение ячейки с ограничивающим( , ) : = ( ) − ( ), =( ). Таким образом, вместо сложного алгоритма определенияпересечения прямоугольника с произвольным полигоном используется простейшее определение пересечения двух прямоугольников со сторонами, параллельными осям координат.
На рис. 2.6 приведен пример ошибочного включенияполигона,показанного на рис. 2.5, в список2,2 .Рисунок 2.6 – Пример ошибочного включения полигона в ячейку.Оценим вычислительную сложность метода. Все описанные размеры выражаются в координатах векторного файла, то есть географических, где коорди52натасоответствует широте, аобрабатываемых данных по осидолготе. Пусть— горизонтальный размер , т.е., фактически, разброс по долготе; вертикальный размер обрабатываемых данных по осиброс по широте;– число полигонов;(географические координаты);–– , т.е., фактически, раз— средний линейный размер полигона– размер ячейки;— число обрабатываемыхточек. При этом считаем, что количество вершин в полигоне ограничено, а значит, можно считать сложность проверки, лежит ли данная точка в заданномполигоне, равной(1).При расчете без индексации алгоритмическая сложность равна произведению числа обрабатываемых точек растра на число полигонов и на среднеечисло вершин в полигоне: = (),(2.23)При индексации необходимо оценить сложность самой индексации и сложность обработки точки в зависимости от размера ячейки.Шаг индексации.Оценим количество ячеек, в списки которых внесенполигон.
Оно равно количеству ячеек, пересекаемых ограничивающим прямоугольником полигона и пропорционально отношению их площадейоднако не меньше1.В случае маленького размера ячейки≪(︁(︀ )︀ )︁ 2,можно пользоваться этим приближением, если же это условие не выполняется, можно задать более точно количество пересекаемых ячеек, однако в любом случае при≃или<это количество ограничено небольшим числом, то есть оценкавыполняется. Учитывая, что сложность добавления в односвязный список —константа, получаем алгоритмическую сложность всего шага индексации:1 =⎧⎪⎪⎨(︂ )︂2()при⎪⎪⎩()при>.(2.24)≤Таким образом, сложность алгоритма линейно зависит от количества по53лигонов, однако при уменьшении ячейки менее характерного размера полигонасложность возрастает квадратично от размера ячейки.Шаг сопоставления по индексу.Определение, лежит ли точка в одном из полигонов, теперь состоит из расчета номера ячейки, в которую попадает точка, который имеет сложность(1)и сопоставление точки с каждымиз полигонов, пересекающих эту ячейку.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
