Рубрики

По заданным n отрезкам линии найдите, пересекаются ли два отрезка.

Мы обсудили проблему, чтобы определить, пересекаются ли два заданных отрезка или нет . В этом посте мы расширим проблему. Здесь нам дано n отрезков, и нам нужно выяснить, пересекаются ли какие-либо два отрезка или нет.

Наивный алгоритм Наивное решение для решения этой проблемы — проверить каждую пару линий и проверить, пересекается ли пара или нет. Мы можем проверить два отрезка за O (1) раз . Следовательно, этот подход использует O (n 2 ).

Алгоритм Sweep Line: Мы можем решить эту проблему за O (nLogn) время, используя алгоритм Sweep Line. Алгоритм сначала сортирует конечные точки вдоль оси x слева направо, затем он проходит вертикальную линию через все точки слева направо и проверяет наличие пересечений. Ниже приведены подробные шаги.

1) Пусть будет n заданных строк. Должно быть 2n конечных точек для представления n линий. Сортировка всех точек по x координатам. При сортировке сохраняйте флаг, чтобы указать, является ли эта точка левой точкой своей линии или правой точкой.

2) Начните с крайней левой точки. Следуйте за каждым пунктом
… .. a) Если текущая точка является левой точкой своего линейного сегмента, проверьте пересечение ее линейного сегмента с сегментами чуть выше и ниже ее. И добавьте свою линию к активным отрезкам линии (отрезкам линии, для которых видна левая конечная точка, но правая конечная точка еще не видна). Обратите внимание, что мы рассматриваем только тех соседей, которые все еще активны.
…. б) Если текущая точка является правильной, удалите ее линейный сегмент из активного списка и проверьте, пересекаются ли ее два активных соседа (точки чуть выше и ниже).

Шаг 2 подобен прохождению вертикальной линии от всех точек, начиная с крайней левой точки до крайней правой точки. Вот почему этот алгоритм называется Sweep Line Algorithm. Техника Sweep Line полезна во многих других геометрических алгоритмах, таких как вычисление двумерной диаграммы Вороного.

Какие структуры данных следует использовать для эффективной реализации?
На шаге 2 нам нужно сохранить все активные отрезки. Нам нужно эффективно выполнять следующие операции:
а) Вставить новый отрезок
б) Удалить отрезок
c) Найти предшественника и преемника по значениям координат y
Очевидным выбором для вышеуказанных операций является самобалансирующееся дерево двоичного поиска, такое как дерево AVL, красное черное дерево. С помощью самобалансирующегося BST мы можем выполнить все вышеперечисленные операции за время O (Logn).
Кроме того, на шаге 1 вместо сортировки мы можем использовать структуру данных min heap. Построение минимальной кучи занимает время O (n), а каждая операция извлечения min занимает время O (Logn) (см. Это ).

псевдокод:
Следующий псевдокод не использует кучу. Это просто сортировка массива.

sweepLineIntersection(Points[0..2n-1]):
1. Sort Points[] from left to right (according to x coordinate)

2. Create an empty Self-Balancing BST T. It will contain all active line 
   Segments ordered by y coordinate.

// Process all 2n points 
3. for i = 0 to 2n-1

    // If this point is left end of its line  
    if (Points[i].isLeft) 
       T.insert(Points[i].line())  // Insert into the tree

       // Check if this points intersects with its predecessor and successor
       if ( doIntersect(Points[i].line(), T.pred(Points[i].line()) )
         return true
       if ( doIntersect(Points[i].line(), T.succ(Points[i].line()) )
         return true

    else  // If it's a right end of its line
       // Check if its predecessor and successor intersect with each other
       if ( doIntersect(T.pred(Points[i].line(), T.succ(Points[i].line()))
         return true
       T.delete(Points[i].line())  // Delete from tree

4. return False

Пример:
Давайте рассмотрим следующий пример, взятый отсюда . Есть 5 линейных сегментов 1 , 2 , 3 , 4 и 5 . Пунктирные зеленые линии показывают линии развертки.

Ниже приведены шаги, за которыми следует алгоритм. Все точки слева направо обрабатываются по одному. Мы поддерживаем самобалансирующееся бинарное дерево поиска.

Обрабатывается левая конечная точка отрезка 1 линии : 1 вставляется в дерево. Дерево содержит 1 . Нет пересечения.

Обрабатывается левая конечная точка отрезка 2 : проверяется пересечение 1 и 2 . 2 вставляется в дерево. Нет пересечения. Дерево содержит 1 , 2 .

Рекомендуемые посты:

По заданным n отрезкам линии найдите, пересекаются ли два отрезка.

0.00 (0%) 0 votes