Презентация на тему "Пространственные базы данных"

Содержание

• 
  Слайд 1
  
• 
  Слайд 2

  Пространственные базы данных

  220 Основные характеристики: Представление пространственных объектов в геометрическом пространстве (обычно двух- или трехмерном) Форма (фигура) и расположение – неотъемлемые компоненты Чаще всего у координат численные значения (с определенной дискретностью и нижней и верхней границами) Области применения: геоинформационные системы (ГИСы), системы автоматизированного проектирования (САПРы), графический интерфейс пользователя (GUI), виртуальная реальность, компьютерные игры, анимация и т.д.

• 
  Слайд 3

  Моделирование пространства

  221 1) Объектные (object-based) модели пространства Компоненты пространственных объектов: Идентификационная информация Описание Пространственная протяженность Классификация объектов на основе размерности: Примечание: зависит от приложения, работающего с объектом а) Объекты нулевой размерности = точки Формы нет или знание формы объекта не требуется Площадь объекта очень мала в сравнении со всем рассматриваемым пространством (например, города на картах, здания на картах, пересечения дорог, и т.д.) Могут появляться в зависимости от масштаба карта (город – точка на мелкомасштабной карте и двухмерный объект на крупномасштабной карте)

• 
  Слайд 4
  

  222 б) Одномерные объекты = линейные объекты Например, дороги на картах Основной геометрический объект – ломаная линия. Состоит из конечного множества отрезков (или сегментов или ребер), таких что любая (за исключением двух точек – начала и конца ломаной линии) из конечных точех этих отрезков принадлежит двум отрезкам Простая ломаная линия – нет пересечений Замкнутая ломаная линия – точки начала и конца ломаной линии совпадают Любая кривая может быть представлена с заданной точностью ломаной линией в) Двухмерные объекты = объекты на плоскости Сущности-объекты имеют не нулевую площадь Основной геометрический объект – полигон (многоугольник). Полигон – область, задаваемая замкнутой ломаной линией Выпуклый полигон P:для любых A,B P, отрезок AB целиком в P г) Трехмерные объекты = объемные объекты (полиэдры=многогранники)

• 
  Слайд 5
  

  223 2) Полевые (field-based) модели пространства Пространственная информация задается непрерывным1 полем значений, т.е. с помощью некой функции (например, по координатам x и y) Для каждой точки пространства может использоваться несколько атрибутов Примеры: Температурное поле (температура в разных точках) Атмосферное давление в разных точках Высота над уровнем моря (на физических картах) Значения уровня серого цвета на полутоновых цифровых изображениях Значения красного, синего, зеленого компонентов на цветных (24-битных) изображениях --------- 1 – не в математическом смысле

• 
  Слайд 6
  

  224 Пример: сосна ель дуб сосна ель дуб сосна ель дуб 0 ID Древесная порода Область Объектная модель Полевая модель

• 
  Слайд 7

  Способы представления пространственных объектов

  225 1) Мозаичное (tessellation) представление Разбиение на ячейки(соты) (возможны разные формы ячеек) Фиксированные ячейки: одинаковые ячейки (сетка прямоугольных координат) Произвольные ячейки: размеры и формы ячеек различаются между собой Мозаика с регулярной/нерегулярной структурой По умолчанию: N x M прямоугольных (обычно квадратных) ячеек, которые называются пикселами Естественное (дискретное) представление полевых данных В случае объектных данных: один пиксел для точки, набор (множество) пикселов для ломаной линии или полигона Более точное представление (с более мелкими ячейками) потребует больше места для хранения; обработка займет больше времени

• 
  Слайд 8
  

  226 2) Векторное представление Естественно для объектных моделей пространства Базисные элементы (примитивы): точки и ребра Полигон задается множеством точек, аналогично ломаная линия 2*nвозможных описания полигона с nвершинами (выбор стартовой вершины, обход по/против часовой стрелки) Область – множество полигонов Представление может дополняться ограничениями (например, только простые1 полигоны) Векторное представление полевых данных; цифровые модели местности (digital elevation models): Значения задаются только для подмножества точек Значения в остальных точках интерполируются Пример: триангулированные неравномерные сети (triangulated irregular networks) ------------------ 1 – граница которого не пересекается сама с собой

