Алгоритм Бентлі — Оттманна

Перетин відрізків $O((n+k)\log n)$

Алгоритм Бентлі — Оттманна в обчислювальній геометрії використовує метод замітання прямою для пошуку всіх точок перетину прямолінійних відрізків на площині. Він узагальнює алгоритм Шеймоса-Нойї, який задану множину відрізків перевіряв на наявність будь-якого перетину. Для вхідних даних, які містять $n$ відрізків, що мають $k$ переринів, алгоритм Бентлі — Оттманна виконується за час $𝒪((n+k)\log n)$. У випадку, коли $k=ℴ\left(\frac{n^2}{\log n}\right)$, його можна розглядати як удосконалення алгоритму повного перебору, який виконується за час $\mathrm{\Theta }(n^2)$.

Алгоритм був розроблений Джоном Бентлі та Томасом Оттманном у 1979 році. Більш детально він описаний у книгах Шаблон:Harvtxt, Шаблон:Harvtxt, та Шаблон:Harvtxt. Хоча й відомі асимптотично більш швідкі алгоритми, алгоритм Бентлі — Оттманна залишається затребуваним завдяки простоті та використанню низького об'єму пам'ятіШаблон:Citation needed.

Загальний опис

В алгоритмі застосовується метод замітання прямою (замітальною прямою, що рухається прямо, скануючи лінії; Шаблон:Lang-en). У методі використовується вертикальна замітальна пряма, що рухається зліва направо, при цьому відрізки, які вона перетинає при даній координаті $x$, можна впорядкувати за координатою $y$, тим самим їх можна порівнювати між собою (котрий вище, котрий нижче). Це порівняння можна здійснити, наприклад, використовуючи рівняння прямої, що проходить через дві точки (відрізки задано двома своїми кінцевими точками): $(x-x_1)/(x_2-x_1)=(y-y_1)/(y_2-y_1)$, де $x_1$, $y_1$ і $x_2$, $y_2$ — координати, відповідно, першої та другої точок відрізка. Замітальна пряма переміщається по так званим точкам подіям (лівим і правим кінцям відрізків, а також точкам перетину відрізків). Після точки перетину відрізки варто міняти місцями, оскільки, наприклад, самий верхній із відрізків, які перетинаються після точки перетину стає самим нижнім. Наведений нижче алгоритм не розрахований на випадок, коли два відрізки перетинаються більше, ніж в одній точці.

NB Замітальну пряму можна також представити як горизонтальну, що рухається згори до низу за координатою $y$, і порівнювати відрізки, що її перетинають за координатою $x$.

Обробка вертикальних відрізків

Виникає проблема з вертикальним відрізком у тому розумінні як його порівнювати на вище/нижче з відрізками, що перетинають. Для цього можна, наприклад, вважати, що якщо точка перетину вертикального з не вертикальним відрізків знаходиться нижче поточної координати $y$ точки події, то вертикальний відрізок знаходиться вище, якщо точка перетину вище поточної координати $y$ точки події, то вертикальний відрізок вважається нижче відрізка, що перетинає його. Якщо поточна координата $y$ дорівнює координаті $y$ точки події, то при видаленні відрізка вважати, що вертикальний відрізок нижче, а при вставленні вважати, що він вище.

Квадрат пам'яті

У гіршому випадку, коли, наприклад, усі відрізки, перетинаючись між собою, утворюють прямокутну сітку, буде $O\left(n^2\right)$ точок перетину, які потрібно буде зберігати. Щоб уникнути використання квадрата пам'яті в алгоритмі, можна видаляти точку перетину відрізків, котрі тимчасово перестають бути сусідніми при даному положенні замітальною прямою. Ці точки все рівно будуть знову знайдені при подальших кроках алгоритму, коли дані відрізки знову стануть сусідніми (Печ, Шерір 1991).

Алгоритм

У наведеному нижче псевдокоді використовуються:

• Q — динамічні структура даних без повторень з логарифмічним часом пошуку, вставки, видалення точок подій і пошуку мінімального елемента (наприклад, червоно-чорне дерево, 2-3-дерево).
• T — динамічні структура даних без повторень з логарифмічним часом пошуку, вставки, видалення відрізків. У ній зберігаються всі відрізки, що перетинають замітальну пряму (наприклад, червоно-чорне дерево, 2-3-дерево).
• q — точка події.
• newq — щойно знайдена точка перетину відрізків, точка події.
• L(q) — безліч відрізків, лівий кінець яких — q (для вертикальних відрізків лівим вважається нижній кінець).
• R(q) — безліч відрізків, правим кінцем яких є q.
• I(q) — безліч відрізків, що перетинаються в q.

