Геом Поиск Локализация - презентация, доклад, проект скачать

Нажмите для полного просмотра!

Содержание ▲

Вы можете ознакомиться и скачать презентацию на тему Геом Поиск Локализация. Доклад-сообщение содержит 17 слайдов. Презентации для любого класса можно скачать бесплатно. Если материал и наш сайт презентаций Mypresentation Вам понравились – поделитесь им с друзьями с помощью социальных кнопок и добавьте в закладки в своем браузере.

Слайды и текст этой презентации

Слайд 1

Описание слайда:

Вычислительная геометрия Лекция 5 Геометрический поиск. Метод локусов Методы локализации точки Метод полос Метод цепей Метод детализации триангуляции

Слайд 2

Описание слайда:

Геометрический поиск Абстрактная модель поиска: некоторый набор данных – «файл»; некоторый новый элемент данных – «образец». Поиск – установление связи между образцом и файлом. Геометрический поиск Файлы – сложные геометрические структуры: множества точек, многоугольники, графы и т.п. Образцы: точки, регионы и т.п. Запрос на поиск (на обработку – просмотр файла) Пример: поиск в массиве чисел. Уникальный запрос. Массовый запрос. Предобработка – структуризация данных (сортировка)

Слайд 3

Описание слайда:

Геометрический поиск 4 меры оценки ресурсов при анализе геометрических алгоритмов поиска: Время предобработки. Сколько времени необходимо для организации данных перед поиском? Время запроса. Сколько времени необходимо для ответа на один запрос? Память. Сколько памяти необходимо для структуры данных (СД)? Время корректировки. Предъявлен элемент данных. Сколько времени потребуется на его включение в СД или исключение из неё?

Слайд 4

Описание слайда:

Фазы обработки при геометрическом поиске

Слайд 5

Описание слайда:

Пример: бинарный поиск в массиве из n элементов Время предобработки: сортировка – O (n log n) Время запроса: log2 (n + 1) или O (log n) Память: O (n) Время корректировки: O (n)

Слайд 6

Описание слайда:

Региональный поиск (подсчет). Региональный поиск: даны n точек на плоскости. Сколько из них лежит внутри заданного прямоугольника, стороны которого параллельны координатным осям? Т.е. сколько точек p = (x, y) удовлетворяют неравенствам a  x  b, c  y  d для заданных a, b, c и d ?

Слайд 7

Описание слайда:

Слайд 8

Описание слайда:

Связь между доминированием и региональным поиском Связь между доминированием и региональным поиском Число точек N(p1p2p3p4) в прямоугольнике p1p2p3p4 определяется следующим образом: N(p1p2p3p4) = Q(p1) - Q(p2) - Q(p4) + Q(p3)

Слайд 9

Описание слайда:

Из точек p опущены перпендикуляры на оси x и y, а полученные линии продолжены в бесконечность. Они создают решетку из (n+1)2 прямоугольников. Из точек p опущены перпендикуляры на оси x и y, а полученные линии продолжены в бесконечность. Они создают решетку из (n+1)2 прямоугольников.

Слайд 10

Описание слайда:

Предобработка: сортировка O(n log n) + решетка O(n3) O(n2) Предобработка: сортировка O(n log n) + решетка O(n3) O(n2) Запрос: 2 бинарных поиска O(log2n)

Слайд 11

Описание слайда:

Задача локализации точки Файл = разбиение геометрического пространства на области, Образец для запроса = точка. Локализация состоит в определении области, содержащей запрошенную точку. Планарное подразбиение плоскости прямолинейными отрезками Многоугольники

Слайд 12

Описание слайда:

n – число вершин простого многоугольника n – число вершин простого многоугольника Принадлежность точки z внутренности простого многоугольника – O(n) без предобработки

Слайд 13

Описание слайда:

k := o; k := o; for i := 1 to n do {цикл по ребрам} if not горизонтальное (ребро[i]) then if ребро[i] пересекает L нижним концом справа от z then k := k + 1; if Odd(k) then z – внутри else z – снаружи;