• 
  Слайд 9
  

  227 3) Полуплоскостное (half-plane) представление Единственный используемый примитив: полуплоскость (см.математическое определение) Солидный математический базис Полуплоскость в d-мерном пространстве задается неравенством: a1x1 + a2x2 + ... + adxd + ad+1 0 Выпуклый полигон – пересечение конечного числа полуплоскостей Полигон – объединение конечного числа выпуклых полигонов Отрезок (ребро) линии – одномерный выпуклый полигон (пересечение двух лучей или полупрямых) Ломаная линия – объединение нескольких отрезков

• 
  Слайд 10

  Вычислительная геометрия

  228 Алгоритмическая техника для выполнения операций в пространственных базах данных 1) Инкрементные алгоритмы Решить задачу для небольшого подмножества входных данных (точек), затем решить задачу для начального множества плюс одна точка из остающихся и т.д. пока все точки не будут рассмотрены Пример: нахождение выпуклой оболочки для множества точек Простейший метод с временной сложностью O(n2): Построить выпуклую оболочку H3 – для первых трех точек Для каждой из остальныхточек { pi }, i>3: Если piвнутри Hi-1, то Hi = Hi-1(проверка «внутри»: при обходе Hi-1по часовой стрелке, piостается справа) Иначе, добавить piкHi-1, возможно удалив старые точки (для pi найти соседние такие точки pa, pb, чтобы угол между отрезками (pa ,pi) и (pb , pi) был наибольшим) Оптимальный алгоритм: O(n log n), используется предварительная сортировка точек

• 
  Слайд 11
  

  229 Иллюстрация к инкрементному нахождению выпуклой оболочки: (1) (2) (3) (4) (5)

• 
  Слайд 12
  

  230 2) Стратегия «разделяй и властвуй» «Разделяй»: задача рекурсивно разбивается на несколько легко решаемых подзадач «Властвуй»: объединение снизу-вверх всех решений в одно общее решение Аналогия: бинарное дерево (см.следующий слайд) Пример: пересечение полуплоскостей Для простоты считаем, что конечный результат – выпуклый полигон внутри прямоугольника R Исходное множество из n полуплоскостей рекурсивно разбивается пополам до тех пор пока мы не получим n отдельных полуплоскостей (это дает нам бинарное дерево) Для каждой из полуплоскостей определяем ее пересечение с R (каждое такое пересечение - выпуклый полигон) Объединение результатов: рекурсивно снизу-вверх определяем попарные пересечения полигонов Сложность: O(n log n), т.к. сложность нахождения пересечения выпуклых полигонов - O(n)

• 
  Слайд 13
  

  231 Пересечение полуплоскостей с помощью метода «разделяй и властвуй»:

• 
  Слайд 14
  

  232 3) Метод заметающей прямой (sweep-line) Разложение пространства на вертикальные полосы, таким образом, чтобы линии, разделяющие полосы, давали нужную информацию для решения проблемы Процесс «заметания» заключается в перемещении вертикальной прямой слева направо, с остановками на границах вертикальных полос и сохранения/обновления информации необходимой для решения Используются две структуры данных: Статус заметающей прямой: содержит объекты, связанные с текущей позицией прямой Перечень событий: содержит границы полос, известные заранее или определяемые динамически Пример: найти все попарные пересечения множества прямоугольников, стороны которых параллельны координатным осям Время работы в наихудшем случае O(n2) Метод на основе заметающей прямой со сложностью прямо пропорциональной количеству находимых объектов (методы с такой сложностью называются output-sensitivemethods)

• 
  Слайд 15
  

  233 Алгоритм нахождения пересекающихся прямоугольников: begin Отсортировать 2n нижние и верхние x-координаты прямоугольников и поместить результат в E Пусть L= while(E  ) do begin p = Min(E) Извлечь (удалить) pиз E ifp- нижняя граница прямоугольникаrthenbeginНайти (и выдать как результат) все прямоугольники из L, которые пересекаются с r ВставитьrвL endif if p- верхняя граница прямоугольникаrthen Удалить r из L endwhile end

• 
  Слайд 16
  

  234 Метод заметающей прямой для нахождения пересекающихся прямоугольников:

