Геометричний пошук

Якщо пряма проходить через вершини многокутника, то при обчисленні значення L необхідно користуватися наступними правилами: якщо обидві вершини ребра належать l, то це ребро треба відкинути; якщо тільки одна вершина ребра лежить на l, то перетин враховується, якщо це вершина з більшою ординатою та ігнорується інакше.

Належність простому многокутнику

begin

L 0;

for i 1 to N do

if ( ребро ( i ) не горизонтальне) then

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

then L L + 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).