Пересечения отрезков

OpenStreetMap хранит 800 миллионов узлов и 70 миллионов дорог. Каждый раз, когда приложение строит маршрут через город, ему нужно знать где дороги пересекаются с реками, зонами и границами. Наивный O(n^2) на 70 миллионах отрезков - 5*10^15 операций. Sweep line доводит это до секунд.

• **ГИС:** наложение слоёв карты - найти где дороги пересекают реки, границы зон, трубопроводы
• **Collision detection в играх:** broad phase - sweep and prune для AABB, определяет потенциальные столкновения среди тысяч объектов
• **САПР/PCB design:** проверка пересечений дорожек на печатной плате - критически важна для производства

Shamos, Hoey, Bentley, Ottmann - sweep революция

В 1976 году Шамос и Хой представили первый sweep line алгоритм для проверки наличия пересечений - O(n log n). Это был прорыв: до них задача казалась неизбежно O(n^2). В 1979 Бентли и Оттманн расширили идею до нахождения ВСЕХ k пересечений за O((n+k) log n). Статья 1979 года стала классикой: алгоритм появился в каждом учебнике по вычислительной геометрии и лёг в основу CGAL - промышленной библиотеки, которой пользуются Google Maps и AutoCAD.

Предварительные знания

• Convex Hull

Парадигма Sweep Line

Вертикальная линейка движется слева направо по плоскости. В каждый момент она «видит» только отрезки, которые её пересекают. По мере движения отрезки появляются и исчезают. Это **sweep line** - одна из мощнейших парадигм вычислительной геометрии. Задача 2D становится серией задач 1D.

**Sweep Line** - парадигма, где вертикальная линия движется по плоскости слева направо. Два ключевых компонента: **Event Queue** (очередь событий - точки, где что-то меняется) и **Status Structure** (упорядоченное множество отрезков, пересекающих sweep line в данный момент).

Три типа событий при sweep line для отрезков:

Ключевое наблюдение: **два отрезка могут пересечься только если они соседи в status structure**. Не нужно проверять все пары - достаточно проверять соседей при каждом изменении status. Это и даёт выигрыш в сложности.

Алгоритм Bentley-Ottmann

Bentley и Ottmann в 1979 году превратили идею sweep line в конкретный алгоритм для нахождения **всех** пересечений среди n отрезков. Наивный подход - O(n^2) пар. Bentley-Ottmann - O((n + k) log n), где k - число пересечений. Разница при n = 10 000 с k = 50: наивный 10^8, B-O около 10^5.

**Bentley-Ottmann** находит все k пересечений среди n отрезков за O((n + k) log n) времени и O(n + k) памяти. Event Queue - heap, Status Structure - сбалансированное BST. На каждое событие - O(log n) операций.

**Сложности реализации:** вырожденные случаи - три отрезка, пересекающиеся в одной точке; вертикальные отрезки; пересечение в концевой точке. Production-реализации (CGAL, Shapely) обрабатывают все эти случаи.

Red-Blue Intersections

Отрезки разделены на два набора - «красные» и «синие». Нас интересуют только пересечения **между** наборами, но не внутри каждого. Это задача **red-blue intersections** - возникает при наложении карт, collision detection между группами объектов, операциях с полигонами в GIS.

**Red-Blue Intersections:** даны два множества отрезков R (красные, n штук) и B (синие, m штук). Найти все пересечения r ∩ b, где r ∈ R, b ∈ B. Пересечения внутри R и внутри B - игнорируем.

Для задачи red-blue пересечений существуют и специализированные алгоритмы. Если один набор - горизонтальные отрезки, а другой - вертикальные, задача решается за O(n log n + k) с помощью **segment tree** или **interval tree**.

Output-Sensitive алгоритмы

В задачах вычислительной геометрии размер вывода **сильно варьируется**. У n отрезков может быть 0 пересечений или O(n^2). Алгоритм, чья сложность зависит от размера вывода - **output-sensitive**. Зачем тратить O(n^2), если пересечений всего 3?

**Output-sensitive алгоритм** - алгоритм, сложность которого зависит не только от размера входа n, но и от размера вывода k. Для задачи пересечения отрезков оптимум - O(n log n + k), достигнутый алгоритмом Балабана (1995).

Bentley-Ottmann в **худшем** случае (k = O(n^2)) медленнее наивного из-за log-фактора! Теоретически оптимальный алгоритм Балабана не имеет этой проблемы, но значительно сложнее в реализации.

Sweep line - выразительная парадигма, превращающая 2D-задачу в серию 1D-событий. Bentley-Ottmann - практичная реализация для пересечения отрезков. Output-sensitivity - важный принцип: алгоритм не должен тратить O(n^2), если ответ содержит O(1) элементов.

Ключевые идеи

• **Sweep line** - парадигма: вертикальная линия движется по плоскости, обрабатывая события (endpoints, intersections)
• **Bentley-Ottmann** O((n+k) log n): event queue + status BST. Проверяем только соседей в status
• **Red-Blue Intersections:** находим пересечения только между двумя группами - модифицированный sweep line
• **Output-sensitivity:** O(n log n + k) - честная оценка, не штрафующая за малое число пересечений

Связанные темы

Sweep line - универсальная парадигма, применяемая далеко за пределами пересечения отрезков:

• Точки, отрезки, полигоны — Базовые примитивы: cross product и orientation - основа проверки пересечения пар
• Выпуклая оболочка — Graham Scan - тоже «обход по порядку». Output-sensitivity: Chan's O(n log h) vs Graham O(n log n)
• Сбалансированные деревья — Status structure - BST. Эффективность sweep line зависит от O(log n) операций в BST

Вопросы для размышления

• Sweep line двигается слева направо. Что меняется, если все отрезки вертикальные? Как адаптировать алгоритм?
• Bentley-Ottmann хуже наивного при k = O(n^2). Почему на практике это редко проблема?
• Как применить sweep line для задачи: найти все пары прямоугольников, которые пересекаются?

Связанные уроки

• cgeom-01 — Cross product и orientation - фундамент проверки пары отрезков
• cgeom-02 — Graham Scan - тоже sweep-идея, output-sensitivity: Chan O(n log h)
• alg-05 — Сбалансированные BST - основа status structure в Bentley-Ottmann
• cgeom-04 — Диаграмма Вороного строится через Fortune sweep line
• cgeom-05 — Триангуляция Делоне использует sweep для построения
• alg-07 — Interval trees - альтернатива sweep для прямоугольных запросов
• la-04-lines-planes