• 
  Слайд 17
  

  235 Типичные задачи вычислительной геометрии: Расположение точки относительно полигона (внутри или вне) Пересечение отрезков прямых Пересечение ломаных линий Пересечение полигонов Отсечение с помощью прямоугольника (отсечение объекта(-ов) вне границ прямоугольного окна) Разбиение полигона на треугольники (триангуляция) Разбиение полигона на трапеции Представление полигона в виде нескольких выпуклых полигонов Ограничение, накладываемые на объекты, упрощают алгоритмы; например, в случае полигонов: Простой полигон: граница не пересекается сама с собой Монотонный полигон: граница составлена из двух монотонных цепочек вершин: верхней и нижней цепочек вершин полигона (цепочка вершин монотонна, если любая вертикальная линия пересекает образуемую ломаную линию не более одного раза) Выпуклый полигон (было дано ранее)

• 
  Слайд 18

  Хранение и извлечение пространственных объектов

  236 Общие замечания: Работа с произвольными фигурами затруднительна  Рассматривают минимальные ограничивающие прямоугольники (далее MBR1): наименьший прямоугольник, охватывающий геометрический объект на плоскости, со сторонами, параллельными координатным осям Значения координат отображаются на интервал [0, 1); пространство – гиперкуб, обозначаемый Ek Факторы, влияющие на производительность: Выбранная структура данных Размерность пространства Распределение объектов в пространстве: Плотность в точке P = число прямоугольников, содержащихP Глобальная плотность = максимум по локальным плотностям ---------- 1 - Minimum bounding rectangle или сокращенно MBR; другое название – ограничивающие блоки (bounding box)

• 
  Слайд 19
  

  237 Минимальные ограничивающие прямоугольники :

• 
  Слайд 20
  

  238 Виды запросов к пространственным объектам: Запросы по точному совпадению:не типичны для пространственных объектов, за исключением операций вставки Запрос по точке: для заданной точкиP  Ek найти все прямоугольникиRтакие, что P  R Пересечение прямоугольников: для заданного прямоугольника S  Ekнайти все прямоугольникиR такие, что S  R   Поиск «включающих» прямоугольников: для заданного прямоугольника S  Ek найти все прямоугольники Rтакие, что S  R(R включает в себя S) Поиск прямоугольников «внутри»: для заданного прямоугольника S  Ekнайти все прямоугольники R такие, что R  S(R внутри S) Запрос по объему: по заданнымv1, v2  (0,1), v1  v2 найти все прямоугольники с объемом (площадью)в интервале[v1, v2] Пространственное соединение: для двух множествk-мерных прямоугольников найти все пары, удовлетворяющие заданному условию соединения (пересечение, включение, нахождение внутри)

• 
  Слайд 21
  

  239 Представление пространственных объектов на основе трансформации координат k-мерный прямоугольник можно представить 2k-мерной точкой Возможные варианты (на примере двухмерного пр-ва): (cx, cy, ex, ey), где (cx, cy) – центральная точка, а exи ey– расстояния от центральной точки до сторон прямоугольника (lx, ly, ux, uy), где (lx, ly) и (ux, uy) – нижняя вершина слева и верхняя вершина справа соответственно Достоинство варианта a): координаты расположения cxи cy отличны откоординат протяженностиex иey Частный случай: Одномерное пространство [0, 1) Прямоугольник = отрезок  [0, 1) Варианты представления: (c, e) = (центр, половина длины) (l, u) = (начальная точка, конечная точка)

• 
  Слайд 22
  

  240 Пример представления (для одномерного пр-ва): Замечания: В случае применения методов доступа к точечным данным возникает проблема «пустых треугольников» (или «мертвых регионов»), см.рисунок выше Вариант представления с координатами центра и протяженности может быть улучшен, если нам известен верхний предел размера стороны прямоугольника (тогда, например, в одномерном случае можно рассматривать только область [0, limit/2]); в этом случае «живое» пространство будет трапецией, а «мертвые» треугольники сравнительно небольшими c l 0 1 L1 L2 L3 L4 0.5 0 1 e     P1 P2 P3 P4 0 1 u  S1  S2  S3  S4 1

• 
  Слайд 23
  

  241 Ответы на запросы: Простые геометрические вычисления укажут на области, соответствующие тому или иному типу запросов Пример: одномерные прямоугольники (=отрезки) могут быть представлены точками в двухмерном пространстве (с помощью координат центра и протяженности); для прямоугольника в запросе S = (c, e) имеем: Недостаток: близко расположенные, но различного объема, прямоугольники могут располагаться довольно далеко друг от друга в двухмерном пространстве c e 0.5 1 R  S R  S   R  S R  S   R  S =  R  S = 

