Интернет магазин китайских планшетных компьютеров

Компьютеры - Алгоритм Бентли Оттмана - Алгоритм

В приведенном ниже псевдокоде используются:

• Q — динамические структура данных без повторений с логарифмическим временем поиска, вставки, удаления точек событий и поиска минимального элемента.
• T — динамические структура данных без повторений с логарифмическим временем поиска, вставки, удаления отрезков. В ней хранятся все отрезки, пересекающие выметающую прямую.
• q — точка события.
• newq — только что найденная точка пересечения отрезков, точка события.
• L — множество отрезков, левый конец которых — q.
• R — множество отрезков, правым концом которых является q.
• I — множество отрезков, пересекающихся в q.

segmentsIntersections
    1) Инициализируются Q и T. В Q заносятся все концы отрезков, упорядоченные по координате x, при этом, если две точки совпали,
       то левая конечная точка отрезка помещается перед правой. Если совпали только x, то точка с меньшим y является меньшей.
       T ← ∅
    2) while Q != ∅
           q ← min;
           processPoint;

processPoint
    1) Найти в Q все отрезки, содержащие q; // они в Q будут соседними, так как точки события, которые содержатся в этих
       отрезках, имеют одинаковые координаты;
    2) if| + |R| + |I| > 1) ИЛИ| > 0)
           then Выдать в ответ точку q;
    3) if| = 0) И|+|R| > 0) // в рассматриваемой точке все отрезки только начинаются или заканчиваются;
           then I ← I ∪ L ∪ R; // добавить в I L и R
    4) Удалить из T R и I;
    5) Вставить в T I и L;
    // из T были удалены все отрезки из множества I, теперь же вставляются обратно в измененном порядке после точки пересечения;
    6) if∪I = ∅) ИЛИ| = |R| - 1)
           then Найти в T верхнего и нижнего соседей q su и sl;
                newq = findIntersect;
                if newq != NULL
                    then add;
    7) else
           Пусть s′ — самый верхний отрезок из L∪I;
           Пусть su — верхний сосед s′ в T;
           Пусть s′′ — самый нижний отрезок из L∪ I;
           Пусть sl — нижний сосед s′′ в T;
           newq = findIntersect;
           if newq != NULL
               then add;
           newq = findIntersect;
           if newq != NULL
               then add;
           // далее убираем квадрат памяти;
           newq = findIntersect;
           if newq != NULL
               then delete;
           newq = findIntersect;
           if newq != NULL
               then delete;
           newq = findIntersect;
           if newq != NULL
               then delete;

findIntersect
    if sl и su пересекаются правее заметающей прямой
        then return newq;
    else return NULL;