Алгоритм заметающей прямой

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