• 
  Слайд 24
  

  242 Представление пространственных объектов на основе отсечения Пространство разбивается на непересекающиеся прямоугольные области (также как и в большинстве методах доступа к точечным данным, см.тему 8) Расположение прямоугольника Rможет быть следующим: Rвнутри одной из областей: простая обработка (как и в методах доступа к точечным данным) Rпересекается как минимум с двумя областями В случае «отсечения»: каждая область пересечения (R с областями на которые разбито пр-во) рассматривается (в том числе хранится) как самостоятельный прямоугольник, но при этом все отсеченные части указывают на один и тот же изначальный объект R1 R2 R31 R32 R33 R34 R41 R42 R51 R52 R6

• 
  Слайд 25
  

  243 Достоинства: Отсечение может осуществляться практически напрямую с помощью любого метода доступа к точечным данным Точки и прямоугольники могут храниться в одном и том же месте Недостатки: Повышенные требования к пространству (многочисленные указатели на один и тот же объект) Дополнительные издержки при операциях вставки и удаления В случае высокой глобальной плотности необходимы избыточные страницы Производительность: Запросы по точному совпадению, по точке и поиск включающих прямоугольников потребуют доступа только к одной странице (при условии, что нет переполнения) Пересечение прямоугольников и поиск прямоугольников «внутри» может потребовать просмотра всех отсеченных частей прямоугольника запроса; количество false drops может быть большим Пример реализации: R+-дерево [3]:сбалансированное внешнее(т.е. данные об объектах хранятся только в листьях) дерево; похоже на R-дерево (см.далее)

• 
  Слайд 26
  

  244 Представление пространственных объектов на основе перекрывающихся областей Каждый прямоугольник представлен в базе данных только один раз (в отличие от R+-дерева) Прямоугольники сгруппированы по дисковым страницам Каждая область (образующая группу прямоугольников) задается минимальным ограничивающим прямоугольником Области могут перекрываться Пример: R1 R2 R3 R4 R5 R6 R7 R8 R9 R10

• 
  Слайд 27
  

  245 Потенциальные недостатки: Высокая степень перекрытия ухудшает производительность Степень перекрытия MBR’ов может быть много выше степени перекрытия рассматриваемого множества прямоугольников Запрос по точному совпадению, вставка и удаление могут потребовать доступа к более чем одной странице Пересечение прямоугольников и поиск прямоугольников внутри могут требовать доступа к одним и тем же страницам, при этом поиск прямоугольников внутри дает как правило много меньшее количество результатов (т.к. каждый прямоугольник внутри также является пересекающимся) Обобщение: Области (минимальные ограничивающие прямоугольники) могут быть сами сгруппированы, образуя прямоугольники более высокого уровня Это позволяет построить древовидную структуру

• 
  Слайд 28

  R-деревья

  246 Индекс на основе перекрывающихся областей - R-дерево [4](rectangle tree): Сбалансированная динамическая внешняя древовидная структура, где узлы – страницы Хранит как точки так и прямоугольники Широко используется; например, в пространственном модуле Oracle Виды узлов: Лист содержит пары (R,TID), где R – MBR пространственного объекта, а TID – указывает на точное описание объекта Внутренний узел содержит пары (R, ptr),где R – MBR прямоугольников в узле-потомке, а ptr – указатель на узел-потомок Свойства: Прямоугольники на пути от вершины дерева к листьям вложены друг в друга (т.е. прямоугольник узла-потомка внутри прямоугольника узла-родителя) Какие-либо ограничения на перекрытие прямоугольников (за исключением только что упомянутого) отсутствуют, но (!) количество перекрытий должно минимизироваться При емкости страницы в M записей, для количества записей на одной странице определяется нижняя граница - mM/2 Для Nзаписей, высота (дерева) logmN1 и количество узлов N/(m 1)

• 
  Слайд 29
  

  247 Пример R-дерева: R10 R1 R2 R3 R4 R5 R6 R7 R8 R9 R11 R12 R13 R14 R15 R16 R1 R2 R3 R15 R16 R4 R5 R6 R7 R8 R9 R10 R11 R12 R13 R14

• 
  Слайд 30
  

  248 Обработка запросов: Запрос по точке: найти объекты, содержащие заданную точку Начиная с корня, рекурсивно просматриваем все поддеревья, MBR’ы которых содержат данную точку. Дойдя до уровня листьев, получим описания объектов, каждый из которых необходимо проверить на предмет содержания точки Запрос на пересечение: найти объекты, пересекающиеся с заданным прямоугольником Обработка такая же как и в a), но проверяется не содержание точки, а пересечение объектов Выполнение других типов запросов происходит похожим образом Производительность: Гарантия отсутствует, т.к. может требоваться просмотр значительного количества узлов дерева Степень перекрытия MBR’ов, описываемых во внутренних узлах, определяет производительность Самая важная роль при минимизации степени перекрытия у операции вставки

