Алгоритм развертки линии - Sweep line algorithm
В вычислительной геометрии , А развертка линия алгоритм или алгоритм плоской развертки является алгоритмической парадигмой , которая использует концептуальную линию развертки или поверхность развертки решать различные проблемы в евклидове пространства . Это один из ключевых методов вычислительной геометрии.
Идея алгоритмов этого типа состоит в том, чтобы представить, что линия (часто вертикальная линия) проходит по плоскости или перемещается по плоскости, останавливаясь в некоторых точках. Геометрические операции ограничиваются геометрическими объектами, которые либо пересекаются, либо находятся в непосредственной близости от линии сдвига, когда она останавливается, и полное решение доступно, когда линия проходит через все объекты.
История
Этот подход можно проследить до алгоритмов рендеринга в компьютерной графике в виде строк с последующим использованием этого подхода в ранних алгоритмах проектирования компоновки интегральных схем , в которых геометрическое описание ИС обрабатывалось параллельными полосами, поскольку полное описание не могло уместиться в объем памяти.
Приложения
Применение этого подхода привело к прорыву в вычислительной сложности геометрических алгоритмов, когда Шамос и Хоуи представили алгоритмы для пересечения отрезков линии в плоскости, и, в частности, они описали, как комбинация подхода строк развертки с эффективными структурами данных ( самобалансировка деревья бинарного поиска ) позволяет определить, есть ли пересечения между N сегментами на плоскости при временной сложности O ( N log N ). Тесно связанный алгоритм Бентли – Оттмана использует технику линий развертки, чтобы сообщить обо всех K пересечениях между любыми N сегментами на плоскости с временной сложностью O (( N + K ) log N ) и пространственной сложностью O ( N ).
С тех пор этот подход использовался для разработки эффективных алгоритмов для ряда задач, таких как построение диаграммы Вороного ( алгоритм Форчун ) и триангуляция Делоне или логические операции над многоугольниками .
Обобщения и расширения
Топологическая развертка - это форма развертки плоскости с ослабленным упорядочением точек обработки, что позволяет избежать необходимости полной сортировки точек; он позволяет более эффективно выполнять некоторые алгоритмы развертки линии.
Вращающихся суппорты методику проектирования геометрических алгоритмов можно также интерпретировать как форму плоской развертки, в проективном двойном входной плоскости: форма проективной двойственности преобразует наклон линии в одной плоскости в й координату точки в двойной плоскости, поэтому прохождение по линиям в отсортированном порядке по их наклону, выполняемое алгоритмом вращающегося штангенциркуля, является двойным по отношению к прохождению через точки, отсортированные по их координатам x в алгоритме развертки плоскости.
Широкий подход можно обобщить на более высокие измерения.