В вычислительной геометрии алгоритм прямой заметания или алгоритм плоской заметания — это алгоритмическая парадигма , которая использует концептуальную прямую заметания или поверхность заметания для решения различных задач в евклидовом пространстве . Это один из важнейших методов в вычислительной геометрии.
Идея алгоритмов этого типа заключается в том, чтобы представить, что линия (часто вертикальная) проносится или перемещается по плоскости, останавливаясь в некоторых точках. Геометрические операции ограничены геометрическими объектами, которые либо пересекают, либо находятся в непосредственной близости от линии проецирования, когда она останавливается, и полное решение доступно, как только линия пройдет по всем объектам.
Этот подход можно проследить до алгоритмов растровой строки рендеринга в компьютерной графике , за которыми последовало использование этого подхода в ранних алгоритмах проектирования компоновки интегральных схем , в которых геометрическое описание ИС обрабатывалось параллельными полосами, поскольку все описание не могло поместиться в памяти. [ необходима ссылка ]
Применение этого подхода привело к прорыву в вычислительной сложности геометрических алгоритмов, когда в 1976 году Шамос и Хоуи представили алгоритмы для пересечения отрезков прямых на плоскости. В частности, они описали, как сочетание подхода сканирующей строки с эффективными структурами данных ( самобалансирующиеся двоичные деревья поиска ) позволяет обнаружить, есть ли пересечения среди N отрезков на плоскости, со сложностью по времени O ( N log N ) . [ 1] Близкий алгоритм Бентли-Оттмана использует технику развертки линии для сообщения обо всех K пересечениях среди любых N отрезков на плоскости со сложностью по времени O(( N + K ) log N ) и сложностью по пространству O( N ) . [2]
С тех пор этот подход использовался для разработки эффективных алгоритмов для ряда задач вычислительной геометрии, таких как построение диаграммы Вороного ( алгоритм Форчуна ) и триангуляция Делоне или булевы операции над многоугольниками .
Топологическая развертка — это форма плоской развертки с простым упорядочением точек обработки, что позволяет избежать необходимости полной сортировки точек; это позволяет более эффективно выполнять некоторые алгоритмы прямой развертки.
Метод вращающегося штангенциркуля для проектирования геометрических алгоритмов также можно интерпретировать как форму плоской развертки в проективной двойственной плоскости входной плоскости: форма проективной двойственности преобразует наклон линии в одной плоскости в x -координату точки в двойственной плоскости, поэтому прогрессия по линиям в отсортированном порядке по их наклону, выполняемая алгоритмом вращающегося штангенциркуля, является двойственной прогрессии по точкам, отсортированным по их x -координатам в алгоритме плоской развертки. [ необходима ссылка ]
Подход «охвата» может быть обобщен на более высокие измерения. [3]