Алгоритм развертки линии
В вычислительной геометрии алгоритм развертки линии или алгоритм развертки плоскости — это алгоритмическая парадигма , которая использует концептуальную линию развертки или поверхность развертки для решения различных задач в евклидовом пространстве . Это один из важнейших методов вычислительной геометрии.
Идея алгоритмов этого типа состоит в том, чтобы представить, что линия (часто вертикальная линия) перемещается по плоскости, останавливаясь в некоторых точках. Геометрические операции ограничены геометрическими объектами, которые либо пересекают линию развертки, либо находятся в непосредственной близости от нее, когда она останавливается, а полное решение становится доступным после того, как линия пройдет через все объекты.
История
[ редактировать ]Этот подход можно отнести к алгоритмам рендеринга строк в компьютерной графике с последующим использованием этого подхода в ранних алгоритмах проектирования топологии интегральных схем , в которых геометрическое описание ИС обрабатывалось в параллельных полосах, поскольку все описание не могло уместиться в памяти. . [ нужна ссылка ]
Приложения
[ редактировать ]Применение этого подхода привело к прорыву в вычислительной сложности геометрических алгоритмов, когда Шамос и Хоуи представили алгоритмы пересечения отрезков прямой на плоскости в 1976 году. В частности, они описали, как сочетание подхода развертки с эффективными структурами данных ( самостоятельность) балансировка двоичных деревьев поиска ) позволяет определить, есть ли пересечения среди сегментов на плоскости с временной сложностью O N ( N log N ) . [ 1 ] Тесно связанный алгоритм Бентли-Оттмана использует метод прогонки линии для сообщения обо всех K пересечениях среди любых N сегментов на плоскости с временной сложностью O(( N + K ) log N ) и пространственной сложностью O( N ) . [ 2 ]
С тех пор этот подход использовался для разработки эффективных алгоритмов для решения ряда задач вычислительной геометрии, таких как построение диаграммы Вороного ( алгоритм Фортьюна ) и триангуляция Делоне или логические операции над многоугольниками .
Обобщения и расширения
[ редактировать ]Топологическая очистка — это форма плоской очистки с простым упорядочиванием точек обработки, что позволяет избежать необходимости полной сортировки точек; это позволяет более эффективно выполнять некоторые алгоритмы развертки линии.
Технику вращающегося штангенциркуля для разработки геометрических алгоритмов можно также интерпретировать как форму прогонки плоскости в проективно-двойственной входной плоскости: форма проективной двойственности преобразует наклон линии в одной плоскости в x координату точки в двойной плоскости, поэтому продвижение по линиям, отсортированным по их наклону, выполняемое с помощью алгоритма вращающихся штангенциркулей, двойственно по отношению к прохождению через точки, отсортированные по их координатам x , в алгоритме прогонки по плоскости. [ нужна ссылка ]
Охватывающий подход может быть обобщен на более высокие измерения. [ 3 ]
Ссылки
[ редактировать ]- ^ Шамос, Майкл И .; Хоуи, Дэн (1976), «Геометрические задачи пересечения», Proc. 17-й симпозиум IEEE. Основы информатики (FOCS '76) , стр. 208–215, doi : 10.1109/SFCS.1976.16 , S2CID 124804 .
- ^ Сувен, Дайан (2008), Пересечение отрезков линии с использованием алгоритма развертки линии (PDF) .
- ^ Синклер, Дэвид (11 февраля 2016 г.). «Алгоритм 3D-сканирования оболочки для расчета выпуклых оболочек и триангуляции Делоне». arXiv : 1602.04707 [ cs.CG ].