Алгоритм Балабана — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
(add some algo)
Строка 68: Строка 68:
 
  <tex>Split_{a,b}(L, Q, L')</tex>
 
  <tex>Split_{a,b}(L, Q, L')</tex>
 
  <tex>\{</tex>
 
  <tex>\{</tex>
     <tex>L' \leftarrow 0; Q \leftarrow 0</tex>
+
     <tex>L' \leftarrow \varnothing; Q \leftarrow \varnothing</tex>
 
     '''For''' <tex>j = 1,...,k</tex> '''do'''
 
     '''For''' <tex>j = 1,...,k</tex> '''do'''
 
         '''if''' отрезок <tex>S_j</tex> не пересекает
 
         '''if''' отрезок <tex>S_j</tex> не пересекает
Строка 77: Строка 77:
 
             добавить <tex>s_j</tex> в конец <tex>L’;</tex>
 
             добавить <tex>s_j</tex> в конец <tex>L’;</tex>
 
  <tex>\}</tex>
 
  <tex>\}</tex>
 +
 +
Эта функция работает за <tex>O(|L|)</tex> времени.
  
 
===Search In Strip===
 
===Search In Strip===
 +
 +
Зная <tex>L</tex> мы можем найти <tex>Int_{a, b}(L)</tex> и <tex>R</tex> используя следующую рекурсивную функцию:
 +
 +
<tex>SearchInStrip_{a, b}(L, R)</tex>
 +
<tex>\{</tex>
 +
    <tex>Split(L, Q, L');</tex>
 +
    '''if''' <tex>L' = \varnothing</tex> '''then'''
 +
        <tex>R \leftarrow Q;</tex>
 +
        '''return'''<tex>;</tex>
 +
    Найдем <tex>Int_{a, b}(Q, L');</tex>
 +
    <tex>SearchInStrip_{a, b} (L', R');</tex>
 +
    <tex>R \leftarrow Merge_b(Q, R’);</tex>
 +
<tex>\}</tex>
  
 
==Примечания==
 
==Примечания==

Версия 15:45, 4 октября 2013

Эта статья находится в разработке!

Алгоритм Балабана — детерминированный алгоритм, позволяющий по множеству отрезков на плоскости получить множество точек, в которых эти отрезки пересекаются.

Введение

Решение задачи по поиску множества пересечений отрезков является одной из главных задач вычислительной геометрии. Тривиальный детерминированный алгоритм имеет временную сложность [math]O(n^2)[/math], и его суть заключается в проверке попарного пересечения отрезков. Сложнее, но эффективнее алгоритм Бентли-Оттмана [1] с оценкой сложности [math]O((n + k)\ log(n)+k)[/math], в основе которого лежит метод заметающей прямой. Алгоритм, предложенный Чазелле и Едельсбруннером [2], имеет лучшую оценку [math]O(n\ log(n) + k)[/math], но в отличие от предыдущих методов требует квадратичной памяти. Оптимальный детерминированный алгоритм был предложен Балабаном [3] с временной оценкой сложности [math]O(n\ log(n) + k)[/math] и [math]O(n)[/math] памяти, где К - число пересекающихся отрезков. При количестве отрезков равным 2000 и большому количеству пересечений целесообразно использовать алгоритм Балабана. Однако в результате громоздкости и высокой сложности реализации алгоритма в большинстве практических задач используется алгоритм заметающей прямой Бентли-Оттмана.

Основные понятия

Введем некоторые обозначения. Пусть [math]Int(S)[/math] - множество всех точек пересечения отрезков из множества [math]S[/math], а [math]K = |Int(S)|[/math] - количество таких пересечений ;
Через [math]\langle a, b \rangle[/math] обозначим вертикальную полосу, которая ограничена прямыми [math]x = a[/math] и [math]x = b[/math], а через [math]s[/math] отрезок с концами абсцисс [math]l[/math] и [math]r[/math].
Рассмотрим взаимное расположение вертикальной полосы [math]\langle a, b \rangle[/math] и отрезка [math]s[/math].


Определение:
Будем говорить, что отрезок [math]s[/math], с концами абсцисс [math]l[/math] и [math]r[/math] :

- содержит(span) полосу [math]\langle a, b \rangle[/math], если [math]l \le a \le b \le r[/math];
- внутренний(inner) для полосы [math]\langle a, b \rangle[/math], если [math]a \lt l \lt r \lt b[/math];

- пересекает(cross) полосу [math]\langle a, b \rangle[/math] в других случаях.


Определение:
Два отрезка [math]s_1[/math] и [math]s_2[/math] называются пересекающимися внутри полосы [math]\langle a, b \rangle[/math], если их точка пересечения лежит в пределах этой полосы.
Для двух множеств отрезков [math]S[/math] и [math]S'[/math] определим множество [math]Int(S, S')[/math] как [math]\{ {s, s'} | (s \in S, s' \in S') \& (s \ intersect \ s') \}[/math].
[math]D = ((s_1, s_2, s_3), \langle a, b \rangle)[/math], [math]Loc(D, s_4) = 0[/math], [math]Loc(D, s_5) = 2[/math] или [math]3[/math], [math]Int(D, \{s_4,\ s_5\}) = \{\{s_3,\ s_5\}\}[/math]

Обозначения [math]Int_{a, b}(S)[/math] и [math]Int_{a, b}(S, S')[/math] будут использоваться для описания подмножеств [math]Int(S)[/math] и [math]Int(S, S')[/math], состоящих из пересекающихся пар отрезков в пределах полосы [math]\langle a, b \rangle[/math]. Далее скобки [math]\{\}[/math] используются для определения неупорядоченных наборов, а скобки [math]()[/math] используются для определения упорядоченных множеств.

Введем отношение порядка на множестве отрезков [math]s_1 \lt _b s_2[/math] если оба отрезка пересекают вертикальную линию [math]x = a[/math] и точка пересечения этой прямой с отрезком [math]s_1[/math] лежит ниже точки пересечения с [math]s_2[/math].


Определение:
Лестница [math]D[/math] — это пара [math](Q, \langle a, b \rangle)[/math], в которой отрезки из множества [math]Q[/math] удовлетворяют следующим условиям :

− любой отрезок из [math]Q[/math] содержит полосу [math]\langle a, b \rangle[/math];
− нет пересечений отрезков внутри лестницы;
[math]Q[/math] упорядочена по отношению [math]\lt _a[/math].

Часть отрезков лестницы внутри полосы будем называть ступеньками.


Определение:
Если точка [math]p[/math] отрезка [math]s[/math] лежит между ступеньками [math]i[/math] и [math]i + 1[/math], тогда число [math]i[/math] называется местоположением [math]s[/math] на лестнице [math]D[/math] и обозначается как [math]Loc(D, s)[/math]


Утверждение:
Имея лестницу [math]D = (Q, \langle a, b \rangle)[/math] и множество отрезков [math]S[/math], множество [math]Int(D, S)[/math] можно найти за время [math]O(|S| log|Q| + |Int(D, S)|)[/math].
Однако, если [math]S’[/math] упорядочено отношением [math]\lt _x[/math], где [math]x \in [a, b][/math], тогда можно найти [math]Int(D, S)[/math] за время [math]O(|S| + |Q| + |Int(D, S)|)[/math].

Алгоритм

Введем несколько дополнительных функций, чтобы упростить основной алгоритм:

Split

Пусть [math]L = (s_1 ,..., s_k)[/math], где [math]s_i \lt _b s_{i+1}[/math]
[math]Split_{a,b}(L, Q, L')[/math]
[math]\{[/math]
    [math]L' \leftarrow \varnothing; Q \leftarrow \varnothing[/math]
    For [math]j = 1,...,k[/math] do
        if отрезок [math]S_j[/math] не пересекает
        последний отрезок из [math]Q[/math] внутри полосы [math]\langle a, b \rangle[/math]
        и при этом содержит её then
            добавить [math]s_j[/math] в конец [math]Q;[/math]
        else
            добавить [math]s_j[/math] в конец [math]L’;[/math]
[math]\}[/math]

Эта функция работает за [math]O(|L|)[/math] времени.

Search In Strip

Зная [math]L[/math] мы можем найти [math]Int_{a, b}(L)[/math] и [math]R[/math] используя следующую рекурсивную функцию:

[math]SearchInStrip_{a, b}(L, R)[/math]
[math]\{[/math]
    [math]Split(L, Q, L');[/math] 
    if [math]L' = \varnothing[/math] then
        [math]R \leftarrow Q;[/math] 
        return[math];[/math]
    Найдем [math]Int_{a, b}(Q, L');[/math]
    [math]SearchInStrip_{a, b} (L', R');[/math]
    [math]R \leftarrow Merge_b(Q, R’);[/math]
[math]\}[/math]

Примечания

Литература

Т.Вознюк, В.Терещенко — К построению эффективного решения задачи пересечения отрезков
Ф.Препарата, М.Шеймос — Вычислительная геометрия