Геом Поиск Локализация

Методы локализации точки
Метод полос
Метод цепей
Метод детализации триангуляции

– «файл»;
некоторый новый элемент данных – «образец».
Поиск – установление связи

между образцом и файлом.
Геометрический поиск
Файлы – сложные геометрические структуры: множества точек, многоугольники, графы и т.п.
Образцы: точки, регионы и т.п.

Запрос на поиск (на обработку – просмотр файла)
Пример: поиск в массиве чисел.
Уникальный запрос. Массовый запрос.
Предобработка – структуризация данных (сортировка)

анализе геометрических алгоритмов поиска:
Время предобработки. Сколько времени необходимо для организации

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

запроса
Корректировка
СД

n элементов
Время предобработки: сортировка – O (n log n)
Время

запроса: ⎡log2 (n + 1)⎤ или O (log n)
Память: O (n)
Время корректировки: O (n)

n точек на плоскости.
Сколько из них лежит внутри заданного

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

В форме отчет – перечислить внутренние точки. Уникальный региональный запрос – O(n) (оптимально). Метод локусов. Локус – геометрическое место точек, в пределах которого ответ не меняется.

вершины.
Можно заменить запрос с прямоугольником четырьмя подзадачами, по одной на

каждую из его вершин.
Подзадача, связанная с вершиной p: определить число точек Q(p) исходного множества, которые удовлетворяют неравенствам x ≤ x(p) и y ≤ y(p), т.е. числа точек в левом нижнем квадранте, определяемом вершиной p.

векторное доминирование
Говорят, что точка (вектор) v доминирует над w, тогда и только тогда, когда для всех индексов (координат) i верно условие vi ≥ wi. На плоскости точка v доминирует над w тогда и только тогда, когда w лежит в левом нижнем квадранте, определяемом v.

Сколько точек “юго-западнее” p?

Число точек N(p1p2p3p4) в прямоугольнике p1p2p3p4 определяется следующим образом:
N(p1p2p3p4) =

Q(p1) - Q(p2) - Q(p4) + Q(p3)

Региональный поиск. Метод локусов

На плоскости существуют области удобной формы, внутри которых число доминирования Q является константой. Локусы.
См. папку «1Метод локусов»

оси x и y, а полученные линии продолжены в бесконечность.

Они создают решетку из (n+1)2 прямоугольников.

Региональный поиск. Метод локусов

0

0

0

0

0

0

0

0

0

0

0

0

0

0

0

0

1

1

1

1

1

0

0

2

1

1

2

2

2

2

4

3

3

3

4

5

решетка O(n3) O(n2)
Запрос: 2 бинарных поиска O(log2n)
Региональный поиск. Метод локусов

пространства на области,
Образец для запроса = точка.
Локализация состоит

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

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

в простом многоугольнике

L

z*

z

to n do {цикл по ребрам}
if not горизонтальное (ребро[i]) then
if

ребро[i] пересекает L нижним концом справа от z
then k := k + 1;
if Odd(k) then z – внутри else z – снаружи;

Локализации точки в простом многоугольнике

O(log n)
Память: O(n)
Предобработка: O(n)

– множество не внешних для P точек, из которых «видны»

все точки многоугольника (O(n)).
Ядро не пусто ↔ многоугольник звездный.

O(log n)
Память: O(n)
Предобработка: O(n)

файл «Локализация точки.doc» и папку «Локализация точки»
Задача локализации точки