Алгоритм переміщення лінії: Розв’язування задач з геометрії…

Основна ідея: Рухома лінія та активний набір

В центрі уваги алгоритму лінії переміщення – дуже проста уявність: уявна вертикальна лінія, що ковзає зліва направо по площині, яка містить точки, відрізки прямих, прямокутники або інші фігури. Замість того, щоб вивчати, як кожен об’єкт взаємодіє з кожним іншим об’єктом, алгоритм турбується лише про невелику кількість об'єктів, які торкаються лінії переміщення. Ця невелика група називається активним набором, і це вся таємниця швидкості цієї техніки. Коли лінія рухається вперед, активний набір не змінюється безперервно; він змінюється лише в певні моменти, що називаються точками подій, такими як початок відрізка, кінець відрізка або перетин двох відрізків. Між подіями нічого значущого не відбувається, тому алгоритм може безпосередньо перейти від однієї події до іншої. Події зазвичай обробляються в порядку зліва направо за допомогою черги пріоритетності, а сам активний набір підтримується у структурі даних, яка забезпечує швидке введення, видалення та запити щодо сусідів, найчастіше збалансованим бінарним пошуковим деревом. Це поєднання – черга подій, що керує оновленнями активного набору – є скелетом під майже кожним алгоритмом лінії переміщення, незалежно від конкретної геометричної задачі, яку потрібно вирішити.

Класичний приклад: Визначення всіх перетинів лінійних відрізків

Підручник демонструє метод переміщення лінії для виявлення кожного перетину між множиною лінійних відрізків. Коли рухома лінія рухається зліва направо, вона підтримує всі відрізки, які зараз перетинає, в збалансованому бінарному пошуковому дереві, відсортованому за вертикальною позицією, тобто їх координату y у поточному місці розташування лінії. Важливими є три види подій: лівий кінець відрізка, який вставляє його в дерево; правий кінець відрізка, який видаляє його; та точка перетину, де два відрізки міняються місцями у вертикальному порядку. Ключовим моментом є те, що два відрізки можуть лише нещодавно перетинатися один з одним, якщо вони були сусідніми у вертикальному порядку незадовго до перетину. Відрізок, який значно вищий за інший у порядку, не може раптово перетнути його без спочатку стати сусідом йому, оскільки шляхи перетину повинні проходити через кожен порядок між ними. Це означає, що алгоритм ніколи не повинен перевіряти кожну пару відрізків на предмет перетину. Йому потрібно лише перевіряти пари, які стають сусідніми у дереві, кожного разу, коли вставляється, видаляється або відрізок міняє позицію зі своїм сусідом. Кожна така перевірка сусідства є дешевою, і загальна кількість перевірок залишається пропорційною кількості відрізків плюс фактичній кількості знайдених перетинів, що робить весь процес дивовижно ефективним навіть для великих та захаращених вхідних даних.

Чому це краще за грубе порівняння парів

Наївний спосіб знайти перетини сегментів - це порівнювати кожен сегмент з кожним іншим сегментом, підхід, який витрачає час пропорційно n на квадрат, де n - кількість сегментів. Подвоїти вхідні дані призведе до збільшення роботи приблизно в чотири рази; із тисячами сегментів це стає болісно повільно. Підхід з використанням sweep-лінії досягає часу виконання пропорційного приблизно n log n для багатьох практичних випадків, а також додаткового часу пропорційного кількості фактичних перетинів. Причина цього драматичного покращення полягає в тому, що sweep лише порівнює локально сусідні об'єкти замість будь-якої можливої пари. Підтримка активної множини у збалансованому пошуковому дереві коштує часу пропорційного log n на вставку, видалення або обмін суміжністю, і таких подій лише порядок n для кінцевих точок, плюс одна подія за перетин. Замість того, щоб ставити n квадрат нездійсненних запитань, наприклад, чи перетинаються ці два сегменти, що знаходяться далеко один від одного, алгоритм ставить набагато менше значущих запитань, кожне з яких можна швидко і точно відповісти, оскільки він використовує геометричний факт, що далекі, несусідні сегменти не можуть перетнутися без спочатку стати сусідами.

Інші Класичні Проблеми, Розв’язані за допомогою Переміщення Лінії