segmentsIntersections(points[])
    1) Ініціалізуються Q і T. До Q заносяться всі кінці відрізків, впорядковані за координатою x, при цьому, якщо дві точки збігаються,
       то ліва кінцева точка відрізка поміщається перед правою. Якщо збігаються лише x, то точка з меншим y є меншою.
       T ← ∅
    2) while Q != ∅
           q ← min(Q);
           processPoint(q);

processPoint(q)
    1) Знайти в Q всі відрізки, які містять q; // вони в Q будуть сусідніми, оскільки точки події, що містяться в цих відрізках, мають однакові координати;
    2) if (|L(q)| + |R(q)| + |I(q)| > 1) АБО (|I(q)| > 0)
           then Видати у відповідь точку q;
    3) if (|I(q)| = 0) І (|L(q)|+|R(q)| > 0) // у точці, яка розглядається, всі відрізки лише починаються або закінчуються;
           then I(q) ← I(q) ∪ L(q) ∪ R(q); // додати в I(q) L(q) і R(q)
    4) Видалити з T R(q) і I(q);
    5) Вставити в T I(q) і L(q);
    // із T були видалені всі відрізки з безліччю I(q), тепер же вставляються назад у зміненому порядку після точки перетину;
    6) if (L(q)∪I(q) = ∅) АБО (|I(q)| = |R(q)| - 1)
           then Знайти в T верхнього та нижнього сусідів q su і sl;
                newq = findIntersect(su, sl);
                if newq != NULL
                    then add(Q, newq);
    7) else
           Нехай s′ — самий верхній відрізок із L(q)∪I(q);
           Нехай su — верхній сусід s′ в T;
           Нехай s′′ — самий нижній відрізок із L(q)∪ I(q);
           Нехай sl — нижній сусід s′′ в T;
           newq = findIntersect(su, s′);
           if newq != NULL
               then add(Q, newq);
           newq = findIntersect(sl, s′′);
           if newq != NULL
               then add(Q, newq);
           // далі прибираємо квадрат пам'яті;
           newq = findIntersect(sl, su);
           if newq != NULL
               then delete(Q, newq);
           newq = findIntersect(s′′, su);
           if newq != NULL
               then delete(Q, newq);
           newq = findIntersect(sl, s′);
           if newq != NULL
               then delete(Q, newq);

findIntersect(sl, su)
    if sl і su перетинаються праворуч від замітальної прямої (або на замітальній прямій вище поточної точки подій)
        then return newq;
    else return NULL;

Аналіз

Нехай $n$ — число відрізків, $m\left(q\right)$ — число відрізків, що перетинають точку $q$. Тоді час на ініціалізацію Q дорівнює $O(n\log n)$, на ініціалізацію T — $O\left(1\right)$. На пошук усіх відрізків, що проходять через точку $q$ і оновлення Q, потрібно $O(m\left(q\right)\log n)$ часу. На оновлення T також $O(m\left(q\right)\log n)$ часу. Сумарно: $O(n\log n+\sum m\left(q\right)\log n)=O(n\log n+\log n\sum m\left(q\right))=O((n+k)\log n)$, де $k$ — число точок перетину $(\sum m\left(q\right)=O(n+k))$. $k=O\left(n^2\right)$.

Пам'ять $O\left(n\right)$, завдяки тому, що віддаляються точки перетину відрізків, котрі перестали бути сусідніми, інакше було б $O(n+k)$, де $k=O\left(n^2\right)$.

Література

• Шаблон:Книга
• Шаблон:Книга
• Шаблон:Книга
• Шаблон:Книга
• Шаблон:Книга

• Шаблон:Citation.
• Шаблон:Citation.
• Шаблон:Citation.
• Шаблон:Citation.
• Шаблон:Citation.
• Шаблон:Citation.
• Шаблон:Citation.
• Шаблон:Citation.
• Шаблон:Citation.
• Шаблон:Citation. Corrigendum, 2 (3): 341–343.
• Шаблон:Citation.
• Шаблон:Citation.
• Шаблон:Citation.
• Шаблон:Citation.
• Шаблон:Citation.
• Шаблон:Citation.

Посилання

• Візуалізатор — окремий випадок (алгоритм Шеймоса — Гоя, 1976 (Визначення наявності відрізків, що перетинаються)).
• Шаблон:Citation