• 
  Слайд 31
  

  249 Вставка в R-дерево: Используя процедуру ChooseLeaf(см.след.слайд),найти лист L для вставляемого прямоугольника R Если в L есть место для R, осуществить вставку; иначе, вызвать процедуру SplitNode, возвращающую листья L и LL, которые совместно содержат R и старые объекты из L Вызвать процедуру AdjustTree с входными параметрами L и возможно LL. Корректировка (дерева) ведет к увеличению ограничивающих прямоугольников в узлах-родителях, и возможно вызовет расщепление узлов Если корневой узел был расщеплен на два, то создать новый корневой узел, узлами-потомками которого будут эти два образовавшихся узла

• 
  Слайд 32
  

  250 Процедура ChooseLeaf: Начать с корневого узла (= N) Если N является листом, вернуть N Просмотреть пары (указывающие на поддеревья) в узле N. Выбрать ту пару, чей MBR при включении прямоугольника R увеличится наименьшим образом (в идеале, вообще не изменится). Пусть F указатель определенной таким образом пары. В спорных случаях (когда приращение MBR’ов одинаково) – выбирать прямоугольник с наименьшей площадью. Переопределить N как узел на который указывает F и продолжить с шага 2

• 
  Слайд 33
  

  251 Расщепление: Наиболее сложная задача (экспоненциальное число альтернатив) Происходит в листе, но может распространиться наверх Задача: минимизировать степень перекрытия MBR’ов Эвристическая процедура: попытаться минимизировать общую площадь двух прямоугольников, образующихся в результате расщепления Два способа (второй на след.слайде) SplitNode (квадратичное время): Найти два прямоугольника R1, R2, которые в случае помещения в один и тот же узел, приведут к наибольшой потере пространства, т.е. для которых Area(MBR(R1, R2){R1, R2}) максимальна. R1и R2 будут «ядрами» двух формируемых групп прямоугольников Остановить процедуру, если все прямоугольники распределены по своим группам. Если все остающиеся прямоугольники должны быть отнесены к одной из групп (для того чтобы было выполнено условие минимально допустимого количество записей в данной группе, см.слайд 246), то поместить прямоугольники в эту группу и остановиться Для каждого из остающихся прямоугольников вычислить d1 = увеличение площади MBR, если прямоугольник отнесен к группе 1, и d2(если к группе 2).Выбрать прямоугольникс наибольшим значением d1-d2, и вставить его в группу для которой d-значение минимально. Перейти к шагу 2.

• 
  Слайд 34
  

  252 Этапы, требующие нелинейного времени, в процедуре выше: Выбор «ядер» (первых элементов в группах) Выбор следующего прямоугольника (шаг 3) SplitNode (линейное время): Выбор первых элементов для групп: для каждого измерения найти два прямоугольника, которые имеют наибольшую нижнюю границу (по этому измерению) и наименьшую верхнюю границу соответственно; определить максимум (по всем измерениям d)следующего выражения: |Max(нижн.граница R1 по измерению d)  Min(верх.граница R2 по измерению d)| длина всего рассматриваемого множества прямоугольников по измерению d; другими словами, будет выбрана пара прямоугольников с наибольшим нормализованным расстоянием между нижней и верхней гранями Выбор следующего прямоугольника: выбирать любой из остающихся Квадратичная процедура работает до определенной степени лучше линейной, в некоторых случаях много лучше линейной

• 
  Слайд 35
  

  253 Корректировка дерева: Параметры: лист L и возможно LL, если L был расщеплен Расширение границ прямоугольников, включающих прямоугольники листа L Расщепление внутренних узлов при необходимости AdjustTree: Зададим N = L и, если существует, NN = LL Если N – корневой узел, то остановиться Пусть узел P – родитель N и PN – запись в P об узле-потомке N. Скорректировать MBR в PN(MBR прямоугольников из узла N) Если NN существует, то создать новую запись PNN, указывающую на NN и хранящую MBR прямоугольников из узла NN Если P вмещает в себя PNN, то вставить PNNв P, иначе: Вызвать SplitNode, производящую P и PP, совместно содержащие PNNи старые записи узла P Переопределить N = P и NN = PP, и перейти к шагу 2

