Алгоритм развертки линии - Sweep line algorithm

Анимация Алгоритм фортуны, техника развертки линии для построения Диаграммы Вороного.

В вычислительная геометрия, а алгоритм линии развертки или же алгоритм развертки плоскости является алгоритмическая парадигма который использует концептуальный линия развертки или же подметать поверхность решать различные проблемы в Евклидово пространство. Это один из ключевых методов вычислительной геометрии.

Идея алгоритмов этого типа состоит в том, чтобы представить, что линия (часто вертикальная линия) проходит по плоскости или перемещается по плоскости, останавливаясь в некоторых точках. Геометрические операции ограничиваются геометрическими объектами, которые либо пересекаются, либо находятся в непосредственной близости от линии сдвига, когда она останавливается, и полное решение доступно, когда линия проходит через все объекты.

История

Этот подход можно проследить до алгоритмы сканирования рендеринга в компьютерная графика, с последующим использованием этого подхода в ранних алгоритмах макет интегральной схемы дизайн, в котором геометрическое описание ИС обрабатывалось в параллельных полосах, потому что все описание не помещалось в памяти.^{[нужна цитата ]}

Приложения

Применение этого подхода привело к прорыву в вычислительная сложность геометрических алгоритмов, когда Шамос и Хои представили алгоритмы для пересечение отрезка прямой в плоскости, и, в частности, они описали, как сочетание подхода строки сканирования с эффективными структурами данных (самобалансирующиеся бинарные деревья поиска ) позволяет определить, есть ли пересечения между N отрезки на плоскости во временной сложности О (N бревноN).^[1] Тесно связанные Алгоритм Бентли – Оттмана для отчета обо всех K пересечения между любыми N отрезки на плоскости с временной сложностью O ((N + K) бревноN) и пространственной сложности O (N).^[2]

С тех пор этот подход использовался для разработки эффективных алгоритмов для ряда задач, таких как построение Диаграмма Вороного (Алгоритм фортуны ) и Триангуляция Делоне или же логические операции над полигонами.

Обобщения и расширения

Топологическая развертка - это форма развертки плоскости с ослабленным упорядочением точек обработки, что позволяет избежать необходимости полной сортировки точек; он позволяет более эффективно выполнять некоторые алгоритмы развертки линии.

В вращающиеся суппорты технику проектирования геометрических алгоритмов можно также интерпретировать как форму развертки плоскости в проективный дуальный входной плоскости: форма проективной двойственности преобразует наклон линии в одной плоскости в Икс-координата точки в двойной плоскости, поэтому прохождение по линиям в отсортированном порядке по их наклону, выполняемое алгоритмом вращающегося штангенциркуля, является двойным по отношению к прохождению через точки, отсортированные по их Икс-координаты в алгоритме развертки плоскости.

Широкий подход можно обобщить на более высокие измерения.

Рекомендации

1. Шамос, Майкл И.; Хои, Дэн (1976), "Проблемы геометрического пересечения", Proc. 17-й симпозиум IEEE. Основы компьютерных наук (FOCS '76), стр. 208–215, Дои:10.1109 / SFCS.1976.16, S2CID  124804.
2. Сувейн, Дайан (2008), Пересечение отрезка линии с использованием алгоритма развертки линии (PDF).