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