• 
  Слайд 36
  

  254 Удаление (прямоугольника R) из R-дерева: Найти лист L, содержащий R, путем просмотра всех поддеревьев, MBR’ы которых пересекаются с R Удалить R из L [подготовка к сжатию дерева] Задать N= L и Q = empty (= множество удаляемых узлов) Если N – корневой узел, то перейти к шагу 7, иначе: пусть узел P – родитель узла N и PN– запись в P об узле N [проверка условия минимальной заполнености узла] Еслив узле N менее чем m (см.слайд 246) записей, то удалить PNиз P and добавить узел N в множество Q, иначескорректировать MBR в PN Переопределить N = P и перейти к шагу 4 [передислокация записей из удаленных узлов] Заново вставить в R-дерево все записи из множества Q. Записи из удаленных листов вставляются в листы (с помощью операции стандартной вставки). В тоже время, записи из удаленных внутренних узлов вставляются во внутренние узлы так, чтобы листья, образуемых ими поддеревьях, были на том же уровне, что и листья основного дерева Если у корневого узла только один узел-потомок, то сделать потомка новым корневым узлом

• 
  Слайд 37
  

  255 R*-дерево [5]: улучшенная версия R-дерева Откладывает расщепление путем принудительной вставки: Сортировка всех прямоугольников на основе расстояний между их центрами и центром соответствующих MBR’ов Определенная часть наиболее удаленных прямоугольников удаляется и затем повторно вставляется Более сложная эвристическая процедура для расщепления: См.[5] Временная сложность O(M*logM) для M прямоугольников Превосходит R-дерево Хорошо работает в качестве метода доступа к точечным данным «Эталонная» структура данных для других структур пространственных данных (пожалуй, наиболее известный метод доступа к пространственным данным)

• 
  Слайд 38
  

  256 X-дерево [6]: Может хранить точечные и пространственные данные Превосходит R*-деревья, TV-деревья, и ряд других структур, особенно в пространствах большой размерности Основное предположение: с ростом размерности пространства последовательный индекс становится все более эффективен, т.к. перекрытия становятся все больше и больше Решение: внутренние узлы могут быть произвольного размера; суперузел содержит более одной страницы Многостраничный суперузел с (физически) последовательно расположенными страницами обрабатывается быстрее, чем такое же число отдельных страниц Для пространств большой размерности большие суперузлы предпочтительны X-tree настраивается на число измерений X-tree – «эталонная» структура для других структур данных высокой размерности

• 
  Слайд 39

  Пространственные соединения

  257 Типичная операция при обработке пространственных запросов Задача: для двух множеств пространственных объектов найти пары, удовлетворяющие заданному пространственному предикату, например: Равенство Пересечение (перекрытие) Включение (асимметрично) Близость Другие топологические зависимости (слева от, справа от, на севере от, и т.д.) В силу использования MBR’ов требуются два шага: Фильтрация: найти пары MBR’ов, удовлетворяющих предикату Уточнение: для каждой из пар, найденных на шаге 1, осуществить окончательную проверку, учитывая реальную геометрию объектов

• 
  Слайд 40
  

  258 Примерный сценарий: Оба множества объектов описываются индексом на основе R-дерева Условие соединения – пересечение Стандартный алгоритм: Основан на обходе деревьев в глубину Начать с корневых узлов На каждом шаге рассматриваются два узла (N1, N2); вычисляются пары пересекающихся записей (e1, e2), где e1N1, e2  N2 Процедура вызывается рекурсивно для поддеревьев, задаваемых e1иe2 При достижении уровня листов происходит сравнение непосредственно самих объектов Совершенствование алгоритма: Проверять только пары (e1, e2),в которых и e1и e2пересекаются с (MBRN1 MBRN2) Метод заметающей прямой: рассматривать два множества прямоугольников (красные и синие), искать пересечения только красных с синими

• 
  Слайд 41

  Применение: географические базы данных

  259 Основные понятия Географический объект: Две компоненты: Описательная часть с численно-текстовыми атрибутами, например, город – название, население и т.д. Пространственная часть (то что мы называем пространственным объектом) описывает геометрию (расположение, форму), например, город: полигон в двухмерном пространстве Элементарные и сложные (сложно-составные) объекты: Сложные объекты состоят из других элементарных/сложных объектов Тема (theme): Класс (тип) географического объекта Соответствует отношению в реляционной бд; тема задается схемой и есть экземпляры темы (класса) Примеры тем: реки, города, страны, дороги и т.д.