Перетин сегментів є лише найвідолішим застосуванням цієї техніки; переміщення лінії зустрічається в різних областях обчислювальної геометрії. Задача про знаходження найближчих пар точок у наборі, тобто пошук двох точок, які найближче одна до одної, може бути вирішена шляхом переміщення лінії по відношенню до відсортованих точок, зберігаючи вузький вертикальний проміжок кандидатів у активному наборі, і не вдаючись до повного порівняння пар. Обчислення площі об’єднання перекриваючихся прямокутників використовує лінію переміщення, яка зупиняється в лівій та правій межах кожного прямокутника, підтримуючи структуру, яка відстежує, які вертикальні інтервали зараз покриті, щоб довжина покриття могла бути виміряна на кожній події та помножена на горизонтальну відстань до наступної події. Можливо, найелегагантнішим застосуванням є алгоритм Фортуни для побудови діаграми Вороного, який розділяє площину на області, найближчі до кожного з набору вхідних точок. Алгоритм Фортуни переміщує лінію по площині, підтримуючи так звану «пляжну лінію» – ланцюг параболічних дуг, що представляють межу між точками, які вже пройшли лінією переміщення, та незадіяною областю за нею, з новими дугами, що з’являються, і старими, що зникають на визначених подіях.

Чому ця техніка так добре узагальнюється

Лінійне переміщення – це не вузька хитринка, яка випадково працює на кількох задачах; це загальна стратегія, яка успішно застосовується завдяки глибокому структурному факту про геометрію. Більшість корисних геометричних зв’язків є локальними, тобто вони залежать лише від сусідніх об'єктів, і змінюються лише в певних, чітко визначених моментах, а не безперервно та непередбачувано. Сусідні сегменти у вертикальному порядку не перемішуються випадково; вони міняються лише на добре визначених точках перетину. Вклад прямокутника у загальну площу не коливається хаотично; він змінюється лише на лівому та правому краях прямокутника. Межа області Вороного не деформується випадково; вона структурується лише під час певних подій з параболидами. Оскільки зміни обмежуються дискретними подіями, алгоритм ніколи не повинен перераховувати всю картину заново, коли він сканує площину. Йому потрібно лише реагувати на кожну подію, яка виникає, оновлюючи компактний активний набір і рухатися далі. Саме тому лінійне переміщення так легко переноситься з перетинів сегментів до об’єднання прямокутників, до діаграм Вороного та безлічі інших проблем: будь-коли геометрична задача може бути сформульована як послідовність локальних, дискретних подій, що проходять по координатах, лінійне переміщення, ймовірно, перетворить повільний, вичерпний підхід у швидкий та елегантний.

Часті запитання

What exactly counts as an event point in a line sweep algorithm?

An event point is any location along the sweep direction where the active set must change. For segment intersection, events are left endpoints, right endpoints, and crossing points. For rectangle union area, events are the left and right edges of each rectangle. The specific events depend on the problem, but they always mark moments where something meaningful happens to the objects the sweep line is tracking.

Why is a balanced binary search tree used to store the active set?

A balanced binary search tree lets the algorithm insert, delete, and find neighboring elements quickly, in time proportional to log n, where n is the number of active objects. Since line sweep repeatedly needs to know which objects are adjacent in the current ordering, and needs to update that ordering efficiently as objects enter and leave, a balanced tree is the natural fit.

Does line sweep only work with a vertical line moving left to right?

No, that is just the conventional description. The same idea works with a horizontal line sweeping top to bottom, a rotating line sweeping through angles, or even a circle expanding outward, as seen in Fortune's algorithm’s beach line. The key requirement is simply that objects can be ordered along the sweep direction and that interactions change only at discrete events.

Can line sweep algorithms handle objects other than line segments and rectangles?

Yes. Line sweep has been applied to circles, polygons, arcs, and more general curves, wherever the objects can be meaningfully ordered along the sweep direction and their relationships change at identifiable event points. The technique is a general algorithmic pattern, not something limited to straight-edged shapes.

Is line sweep always faster than brute force?

For problems with many local interactions, yes, line sweep is typically much faster because it avoids examining irrelevant pairs of far-apart objects. However, it requires careful implementation of the event queue and active-set data structure, and for very small inputs the overhead may not matter much. Its real advantage appears as the number of objects grows large.

Спробуйте наживо

Усе, що вище, працює прямо у вашому браузері — відкрийте The Line Sweep Algorithm: Solving Geometry Problems by Sweeping a Line Across the Plane і змінюйте параметри під час роботи. Нічого не встановлюється, нічого не завантажується на сервер, уся модель живе в одній вкладці.

▶ Відкрити симуляцію The Line Sweep Algorithm: Solving Geometry Problems by Sweeping a Line Across the Plane

Алгоритм переміщення лінії: Розв’язування задач з геометрії шляхом переміщення лінії по площині