Геометричний пошук, Детальна інформація

if ( ребро( i ) перетинає l нижнім кінцем зліва від z)

then L \xF0AC\xF020L + 1;

if (L непарне) then z всередині else z ззовні;

end.

Теорема. Належність точки z внутрішній області простого N - кутника можна встановити за час O(N) без передобробки.

Задача. Належність точки опуклому многокутнику. Дано опуклий многокутник (N - кутник) P та точка z. Чи знаходиться точка z в середині P?

Алгоритм. Вершини опуклого многокутника впорядкуємо за полярними кутами відносно довільної внутрішньої точки q, в якості якої можна взяти, наприклад, центр ваги довільних трьох вершин P. Проведемо N променів з точки q через вершини многокутника. Ці промені розіб’ють площину на N клинів, кожен з яких розбивається стороною многокутника на дві частини. За допомогою двійкового пошуку можна знайти клин, в якому лежить точка z (промені розташовані в порядку зростання їх полярних кутів проти годинникової стрілки). Точка z лежить між променіми pi та pi+1 тоді і тільки тоді, коли кут (zqpi+1) додатний, а кут (zqpi) від’ємний. Коли точки pi та pi+1 знайдено, то точка z буде внутрішньою тоді і тільки тоді, коли кут (pipi+1z) від’ємний.

Теорема. Час відповіді на запит про належність точки опуклому N - кутнику дорівнює O(log N) при затраті O(N) пам’яті та O(N) часу на попередню обробку.

Попередня обробка полягає в розташуванні вершин многокутника в структурі даних, придатної для двійкового пошуку.

Зірчасті многокутники є більш обширним класом простих многокутників, що включають в себе опуклі многокутники. Зірчастий многокутник містить хоча б одну таку точку q, що відрізок qpi повністю лежить всередині многокутника P для довільної вершини pi. Множина всіх можливих таких точок q називається ядром P. Після знаходження такої точки q можна використовувати попередній алгоритм.

Теорема. Час відповіді на запит про належність точки зірчастому N - кутнику дорівнює O(log N) при затраті O(N) пам’яті та O(N) часу на попередню обробку.

Локалізація точки на планарному розбитті

Метод смуг. Нехай задано планарний граф G. Проведемо горизонтальні прямі через кожну його вершину. Ці прямі розіб’ють площину не більш ніж на N + 1 горизонтальних смуг. Відсортуємо ці смуги за координатою y, після чого можна знайти ту смугу, в якій знаходиться задана точка z за час O(log N).

Знайдена смуга перетинає відрізки ребер графа G. Оскільки G є плоске укладання планарного графа, то його ребра перетинаються між собою лише у вершинах, а оскільки кожна вершина лежить на границі смуги, то відрізки ребер всередині смуг не перетинаються. Тому ці відрізки можна впорядкувати зліва направо та використати двійковий пошук для визначення тієї трапеції (які можуть вироджуватися у трикутники), в яку попала точка z, витративши на це час O(log N). Оскільки смуга може містити O(N) відрізків, то час, необхідний на їх впорядкування, дорівнює O(N * log N).

Нехай k – кількість смуг планарного графа G. Позначимо через L список смуг, кожний елемент L[i] (1 \xF0A3\xF020i \xF0A3 k) якого містить вказівник li на список відсортованих (зліва направо) відрізків у смузі.

Оскільки граф може мати O(N) смуг, а на впорядкування відрізків у кожній смузі витрачається час O(N * log N), то для побудови структур даних L та li (1 \xF0A3\xF020i \xF0A3 k) необхідно витратити час O(N2 * log N).

Локалізація точки методом смуг

1. Використовуючи y - координату точки z, методом бінарного пошуку у списку смуг L знайти смугу j, в якій лежить точка z.

2. Використовуючи x - координату точки z, методом бінарного пошуку у списку відрізків li знайти відрізки e1 та e2, між якими лежить точка z.

Витрати по пам’яті дорівнюють O(N2), оскільки існують такі планарні графи, сумарна кількість відрізків в полосах яких може досягати O(N2). Справа на малюнку біля кожної смуги вказано кількість відрізків, яка знаходиться в ній.

Якщо ребро графа проходить через декілька смуг, то ці смуги йдуть послідовно одна за іншою. Час передобробки можна скоротити якщо використати метод замітання площини.

Алгоритм плоского замітання характеризується двома основними структурами даних:

1. Список точок подій – послідовність позицій, що назначаються для замітаючої прямої.

2. Статус замітаючої прямої – опис перетину замітаючої прямої із замітаємим геометричним об’єктом.

Якщо замітання проводити знизу вгору, то моментальним статусом замітаючої прямої буде впорядкована зліва направо послідовність ребер графа, що перетинають ту смугу, де знаходиться замітаюча пряма. Ця послідовність (порядок ребер) не змінюється всередині смуги, але змінюється на границі з наступною смугою, коли досягається наступна вершина графа. Статус замітаючої прямої можна зберігати у формі дерева, збалансованого за висотою (2-3 дерева). Списком точок подій є перелічені знизу вгору вершини графа.

Передобробка. Побудова структур даних.

1. Відсортувати вершини графа G по зростанню y координати. Нехай відсортованим списком буде {v1, v2, ..., vn}. Побудуємо список L[i], з кожним елементом якого пов’яжемо дві точки vi та vi+1 графа G, одна з яких знаходиться на нижній границі смуги, а друга – на верхній. При цьому нехай вершина v0 має мінімальну y - координату, а vn+1 – максимальну y - координату. Умовоно орієнтуємо ребра графу G, які направлені від вершини з меншою y - координатою до вершини з більшою y - координатою.

2. Для смуги L[1] побудуємо порожнє 2 - 3 дерево T1. Список l1 покладемо порожнім.

3. k \xF0AC 2.

4. Розглянемо вершину vk-1 та видалимо всі вебра, які входять у vk-1 з дерева Tk-1 та вставимо у Tk-1 всі ребра, що виходять з vk-1. Отримали дерево Tk для L[k].