• 
  Слайд 42
  

  260 Геоинформатические операции Проекция темы на подмножество описательных атрибутов: Соответствует реляционной проекции Визуальный результат: часть атрибутов на карте пропадает Выборка на основе описательных атрибутов: Соответствует реляционной выборке Остаются только те географические объекты, что удовлетворяют условиям выборки Визуальный результат: часть объектов пропадает Геометрическая выборка: Объекты в заданном окне: выбираются объекты (возвращаются целиком), пересекающиеся с заданным прямоугольником Запрос по точке: выбираются объекты, геометрия которых содержит данную точку Отсечение по заданному окну: выбираются объекты (возвращаются только(!) пересечения, а не целые объекты), пересекающиеся с заданным прямоугольником

• 
  Слайд 43
  

  261 Объединение тем: Соответствует реляционному объединению Объединяет две темы, имеющие одинаковые схемы Наложение тем: Рядовая операция в геоинформационных приложениях Пространственное соединение: вычислить пересечения На основе пересечений создаются новые географические объекты: Описательные атрибуты берутся от обоих пересекающихся объектов Пространственная компонента определяется геометрией пересечения Метрические операции: Например, расстояние между Москвой и Санкт-Петербургом Топологические операции: Например, список стран, имеющих общую границу с Россией (Украина, Белоруссия, Литва, Латвия и т.д.) Список городов до которых можно долететь (без дополнительной посадки) из Санкт-Петербурга

• 
  Слайд 44
  

  262 Геопространственные СУБД 1) Специализированные геоинформационные СУБД ArcInfo: Задумана как набор инструментальных средств разработки Большой выбор пространственных функций Подсистемы: Arc – пространственные данные, Info – описательные данные Представление пространственных данных: векторное, растровое (сеточное), триангуляционное 2) Расширения реляционных СУБД Oracle Spatial: Новый пространственный тип данных SQL расширен операторами для манипуляций с пространственным типом данных Пространственное индексирование на основе Z-порядка (см.предыдущую тему) Оптимизация запросов, например, для пространственных соединений

• 
  Слайд 45
  

  263 PostgreSQL: Объектно-реляционная СУБД Свободно распространяемая, открытый код Расширенные возможности: Геометрические типы: точка, линия, прямоугольник, полигон, окружность и т.д. Операции с геометрическими объектами: сдвиг, масштабирование и т.д. Индекс на основе обобщенного R-дерева Вставка геометрических объектов в виде строки координат в SQL, например, треугольник – ‘((1,2), (4,5), (3,1))’ В тоже время: Не поддерживаются топологические операции (например, близости) Не поддерживается наложение тем Не поддерживается пересечение полигонов

• 
  Слайд 46

  Упражнения

  264 Рассмотрим простой (см.слайды «Вычислительная геометрия» для определения простого полигона) полигон в двухмерном пр-ве, задаваемый списком точек по часовой стрелке – P = ((x1, y1), (x2, y2), ... (xn,yn)). Предложить правило (основные принципы), определяющее находится ли заданная точка (x, y) внутри P.Предложите варианты правила в случаях, если полигон: выпуклый, не выпуклый, точки на гранях полигонане внутри P. Предложить способ (основные принципы) для нахождения пересечения двух треугольников в двухмерном пространстве.

• 
  Слайд 47

  Ссылки на литературу

  265 [1] P. Rigaux, M. Scholl, A. Voisard. Spatial Databases, with Application to GIS, Morgan-Kaufmann, 2002 [2] Gaedeand Günther. Multidimensional Access Methods.ACM Computing Surveys, 30(2), 1998 [3]T. Sellis, N. Roussopoulos, and C. Faloutsos. The R+-Tree: A dynamic index for multi-dimensional objects. VLDB-1987,1987 [4] A. Guttman. R-Trees: A Dynamic Index Structure for Spatial Searching. SIGMOD-1984, 1984 [5] N. Beckmann, H. Kriegel, R. Schneider, B. Seeger. The R*-Tree: An Efficient and Robust Access Method for Points and Rectangles. SIGMOD-1990, 1990 [6] S. Berchtold, D. Keim, H. Kriegel. The X-tree: An Index Structure for High-Dimensional Data.VLDB-1996, 1996