Содержание
- 2. Пространственные базы данных Основные характеристики: Представление пространственных объектов в геометрическом пространстве (обычно двух- или трехмерном) Форма
- 3. Моделирование пространства 1) Объектные (object-based) модели пространства Компоненты пространственных объектов: Идентификационная информация Описание Пространственная протяженность Классификация
- 4. Моделирование пространства б) Одномерные объекты = линейные объекты Например, дороги на картах Основной геометрический объект –
- 5. Моделирование пространства 2) Полевые (field-based) модели пространства Пространственная информация задается непрерывным1 полем значений, т.е. с помощью
- 6. Моделирование пространства Пример:
- 7. Способы представления пространственных объектов 1) Мозаичное (tessellation) представление Разбиение на ячейки(соты) (возможны разные формы ячеек) Фиксированные
- 8. Способы представления пространственных объектов 2) Векторное представление Естественно для объектных моделей пространства Базисные элементы (примитивы): точки
- 9. Способы представления пространственных объектов 3) Полуплоскостное (half-plane) представление Единственный используемый примитив: полуплоскость (см.математическое определение) Солидный математический
- 10. Вычислительная геометрия Алгоритмическая техника для выполнения операций в пространственных базах данных 1) Инкрементные алгоритмы Решить задачу
- 11. Вычислительная геометрия Иллюстрация к инкрементному нахождению выпуклой оболочки: (1) (2) (3) (4) (5)
- 12. Вычислительная геометрия 2) Стратегия «разделяй и властвуй» «Разделяй»: задача рекурсивно разбивается на несколько легко решаемых подзадач
- 13. Вычислительная геометрия Пересечение полуплоскостей с помощью метода «разделяй и властвуй»:
- 14. Вычислительная геометрия 3) Метод заметающей прямой (sweep-line) Разложение пространства на вертикальные полосы, таким образом, чтобы линии,
- 15. Вычислительная геометрия Алгоритм нахождения пересекающихся прямоугольников: begin Отсортировать 2n нижние и верхние x-координаты прямоугольников и поместить
- 16. Вычислительная геометрия Метод заметающей прямой для нахождения пересекающихся прямоугольников:
- 17. Вычислительная геометрия Типичные задачи вычислительной геометрии: Расположение точки относительно полигона (внутри или вне) Пересечение отрезков прямых
- 18. Хранение и извлечение пространственных объектов Общие замечания: Работа с произвольными фигурами затруднительна ⇒ Рассматривают минимальные ограничивающие
- 19. Хранение и извлечение пространственных объектов Минимальные ограничивающие прямоугольники :
- 20. Хранение и извлечение пространственных объектов Виды запросов к пространственным объектам: Запросы по точному совпадению: не типичны
- 21. Хранение и извлечение пространственных объектов Представление пространственных объектов на основе трансформации координат k-мерный прямоугольник можно представить
- 22. Хранение и извлечение пространственных объектов Пример представления (для одномерного пр-ва): Замечания: В случае применения методов доступа
- 23. Хранение и извлечение пространственных объектов Ответы на запросы: Простые геометрические вычисления укажут на области, соответствующие тому
- 24. Хранение и извлечение пространственных объектов Представление пространственных объектов на основе отсечения Пространство разбивается на непересекающиеся прямоугольные
- 25. Хранение и извлечение пространственных объектов Достоинства: Отсечение может осуществляться практически напрямую с помощью любого метода доступа
- 26. Хранение и извлечение пространственных объектов Представление пространственных объектов на основе перекрывающихся областей Каждый прямоугольник представлен в
- 27. Хранение и извлечение пространственных объектов Потенциальные недостатки: Высокая степень перекрытия ухудшает производительность Степень перекрытия MBR’ов может
- 28. R-деревья Индекс на основе перекрывающихся областей - R-дерево [4] (rectangle tree): Сбалансированная динамическая внешняя древовидная структура,
- 29. R-деревья Пример R-дерева: R10 R1 R2 R3 R4 R5 R6 R7 R8 R9 R11 R12 R13
- 30. R-деревья Обработка запросов: Запрос по точке: найти объекты, содержащие заданную точку Начиная с корня, рекурсивно просматриваем
- 31. R-деревья Вставка в R-дерево: Используя процедуру ChooseLeaf (см.след.слайд), найти лист L для вставляемого прямоугольника R Если
- 32. R-деревья Процедура ChooseLeaf: Начать с корневого узла (= N) Если N является листом, вернуть N Просмотреть
- 33. R-деревья Расщепление: Наиболее сложная задача (экспоненциальное число альтернатив) Происходит в листе, но может распространиться наверх Задача:
- 34. R-деревья Этапы, требующие нелинейного времени, в процедуре выше: Выбор «ядер» (первых элементов в группах) Выбор следующего
- 35. R-деревья Корректировка дерева: Параметры: лист L и возможно LL, если L был расщеплен Расширение границ прямоугольников,
- 36. R-деревья Удаление (прямоугольника R) из R-дерева: Найти лист L, содержащий R, путем просмотра всех поддеревьев, MBR’ы
- 37. R-деревья R*-дерево [5]: улучшенная версия R-дерева Откладывает расщепление путем принудительной вставки: Сортировка всех прямоугольников на основе
- 38. R-деревья X-дерево [6]: Может хранить точечные и пространственные данные Превосходит R*-деревья, TV-деревья, и ряд других структур,
- 39. Пространственные соединения Типичная операция при обработке пространственных запросов Задача: для двух множеств пространственных объектов найти пары,
- 40. Пространственные соединения Примерный сценарий: Оба множества объектов описываются индексом на основе R-дерева Условие соединения – пересечение
- 41. Применение: географические базы данных Основные понятия Географический объект: Две компоненты: Описательная часть с численно-текстовыми атрибутами, например,
- 42. Применение: географические базы данных Геоинформатические операции Проекция темы на подмножество описательных атрибутов: Соответствует реляционной проекции Визуальный
- 43. Применение: географические базы данных Объединение тем: Соответствует реляционному объединению Объединяет две темы, имеющие одинаковые схемы Наложение
- 44. Применение: географические базы данных Геопространственные СУБД 1) Специализированные геоинформационные СУБД ArcInfo: Задумана как набор инструментальных средств
- 45. Применение: географические базы данных PostgreSQL: Объектно-реляционная СУБД Свободно распространяемая, открытый код Расширенные возможности: Геометрические типы: точка,
- 46. Упражнения Рассмотрим простой (см.слайды «Вычислительная геометрия» для определения простого полигона) полигон в двухмерном пр-ве, задаваемый списком
- 48. Скачать презентацию